This post shows you all types of Linked List in Data Structure. What are types of Linked List? How to implement those in Java language? What is the advantages and disadvantages of those?
Types of Linked List in Data Structure
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Singly Linked List
It is the most common of types of Linked List in Data Structure. Each node has data and a pointer to the next node.
A node is designed as
|
1 2 3 4 5 6 7 8 9 10 11 |
/* Linked list Node*/ class Node { int data; // data item Node next; //Next is by default initialized as null // Constructor to create a new node Node(int d) { data = d; next = null; } } |
A Linked List is implemented in Java like this
|
1 2 3 4 5 6 7 8 9 10 11 |
/* Linked list Node*/ class Node { int data; // data item Node next; //Next is by default initialized as null // Constructor to create a new node Node(int d) { data = d; next = null; } } |
If you want to implement simple program for linkedlist, see the post Linked List Data Structure in Java
Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list. Thus, we can go in either direction: forward or backward.
A node is represented as
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Class for Doubly Linked List public class DoubleLinkedList { Node head; // head element /* DLL Node*/ class Node { int data; Node prev; Node next; // Constructor, and next and prev is by default initialized as null Node(int d) { data = d; } } } |
Advantages over Singly Linked List
- A Doublely Linked List can be traversed in both forward and backward direction.
- The delete operation in Doublely Linked List is more efficient if pointer to the node to be deleted is given.
- You can quickly insert a new node before a given node.
- In Singly Linked List, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In Doublely Linked List, we can get the previous node using previous pointer.
Disadvantages over Singly Linked List
- Every node of Doublely Linked List require extra space for an previous pointer. Although, It is possible to implement Doublely Linked List with single pointer.
- All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers.
Circular Linked List
Circular linked list is a variation of linked list where all nodes are connected to form a circle. There is no NULL at the end. It is a popular list of types of Linked List in Data Structure.
A Circular linked list can be either singly linked or doubly linked.
- If a singly linked list, next pointer of last item points to the first item.
- If a doubly linked list, prev pointer of first item points to last item as well.
Advantages of Circular Linked Lists
- Any node can be a starting point. You can traverse the whole list by starting from any point and stop when the first visited node is visited again.
- Circular linked list is useful for the implementation of queue. You just maintain a pointer to the last inserted node and front can always be obtained as next of last. Unlike the implementation of normal queue, you must maintain two pointers for front and rear.
- Circular Linked List is useful in applications to repeatedly go around the list. For example, it is popular for the operating system to put the running applications on a list and then to cycle through them, setting each of them a slice of time to execute, and then making them wait while the CPU is given to another application.
- Circular Doubly Linked List is used for the implementation of advanced data structures like Fibonacci Heap.
That’s all about Types of Linked List in Data Structure.
References
Linked List Data Structure in Java
Data Structures and Algorithms Tutorial in Java
