Differentiate between singly linked list and doubly linked list. How do you insert and delete a node from doubly linked list? Explain.

Question

Suresh Chand · Accepted Answer

The difference between singly linked list and doubly linked list are Basis of comparison Singly linked list Doubly linked list Definition A single linked list is a list of nodes in which node has two parts, the first part is the data part, and the next part is the pointer pointing to the next node in the sequence of nodes. A doubly linked list is also a collection of nodes in which node has three fields, the first field is the pointer containing the address of the previous node, the second is the data field, and the third is the pointer containing the address of the next node. Access The singly linked list can be traversed only in the forward direction. The doubly linked list can be accessed in both directions. List pointer It requires only one list pointer variable, i.e., the head pointer pointing to the first node. It requires two list pointer variables, head and last. The head pointer points to the first node, and the last pointer points to the last node of the list. Memory space It utilizes less memory space. It utilizes more memory space. Efficiency It is less efficient as compared to a doubly-linked list. It is more efficient. Implementation It can be implemented on the stack. It can be implemented on stack, heap and binary tree. Complexity In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). In a doubly-linked list, the time complexity for inserting and deleting an element is O(1). Insert a node in doubly linked list: We have supposed that we want to insert a node at 3rd position. 1. Traverse to N-1 node in the list. Where N is the position to insert. Say temp now points to N-1th node. 2. Create a newNode that is to be inserted and assign some data to its data field. 3. Connect the next address field of newNode with the node pointed by next address field of temp node. 4. Connect the previous address field of newNode with the temp node 5. Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newNode. 6. Connect the next address field of temp node to newNode i.e. temp->next will now point to newNode. 7. Final list Delete a node in doubly linked list: Let us suppose that we want to delete node from 2nd position. 1. Traverse to Nth node of the linked list, lets say a pointer current points to Nth node in our case 2 node. 2. Link the node behind current node with the node ahead of current node, which means now the N-1th node will point to N+1th node of the list. Which can be implemented as current->prev->next = current->next. 3. 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. 4. Finally delete the current node from memory and you are done.

Differentiate between singly linked list and doubly linked list. How do you insert and delete a node from doubly linked list? Explain.

Leave your Answer:

Hits Counter

Question

Differentiate between singly linked list and doubly linked list. How do you insert and delete a node from doubly linked list? Explain.

Leave your Answer: