What are the Types of Linked Lists in Data Structure?

Linked List is a linear data structure that consists of nodes. Each node in the linked list has both "data" and "links" i.e pointers of the next or previous nodes or both. These nodes are connected to the adjacent nodes using links or pointers.

The nodes in the linked lists need not be stored at contiguous memory locations. This article mainly explains all types of linked lists data structures and also explains the applications and representation of each linked list.

So, the different types of linked lists in data structures are:

1. Singly linked list
2. Doubly linked list
3. Circular linked list
4. Doubly circular linked list

Every type of linked list has its properties and is different from another linked list in both its representation and implementation part. The below article explains all types of linked lists in detail.

Singly Linked List

• The first and most simple type of linked list is a singly linked list. The singly-linked list consists of nodes.
• Each node of the singly linked list consists of a data value and a pointer to the next node.
• The first node of the singly linked list is called as head of the linked list.
• The last node of the singly linked list is called the tail of the linked list and it points to null, which indicates the end of the linked list.
• A singly linked list is traversed only in one direction i.e, only unidirectional traversal is possible in the singly linked list which is from the head to the last node or the tail.

The below image clearly explains what the singly linked list looks like:

In the above image, next represents the pointer to the next node.

Representation of singly linked list in C++, Python, and java is as follows:

C++ representation: of a singly linked list.

Output:

Python representation: of the singly linked list.

Output:

Java representation: of singly linked list.

Output:

The singly linked list formed by assigning values to the nodes are:

Applications of a Singly Linked List are as follows:

• Singly-linked lists are used for the implementation of stacks and queues.
• Singly-linked lists are also used for preventing data collision in hash maps.

Doubly Linked List

• Doubly linked lists are very similar to singly linked lists but have an extra pointer that points to the previous node.
• Every node in the doubly linked list has three parts i.e, data of the node, a pointer (link) to the next node which has the address of the next node, and the third part is another pointer (link) to the previous node which has the address of the previous node.
• The first node in the doubly linked list is called the head node and the last node is called the tail node. The first node's previous pointer points to the null value and the last node's next pointer point to the null value.
• A doubly linked list is a bi-directional linked list i.e, you can traverse either from head to tail or tail to head. Here pointer to the next node is generally called next and the information to the previous node is called prev.

The representation of doubly linked lists is clearly shown in the below image:

Representation of doubly linked list in C++, Python, and Java is as follows:

C++ representation: of a doubly linked list.

Output:

Python representation: of a doubly linked list.

Output:

Java representation: of a doubly linked list.

Output:

An example of a doubly linked list having four nodes is shown in the below figure:

Applications of the Doubly Linked Lists:

• Doubly linked lists are used by the internet browser to implement backward and forward navigation of visited web pages using a backward and forward arrow button.
• The doubly linked list is also used by various applications where it involves undo and redo functionalities.

Circular Linked List

The next type of linked list in data structures is a circular linked list. When the last node of a singly linked list points to its first node, we get a circular linked list. Here pointer to the next node is generally called next. The first node in the circular linked list is called the head node.

A circular linked list can be traversed in only one direction so it is a unidirectional linked list.

The below image clearly explains the representation of the circular linked list:

Representation of circular linked list in C++, Python, and Java is as follows:

C++ representation: of a circular linked list.

Output:

Python representation: of circular linked list.

Output:

Java representation: of a circular linked list is created using classes and creating its objects by passing the node's data value.

Output:

In the implementation of the circular linked list, we need to make the last node's next pointer point to the first node i.e, the head node.

An example of a circular linked list having four nodes is shown in the below figure:

Applications of Circular Linked List:

• For example, consider you are working on a windows manager that allows users to cycle through windows by pressing Cmd+Tab, this is an application of circular linked list.
• Circular linked lists can also be used to implement queues by using only one pointer to the last inserted node, whereas in the singly linked list, we use two pointers.

Doubly Circular Linked List

The last type of linked list in data structures is a doubly circular linked list. As the name suggests it is the combination of both a circular linked list and a doubly linked list. Same as in the doubly linked list each node has three parts. One part is for data, the second part is for storing the address of the next node and the last part is for storing the address of the previous node. The first node in the linked list is called the head node.

Another specialty of a doubly circular linked list is that same as in a circular linked list, the doubly circular linked list's last node points to the head of the linked list. Here pointer to the next node is generally called next and the information to the previous node is called prev. A doubly circular linked list can be traversed in both directions and is hence called a bi-directional linked list.

The below image clearly explains the representation of a doubly circular linked list:

Representation of a doubly circular linked list in C++, Python, and Java are as follows:

C++ representation: of a doubly circular linked list is created using classes and creating its objects by passing the node's data value.

Output:

Python representation: of a doubly circular linked list is created using classes and creating its objects by passing the node's data value.

Output:

Java representation: of a doubly circular linked list is created using classes and creating its objects by passing the node's data value.

Output:

In the implementation of a doubly circular linked list, we need to make the last node's next pointer point to the first node's prev pointer.

An example of a doubly circular linked list having four nodes is shown in the below figure:

Applications of Doubly Circular Linked List:

• Popular real-life example of a doubly linked list in music players, apps like Spotify, and Gaana uses doubly linked lists to keep track of previous and next songs in the music album.
• Another application of a doubly circular linked list is managing the shopping cart on online websites.