Singly Linked List vs Doubly Linked List
Linked list is a linear data structure that is used to store a collection of data. A linked list allocates memory to its elements separately in its own block of memory and the overall structure is obtained by linking these elements as links in a chain. A singly linked list is made up of a sequence of nodes and each node has a reference to the next node in the sequence. A doubly linked list contains a sequence of nodes in which each node contains a reference to the next node as well as to the previous node.
Singly Linked List
Each element in a singly linked list has two fields as shown in Figure 1. The data field holds the actual data stored and the next field holds the reference to the next element in the chain. The first element of the linked list is stored as the head of the linked list.
Figure 2 depicts a singly linked list with three elements. Each element stores its data and all elements except the last one store a reference to the next element. Last element holds a null value in its next field. Any element in the list can be accessed by starting at the head and following the next pointer until you meet the required element.
Doubly Linked List
Each element in a doubly linked list has three fields as shown in Figure 3. Similar to singly linked list, the data field holds the actual data stored and the next field holds the reference to the next element in the chain. Additionally, the previous field holds the reference to the previous element in the chain. The first element of the linked list is stored as the head of the linked list.
Figure 4 depicts a doubly linked list with three elements. All the intermediate elements store references to the first and previous elements. Last element in the list holds a null value in its next field and the first element in the list holds a null value in its previous field. Doubly linked list can be traversed forward by following the next references in each element and similarly can be traversed backwards using the previous references in each element.
What is the difference between Singly Linked List and Doubly Linked List?
Each element in the singly linked list contains a reference to the next element in the list, while each element in the doubly linked list contains references to the next element as well as the previous element in the list. Doubly linked lists require more space for each element in the list and elementary operations such as insertion and deletion is more complex since they have to deal with two references. But doubly link lists allow easier manipulation since it allows traversing the list in forward and backward directions.