Linked List Data Structure

Linked List

Prerequisites for Linked List
Definition of linkedlist
Important points of Linked List
Types of Linked List
Basic Operations performed on Linked List
Difference Between Linked List and Arrays
Drawbacks of Linked List
Applications of Linked List In real world
Singly Linked List in C
Doubly Linked List in C
Singly Circular Linked List in C
Doubly Circular Linked Listist in C
Add node in Singly Linked List
Display Data of Linked List
Deletion of a node from linked list

Pointer

A pointer is a variable which stores the address of another variable. By using a pointer we can directly access the memory address of the variable. Like any variable or constant, you must declare a pointer before using it to store any variable address.

The general form of a pointer variable declaration is type *variable-name;

Here, type is the pointer's base type; it must be a valid C data type and var-name is the name of the pointer variable. The asterisk * used to declare a pointer.

& - Address Operator

The "Address Of" Operator denoted by the ampersand character (&), & is a unary operator, which returns the address of a variable.

After declaration of a pointer variable, we need to initialize the pointer with the valid memory address; to get the memory address of a variable Address Of" (&) Operator is used.

Definition of linkedlist

A linked list is a sequence of data structures, which are connected together via links. Each link is connected to another. Linked list can be visualized as a chain of nodes, where every node points to the next node.

Important points of Linked List

Linked List contains a link element called first.
Each link carries a data field(s) and a link field called next.
Each link is linked with its next link using its next link.
Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

Simple Linked List − Item navigation is forward only.
Doubly Linked List − Items can be navigated forward and backward.
Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations on Linked List

Following are the basic operations supported by a list.

Insertion − Adds an element to the list.
Deletion − Deletes an element from the list.
Display − Displays the complete list.
Search − Searches an element in the linked list.
Delete − Deletes an element from the linked list

Difference Between Linked List and Arrays

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other.

Differences between Linked list and Arrays Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.

In addition, memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.

Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.

In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.

In a linked list though, you have to start from the head and work your way through until you get to the fourth element.

p>Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower. Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.

For example, suppose we maintain a sorted list of IDs in an array id[]. id[] = [1000, 1010, 1050, 2000, 2040, …..].And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved. So Linked list provides the following two advantages over arrays

1) Dynamic size
2) Ease of insertion/deletion

(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive because a room has to be created for the new elements and to create room existing elements have to be shifted.

Drawbacks of Linked List

Linked lists have following drawbacks

Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
Extra memory space for a pointer is required with each element of the list. Arrays have better cache locality that can make a pretty big difference in performance.

Applications of Linked List In real world

Image viewer – Previous and next images are linked, hence can be accessed by next and previous button.
Previous and next page in web browser – We can access previous and next url searched in web browser by pressing back and next button since, they are linked as linked list.
Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

Singly Linked List

Description of singly Linked List
Singly Linked List structure
Allocate memory for Structure node
Syntax of malloc() function
Syntax of creating Node structure
Creating Singly Linked List
Display Data of Singly Linked List
Traverse/Display a Singly Linked List
Inserting a Node in Singly Linked List
Modification in pointers while inserting node in Singly Linked List
Inserting node at the end of linkedlist
Modification in pointers while inserting node at the end in Singly Linked List
Insert a node at given position in Singly Linked List
Algorithm for searching data in Singly Linked List
Search Logic of singly linked list
Deletion of a node from linked list
Delete a node from the end in Singly Linked List
Delete a node from specified position in Singly Linked List

A singly linked list is a type of linked list which is unidirectional. It can be traversed only in one direction from head to last node. Each element in the linked list is called as node.

A single node contains data and pointer to the next node which helps in maintaining the structure of the list.

Description of singly Linked List

The first node is called as start node or head. It contains the address of the first node.
The last node called as tail points to NULL which helps us to find out where the linked list ends.
Different operations like insertion, deletion, searching and traversal can be performed on the linked list.
All nodes are stored randomly in memory.
In SLL we cannot traverse in reverse direction.

Singly Linked List structure



struct node



int data;   

struct node *next;  

        };

Declaring a node of Singly Linked List

The node structure defined contains two parts:-We have defined our own data type containing an integer and pointer.

Data part:- The data part is the value of the element present.
Address part:- It is a pointer variable which stores address of the next node so it is of type structure.ie:- It points to a node structure containing two parts Data Part and address part.

We have defined our own data type. Still memory is not yet been allocated to the structure. We also need to declare head pointer. We can declare it as struct node *head; Here head pointer stores the address of node and the data type of this node is struct node.

Initially when list is not made the head pointer will point to nothing ie:- NULL To allocate memory we need to use malloc() The syntax of malloc() is malloc(sizeof(struct node)) The size will be of two parts ie:- size of data and size of pointer.

Malloc() returns a void pointer so we need to store the value returned by malloc to a pointer.

Allocate memory for Structure node

We can allocate memory to a node using dynamic memory allocation. We can do it by making use of malloc() or calloc() function.

Syntax of malloc()

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

Thus we have created a memory block so newnode will have some address in it. We can store some address for that linked list. We can accept the value from user.

Syntax of creating Node structure

struct node

{

int data;

struct node * next;

};

struct node *newnode, head;

Creating Singly Linked List

head= NULL;

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

printf(“enter data”);

scanf(“%d”, &newnode->data);

newnode->next =  NULL;

If(head==NULL)

head=temp=newnode;

else

temp->next=newnode;

Temp=newnode;

Display Data of Linked List

To display data we can use either while loop or for loop. While loop continues till we do not reach NULL. For loop starts from first node and traverses all nodes till we don’t get a NULL.

While(temp!=NULL)

Traverse/Display a Singly Linked List



void display()

{

 struct node *temp;

temp=start;

while(temp!=NULL)

{

printf("%d",temp->data);

temp=temp->next;

  }

}

Inserting a Node in SLL

At the beginning
At the End
After a given position

Modification in pointers while inserting node in ssl

newNode->next = head; // Link address part head = newNode; 

head = newNode;

Inserting node at the end of linkedlist

Create a new node and make sure that the address part of the new node points to NULL i.e. newnode->next=NULL Traverse to the last node of the linked list and connect the last node of the list with the new node, i.e. last node will now point to new node.

lastNode->next = newNode.

Modification in pointers while inserting node at the end



newNode->data = data; // Link the data part 

newNode->next = NULL; 

temp = head; // Traverse to the last node 

while(temp->next != NULL) 

 temp = temp->next;

 temp->next = newNode; // Link address part

Insert a node at given position

Traverse to the n-1 position of the linked list and connect the new node with the n+1 node. Means the new node should also point to the same node that the n-1 node is pointing to.

newnode->next=temp->

next where temp is the n-1 node Now at last connect the n-1th node with the new node i.e. the n-1th node will now point to new node. (temp->next = newNode; where temp is the n-1th node).

Searching elements in Singly Linkedlist

Searching is performed in order to find the location of a particular element in the list. Searching any element in the list needs traversing through the list and make the comparison of every element of the list with the specified element.

If the element is matched with any of the list element then the location of the element is returned from the function.

Algorithm for searching data in Singly Linked List

Step 1: SET PTR = HEAD
Step 2: Set I = 0
Step 3: IF PTR is NULL Data not found
Step 4: REPEAT STEP 5 TO 7 UNTIL PTR != NULL
Step 5: Check if ptr → data = searchitem write i+1 End of IF
Step 6: I = I + 1
Step 7: PTR = PTR → NEXT [END OF LOOP]
Step 8: EXIT.

Search Logic of singly Linked List


while (ptr!=NULL)  

{  

if(ptr->data ==item)  

{  

printf("item found at location %d ",i+1);  

flag=0;  

  }   

 else  

 {  

flag=1;  

 }  

 i++;  

ptr = ptr -> next;  

  }  

 if(flag==1)  

   {  
 printf("Item not found\n");
 }

