Linked List | Types of Linked Lists (Java)

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. A linked list is a linear data structure where each element is a separate object.

Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

Advantages:

• Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
• Insertion and deletion node operations are easily implemented in a linked list.
• Linear data structures such as stacks and queues are easily executed with a linked list.
• They can reduce access time and may expand in real time without memory overhead.

Disadvantages:

• They have a tendency to use more memory due to pointers requiring extra storage space.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards[1] and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.

Types of Linked Lists:

1. Single linked list
2. Double linked list
3. Single Circular linked list
4. Double Circular linked list