Finance[US] Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
1.3k views
in RTU/BTU B.Tech(CSE-III Sem) DSA LAB by Goeduhub's Expert (5.8k points)
Insertion of Node at beginning in Doubly Linked List

1 Answer

0 like 0 dislike
by Goeduhub's Expert (5.8k points)
edited by
 
Best answer

Doubly Linked List

Doubly linked list is a linear data structure which is  type of linked list in which each node consist of data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space.

Singly linked listDoubly linked list
A singly linked list is a linked list where the node contains some data and a pointer to the next node in the listA doubly linked list is complex type of linked list where the node contains some data and a pointer to the next as well as the previous node in the list
It allows traversal only in one wayIt allows a two way traversal
It uses less memory per node (single pointer)It uses more memory per node(two pointers)
Complexity of insertion and deletion at a known position is O(n)Complexity of insertion and deletion at a known position is O(1)
If we need to save memory and searching is not required, we use singly linked listIf we need better performance while searching and memory is not a limitation, we go for doubly linked list
If we know that an element is located towards the end section, eg. ‘zebra’ still we need to begin from start and traverse the whole listIf we know that an element is located towards the end section e.g. ’zebra’ we can start searching from the Back.
Singly linked list can mostly be used for stacksThey can be used to implement stacks, heaps, binary trees.

Advantages of Doubly Linked list

  • We can traverse in both directions i.e. from starting to end and as well as from end to starting.
  • It is easy to reverse the linked list.
  • If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the previous node.

Disadvantages of Doubly Linked list

  • It requires more space per space per node because one extra field is required for pointer to previous node.
  • Insertion and deletion take more time than linear linked list because more pointer operations are required than linear linked list.

Applications 

  • The browser cache which allows you to hit the BACK buttons (a linked list of URLs).
  • Applications that have a Most Recently Used (MRU) list (a linked list of file names).
  • A stack, hash table, and binary tree can be implemented using a doubly linked list. 
  • Undo functionality in Photoshop or Word (a linked list of state).
  • A great way to represent a deck of cards in a game.

Node Creation

struct node   

{  

    struct node *prev;  

    int data;  

    struct node *next;  

};  

struct node *head;  

Insertion at Beginning in Doubly LinkedList-

insertion of node at begining in doubly linkedlist

Algorithm-

  1. IF ptr = NULL
  2. SET NEW_NODE = ptr
  3. SET ptr = ptr -> NEXT
  4. SET NEW_NODE -> DATA = VAL
  5. SET NEW_NODE -> PREV = NULL
  6. SET NEW_NODE -> NEXT = START
  7. SET head -> PREV = NEW_NODE
  8. SET head = NEW_NODE
  9. EXIT

Program Code

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

void insertbeginning(int);

struct node

{

    int data;

    struct node *next;

    struct node *prev;

};

struct node *head;

void main ()

{

    clrscr();

    int choice,item;

    do

    {

printf("\nEnter the item which you want to insert: ");

scanf("%d",&item);

insertbeginning(item);

printf("Press 0 to insert more! ");

scanf("%d",&choice);

    }while(choice == 0);

}

void insertbeginning(int item)

{

   struct node *ptr = (struct node *)malloc(sizeof(struct node));

   if(ptr == NULL)

   {

       printf("\nOVERFLOW");

   }

   else

   {

   if(head==NULL)

   {

       ptr->next = NULL;

       ptr->prev=NULL;

       ptr->data=item;

       head=ptr;

   }

   else

   {

       ptr->data=item;

       ptr->prev=NULL;

       ptr->next = head;

       head->prev=ptr;

       head=ptr;

   }

}

}

Output


For more Data Structures & Algorithms Tutorials Click here


Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...