Deletion of a node from Linked List

At the beginning.
At the end.
From the specified position.

Deletion of a node from beginning

Deleting a node from the beginning of the list is the simplest operation of all. It just needs a few adjustments in the node pointers.

Since the first node of the list is to be deleted, therefore, we just need to make the head point to the next of the head. This will be done by using the following statements.

ptr = head;                              head=ptr->next;

Now, free the pointer ptr which was pointing to the head node of the list. This will be done by using the following statement.



free(ptr)  

void begdelete()  

{  

struct node *ptr;  

if(head == NULL)  

{ 
 
  printf("\nList is empty");   
  
  }  

 else   

   {  

  ptr = head;  
                                       // Address of head is stored in ptr variable.

head = ptr->next;  
//Store ptr->next ie:- Address of next node in head

free(ptr);    
// Free the previously allocated ptr memory variable.

printf("\n Node deleted from the begining ...");  

  }  

     }

Delete a node from the end in Singly Linked List

There are two scenarios in which, a node is deleted from the end of the linked list. There is only one node in the list and that needs to be deleted.

There are more than one node in the list and the last node of the list will be deleted. In the first scenario, the condition head → next = NULL will survive and therefore, the only node head of the list will be assigned to null. This will be done by using the following statements.



ptr = head;  

head = NULL ;

free(ptr);

The condition head → next = NULL would fail and therefore, we have to traverse the node in order to reach the last node of the list. For this purpose, just declare a temporary pointer temp and assign it to head of the list. We also need to keep track of the second last node of the list.

For this purpose, two pointers ptr and ptr1 will be used where ptr will point to the last node and ptr1 will point to the second last node of the list. this all will be done by using the following statements.


ptr = head;   

 while(ptr->next != NULL) {
 
 ptr1 = ptr;  

 ptr = ptr ->next;  

}

Now, we just need to make the pointer ptr1 point to the NULL and the last node of the list that is pointed by ptr will become free. It will be done by using the following statements. ptr1->next = NULL; free(ptr);

Delete a node from specified position in Singly Linked List

To delete a node from a linked list, we need to do these steps Find the previous node of the node to be deleted. Change the next pointer of the previous node> Free the memory of the deleted node.



void delete_specified()  

 {

struct node *ptr, *ptr1;  

int loc,i;   

scanf("%d",&loc);  

ptr=head; 

for(i=0;i<loc;i++)  

{  
ptr1 = ptr;       

  ptr = ptr->next;  

   if(ptr == NULL)  

 {  

printf("\nThere are less than %d elements in the list..\n",loc);  

 return;  

  }  

}  

ptr1 ->next = ptr ->next;  

free(ptr);  
printf("\nDeleted %d node ",loc);  

    }

//Declaring struct node


struct node

 {

  int data; 

  struct node *next; 

  };

Traverse Linked List

Displaying the contents of a linked list is very simple. We keep moving the temp node to the next one and display its contents.

When temp is NULL, we know that we have reached the end of the linked list so we get out of the while loop.

Code to traverse



struct node *temp = head; 

printf("\n\nList elements are - \n"); 

while(temp != NULL) 

{ 

printf("%d --->",temp->data); 

temp = temp->next;

 }

Add node in Singly Linked List,Steps

You can add elements to either the beginning, middle or end of the linked list. Add to the beginning. Allocate memory for new node Store data. Change next of new node to point to head Change head to point to recently created node.

Add node to the End of linked list

Allocate memory for new node
Store data
Traverse to last node
Change next of last node to recently created node

Add node to the middle of linked list

Allocate memory and store data for new nodes.
Traverse to node just before the required position of new node.
Change next pointers to include new node in between.

Steps for Deleting nodes from Beginning,End,Middle position of linked list

Delete from beginning

Point head to the second node head = head->next;

Delete from end

Traverse to second last element
Change its next pointer to null

Delete from Middle

