3 Types of Linked List in Data Structure, pros and cons

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

  1. Singly Linked List
  2. Doubly Linked List
  3. 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.

Types of Linked List in Data Structure, Singly Linked List

A node is designed as

A Linked List is implemented in Java like this

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.

Doubly Linked List

A node is represented as

Advantages over Singly Linked List
  1. A Doublely Linked List can be traversed in both forward and backward direction.
  2. The delete operation in Doublely Linked List is more efficient if pointer to the node to be deleted is given.
  3. You can quickly insert a new node before a given node.
  4. 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
  1. 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.
  2. 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.

Circular Linked List,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
  1. 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.
  2. 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.
  3. 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.
  4. 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

Please share it if you found this useful
Hide Buttons