Linked List Implementation : In Simple Terms

Java Starter Kit #1

Overview

In Java POV, the collection framework gives us a wide range of data structures to choose from. Among them, one of the legacies yet widely used data structure is Linked List.

The major Pros of Linked List come into play when the data structures need to store a huge amount of values or when the length is not definite. This is the time when this implementation of collection shines. The insertion and deletion of elements from LL are faster than other data structures. 

Unlike array which again is a popular implementation of List interface in Java, LL doesn't store data in a continuous manner.

Some other pros include:

- Zero Memory Wastage: when an element is inserted or deleted, the allocation of memory is dynamic. When removed the previously-stored node reference is removed as hence GC clears it. And when inserted it allocates a new node when it is inserted and doesn't pre-occupy any space in the heap at the initialization of LL.

Linked List is a type of Queue implementation that also follows the FIFO principle when the interface used to declare is a Queue rather than a List. We will get all the functionality apart from add() (used to add an element to the LL), such as poll() (used to return the value of the top element as well as to remove it from the LL) and peek() (used to return the value of the top element, this doesn't remove the element from LL).

Working

Talking about the working of a simple Linked List, apart from the data to be stored in the list we also store the reference of the next data, or technically known as the reference of a node.

In Java terms, an object-like node is used to store an element  (data)  in LL. In the Node, there will be a (next) variable for storing the value and another variable for storing the instance of the next node.

When the LL is empty and one element is inserted, the Node will have data storing the element and the next as null. And the head will be storing this node.

When the LL is not empty, which means the head is present. The first thing we should keep in mind is that in LL the FIFO principle is followed and hence first we should transverse to the end of the LL and then add the new node with the data element.

Simple Implementation of Linked List in Java: Linked List

Keynotes

Some keynoted points of Linked List in Java:

• Linked List is an implementation of Java's Collection Framework implementing List and Deque.
• Internally LL implements doubly Linked List (which means the reference of the previous, as well as next node, is stored).
• As it's implementing List, it allows null values and also duplicate values.
• In LL insertion order is maintained.
• LL is not thread-safe, can be synchronized using collections methods like Collection.synchronizedList().

Cons of Linked List

While talking so much about LL, it has some setbacks too.

One major concern is the additional memory that the reference to the next node takes. And this is more in the case of Doubly Linked List.

Traversal of nodes and fetching a random element is also an expensive operation.

Official documentation of Linked List: Oracle Linked List

**Glossary

• LL - Linked List
• FIFO - First In First Out
• GC - Garbage Collection