Traverse to element before the element to be deleted.
Change next pointers to exclude the node from the chain.
Deallocate the memory using free.

Doubly Linked List

Basic Operations performed on doubly linked list
Important points about doubly Linked List
Advantages of doubly linked list over Singly Linked List
Disadvantages of doubly linked list over singly linked list
Traversing doubly linked list
Code for creating doubly Linked List
Searching Element in Doubly Linked List
Insertion in doubly Linked List
Insert a new node at end position in double Linked List
Inserting new node at given position step by step in doubly Linked List
Delete a node from start position in Doubly Linked List
Deleting node at the position in doubly Linked List

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backwardeasily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.

Data − It stores data in a linked list.
Next − Each link of a linked list contains a link to the next node called Next.
Prev − Each link of a linked list contains a link to the previous node called Prev.

Basic Operations performed on doubly linked list

Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Insert at Last − Adds an element at the end of the list.
Delete the Last − Deletes an element from the end of the list.
Insert After − Adds an element after an item of the list.
Delete − Deletes an element from the list using the key.
Display forward − Displays the complete list in a forward manner.
Display backward − Displays the complete list in a backward manner.

Important points about doubly Linked List

Doubly Linked List contains a link element called first and last.
Each link carries a data field(s) and two link fields called next and prev.
Each link is linked with its next node using its next link.
Each link is linked with its previous node using its previous link.
The last link carries a link as null to mark the end of the list.

Advantages of doubly linked list over Singly Linked List

A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
We can quickly insert a new node before a given node.

Disadvantages of doubly linked list over singly linked list

Every node of the DLL requires extra space for a previous pointer.
All operations require an extra pointer to be maintained.
For example, in insertion, we need to modify previous pointers together with next pointers.

Code for creating doubly Linked List

Adding element in doubly Linked List



void create()

{

    int x;

        NODE *temp,*q;

temp=(NODE*)malloc (sizeof(NODE));

 printf("\n Enter value of data :");

    scanf("%d", &x);

      temp->data=x;

       temp->next=NULL;

if(start==NULL)

        start=temp;

            else

                {

        q=start;

                                while(q->next!=NULL)

                                            q=q->next;

                                            q->next=temp;

                                           temp->prev=q;

                                                }

         }

Traversing doubly linked list


void display()

{

NODE *q;

q=start;

printf("NULL <=> ");

while(q!=NULL)

{

printf("%d <=> ",q->data);

                                    q=q->next;

                                        }

                                        printf("NULL");

                                        }

Searching Element in Doubly Linked List

void search()

{

 NODE *temp,*q;

 int x,pos;

printf("\n enter element to Search:");

scanf("%d",&x);

q=start;

pos=1;

while(q!=NULL)

{

if(q->data==x)

{

printf("\n element found in the LIST at %d position.",pos);

 break;

     }

q=q->next;

   pos++;

    }

   if(q==NULL)

 printf("\n Element doesnot exist");

 }

Insertion in doubly Linked List

insertion at beginning in Doubly Linked List

As in doubly linked list, each node of the list contains double pointers therefore we have to maintain more number of pointers in doubly linked list as compared to singly linked list.

There are two scenarios of inserting any element into a doubly linked list. Either the list is empty or it contains at least one element. Perform the following steps to insert a node in a doubly linked list at beginning.

Perform Insertion of node in Doubly circular linked list

Allocate the space for the new node in the memory. This will be done by using the following statement. ptr = (struct node *)malloc(sizeof(struct node));

Check whether the list is empty or not. The list is empty if the condition head == NULL holds. In that case, the node will be inserted as the only node of the list and therefore the prev and the next pointer of the node will point to NULL and the head pointer will point to this node.

   

 ptr->next = NULL;  

 ptr->prev=NULL;  

 ptr->data=item;  

                                head=ptr;

In the second scenario, the condition head == NULL becomes false and the node will be inserted in the beginning. The next pointer of the node will point to the existing head pointer of the node. The prev pointer of the existing head will point to the new node being inserted.

This will be done by using the following statements. ptr->next = head; head→prev=ptr;

Insert a new node at end

In order to insert a node in doubly linked list at the end, we must make sure whether the list is empty or it contains any element. Use the following steps in order to insert the node in the doubly linked list at the end.

Allocate the memory for the new node. Make the pointer ptr point to the new node being inserted. ptr = (struct node *) malloc(sizeof(struct node));



ptr->next = NULL;  

ptr->prev=NULL;  

ptr->data=item;  

head=ptr;

In the second scenario, the condition head == NULL becomes false. The new node will be inserted as the last node of the list. For this purpose, we have to traverse the whole list in order to reach the last node of the list. Initialize the pointer temp to head and traverse the list by using this pointer.

   
     temp = head;   

      while (temp != NULL)  

       {  
     temp = temp → next;   }

The pointer temp point to the last node at the end of this while loop. Now, we just need to make a few pointer adjustments to insert the new node ptr to the list. First, make the next pointer of temp point to the new node being inserted i.e. ptr. temp→next =ptr;

make the previous pointer of the node ptr point to the existing last node of the list i.e. temp. ptr → prev = temp;

make the next pointer of the node ptr point to the null as it will be the new last node of the list. ptr → next = NULL

Inserting new node at given position step by step

Traverse to n-1 nodes in the list. Where n is the position to insert. Say temp now points to the n-1 node. Suppose you need to insert a node at the third position.
Create a new node that is to be inserted and assign some data to its data field.
Connect the next address field of new node with the node pointed by next address field of temp node.
Connect the previous address field of newnode with the temp node.
Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newNode.
Connect the next address field of temp node to newNode i.e. temp->next will now point to newNode.

Delete a node from start position

Deletion in a doubly linked list at the beginning is the simplest operation.

Step 1:- We just need to copy the head pointer to pointer ptr ptr = head;
Step 2:- shift the head pointer to its next. head = head → next;
Step 3:- Now make the prev of this new head node point to NULL. This will be done by using the following statements. head → prev = NULL
Step 4:- Now free the pointer ptr by using the free function. free(ptr)

STEP 1: SET PTR = HEAD
STEP 2: SET HEAD = HEAD → NEXT
STEP 3: SET HEAD → PREV = NULL
STEP 4: FREE PTR

Deleting node at the position

Deletion of the last node in a doubly linked list needs traversing the list in order to reach the last node of the list and then make pointer adjustments at that position. In order to delete the last node of the list, we need to follow the following steps.

If the list is already empty then the condition head == NULL will become true and therefore the operation can not be carried on.

If there is only one node in the list then the condition head → next == NULL become true. In this case, we just need to assign the head of the list to NULL and free head in order to completely delete the list.

Otherwise, just traverse the list to reach the last node of the list. This will be done by using the following statements.

Deleting node at the end position of doubly linked list



q = head;   

if(q->next != NULL)  

{  

q = q-> next;   

     }

The ptr would point to the last node at the end of the for loop. Just make the next pointer of the previous node of ptr to NULL. q → prev → next = NULL free the pointer as this the node which is to be deleted. free(ptr)

Deleting node from specific position In doubly linked list.

Let us suppose that we want to delete nodes from 2nd position...

Traverse to the Nth node of the linked list, let's say a pointer current points to the Nth node in our case 2 nodes.
Link the node behind the current node with the node ahead of the current node, which means now the N-1th node will point to the N+1th node of the list. Which can be implemented as current->prev-> next = current->next
If N+1th node is not NULL then link the N+1th node with N-1th node i.e. now the previous address field of N+1th node will point to N-1th node. Which can be implemented as current->next->prev = current->prev.
Finally delete the current node from memory and you are done.

Singly Circular Linked List

Inserting node at start position in Singly Circular Linked List.
Inserting node at end position in Singly Circular Linked List.
Delete node at start position in Singly Circular lis
Delete node at end position in Singly Circular list

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked lists as well as circular doubly linked lists.

