What is the Difference Between Single Linked List and Double Linked List

The main difference between Single Linked List and Double Linked List is that a node in the single linked list stores the address of the next node while a node in a double linked list stores the address of the next node and the previous node.

An array is a data structure that stores a group of elements of the same data type. One major drawback of an array is that it is pre-defined or has a fixed length. A Linked List provides a solution to this issue as it allows storing data dynamically. Therefore, it is possible to add elements at runtime. In other words, a Linked List allows allocating memory for the elements when required. There are various types of linked lists, and single linked list and double linked list are two of them.  In brief, a single linked list allows traversing to one direction while a double linked list allows traversing to both directions through the elements.

Key Areas Covered

1. What is Single Linked List
     – Definition, Functionality
2. What is Double Linked List
     – Definition, Functionality
3. What is the Difference Between Single Linked List and Double Linked List
     – Comparison of Key Differences

Key Terms

Single Linked List, Double Linked List

What is Single Linked List

A linked list is a linear data structure that consists of a group of nodes in a sequence. A node or an element consists of data and the address of another node. A single linked list is a type of linked list.

A single linked list stores the data and the address of the next node in the sequence. As the nodes stores the address of the next node, the nodes are referring to each other. Therefore, it forms a structure similar to a chain. It is possible to perform operations such as inserting, deleting and traversing through the elements in a single linked list.

What is Double Linked List

Similar to a single linked list, a double linked list is also a type of linked list. It is also called a doubly linked list. It stores data and two addresses. These addresses are the address of the next node and the address of the previous node. As there are two references, it is possible to go forward and backward through elements in the double linked list. Furthermore, the programmer can perform operations such as inserting elements and deleting elements in a double linked list.

In addition to these two types, there is another linked list as a circular linked list. In this kind of list, the last node stores the address of the first node. Therefore, it forms a structure similar to a circular chain.

Difference Between Single Linked List and Double Linked List

Definition

A single linked list is a linked list that contains nodes which have a data field and a next field which points to the next node in the line of nodes. A double linked list, in contrast, is a linked list that contains the data field, next field that points to the next node and a previous field that points to the previous node in the sequence. Thus, this is the main difference between Single Linked List and Double Linked List.

Direction

Moreover, a single linked list allows traversing in one direction through the elements while a double linked list allows traversing in both directions (backward and forward).

Memory Requirement

Memory requirement is another difference between Single Linked List and Double Linked List. A single linked list requires less memory as it stores only one address while a double linked list requires more memory as it stores two address.

Insertion and Deletion

The complexity of insertion and deletion at a known position in a single linked list is O(n). The complexity of insertion and deletion at a known position in a double linked list is O(1). Hence, this is another difference between Single Linked List and Double Linked List.

Conclusion

A linked list is a linear data structure that consists of a group of nodes in a sequence. It stores elements in noncontiguous memory locations at runtime. Single and double linked list are two types of linked lists. The main difference between Single Linked List and Double Linked List is that a node in the single linked list stores the address of the next node while a node in a double linked list stores the address of the next node and the previous node.

Reference:

1. “Introduction to Linked Lists.” Types of Network Topology in Computer Networks | Studytonight,  Available here.

Image Courtesy:

1. “CPT-LinkedLists-addingnode” By Singly_linked_list_insert_after.png: Derrick Coetzeederivative work: Pluke (talk) – Singly_linked_list_insert_after.png (Public Domain) via Commons Wikimedia
2. “Doubly-linked-list” By Lasindi – Own work (Public Domain) via Commons Wikimedia