We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.

The last link's next points to the first link of the list in both cases of singly as well as doubly linked list. The first link's previous points to the last of the list in case of doubly linked lists.

Inserting node at start position in Singly Circular Linked List.

Firstly, allocate the memory space for the new node by using the malloc method of C language. struct node *ptr = (struct node *)malloc(sizeof(struct node));

In the second scenario, the condition head == NULL will become false which means that the list contains at least one node. In this case, we need to traverse the list in order to reach the last node of the list. This will be done by using the following statement.


  
  temp = head;  

  while(temp->next != head)  

  temp = temp->next;

At the end of the loop, the pointer temp would point to the last node of the list. Since, in a circular singly linked list, the last node of the list contains a pointer to the first node of the list.

Therefore, we need to make the next pointer of the last node point to the head node of the list and the new node which is being inserted into the list will be the new head node of the list therefore the next pointer of temp will point to the new node ptr.

This will be done by using the following statements. temp -> next = ptr; the next pointer of temp will point to the existing head node of the list. ptr->next = head; Now, make the new node ptr, the new head node of the circular singly linked list. head = ptr;

Inserting node at the end position in Singly Circular Linked List

Firstly, allocate the memory space for the new node by using the malloc method of C language.

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

temp = head; while(temp->next != head) temp = temp->next;

At the end of the loop, the pointer temp would point to the last node of the list. Since, the new node which is being inserted into the list will be the new last node of the list. Therefore the existing last node i.e. temp must point to the new node ptr. This is done by using the following statement.

temp -> next = ptr; The new last node of the list i.e. ptr will point to the head node of the list. ptr -> next = head;

Delete node at start position in Singly Circular list

If the list contains more than one node then, in that case, we need to traverse the list by using the pointer ptr to reach the last node of the list. This will be done by using the following statements.



     ptr = head;   

    while(ptr -> next != head)  

   ptr = ptr -> next;

At the end of the loop, the pointer ptr point to the last node of the list. Since, the last node of the list points to the head node of the list. Therefore this will be changed as now, the last node of the list will point to the next of the head node.

ptr->next = head->next; Now, free the head pointer by using the free() method in C language free(head);

Make the node pointed by the next of the last node, the new head of the list. head = ptr->next; In this way, the node will be deleted from the circular singly linked list from the beginning.

Delete node at end position in Singly Circular list

If the list contains more than one element, then in order to delete the last element, we need to reach the last node. We also need to keep track of the second last node of the list. For this purpose, the two pointers ptr and preptr are defined. The following sequence of code is used for this purpose.



ptr = head;  

  while(ptr ->next != head)  

      {  



  ptr = ptr->next;  

       }

now, we need to make just one more pointer adjustment. We need to make the next pointer of preptr point to the next of ptr (i.e. head) and then make pointer ptr free. ptr->next = ptr -> next; free(ptr);

Doubly circular linked list

Structure of Doubly circular linked list
Procedure for node Insertion in Doubly circular linked list

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

Structure of Doubly circular linked list

// Structure of the node 

struct node 

{

 int data;

  struct node *next; // Pointer to next node 

  struct node *prev; // Pointer to previous node 

  };

Procedure for node Insertion in Doubly circular linked list

In the second scenario, the condition head == NULL becomes false. In this case, we need to make a few pointer adjustments at the end of the list. For this purpose, we need to reach the last node of the list through traversing the list. Traversing the list can be done by using the following statements.



temp = head;   

while(temp -> next != head)  

{  

    temp = temp -> next;   

    }

At the end of the loop, the pointer temp would point to the last node of the list. Since the node which is to be inserted will be the first node of the list therefore, temp must contain the address of the new node ptr into its next part. All the pointer adjustments can be done by using the following statements.

  
 
 temp -> next = ptr;  

  ptr -> prev = temp;  

    head -> prev = ptr;  

      ptr -> next = head;  

      head = ptr;