In Java Collections framework there are two general purpose implementations of the List interface-

__ArrayList__- LinkedList

- To read more about
**how ArrayList works internally**in Java refer this post-__How ArrayList works internally in Java__

In this post I'll talk about LinkedList internal implementation in Java Collections framework.

**Note**- Code of LinkedList class used here for reference is from Java 10.

**Table of contents**

- Internal implementation of LinkedList class in Java
- Graphical representation of Java LinkedList with nodes
- Java LinkedList internal implementation - linkFirst() method
- Java LinkedList internal implementation - linkLast() method
- Java LinkedList internal implementation - add(int index, E element) method

### Internal implementation of LinkedList class in Java

LinkedList class in Java implements **List and Deque interfaces** and LinkedList implements it using **doubly linkedlist**.

In the implementation of the LinkedList class in Java there is a **private class Node** which provides the structure for a node
in a doubly linked list. It has item variable for holding the value and two reference to Node class itself for
connecting to next and previous nodes.

__The Node class from Linked List implementation__

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

### Graphical representation of Java LinkedList with nodes

Here is a graphical representation of a linked list to help you better visualize how actually a node will look like and
how it connects with other nodes through next and prev references.

Since reference is stored for both next and previous nodes that is why it is a **doubly linked list
implementation**.

Though there are many methods with in the LinkedList class but here I'll try to explain the internal working of the LinkedList, how references are created and shuffled using these 3 methods-

- private void linkFirst(E e)
- void linkLast(E e)
- public void add(int index, E element)

### Java LinkedList internal implementation - linkFirst() method

linkFirst() method is used to add an element at the beginning of the list and it is implemented as follows in the LinkedList class

/** * Links e as first element. */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }

Here one more important thing to mention is first and last Node class references which always refer to the first and last element of the linked list.

/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first;

/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;

With this info it is easy to see that in the **linkFirst method**, when the very **first element** is inserted into
the list *first and last both refer to this new node*.

**f**will hold the reference to the node which was the

*first element before this insertion*.

**first**will be assigned the reference to the newly created node (

**first = newNode;**). The element which was the first element before this insertion is at second position now so its

*prev element should store reference of the first node*, that's what is happening here

**f.prev = newNode**;

And in the call to the **constructor of the node class** f is sent as a parameter. If you see in the Node
class constructor there is a line **this.next = next;** that's how the newly created node is storing the reference
to the second node.

### Java LinkedList internal implementation - linkLast() method

linkLast() method is used to *insert element as the last element of the list*. In that case the node which
is *currently the last node of the linked list will become the second last node*. So the newly created
node's prev should store the reference to this second last node and the next of the second last node should
store the reference to the node which is the last node now.

/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

Here it is first checking if it is the **very first element** which is inserted in that case both first and
last references point to it. If elements are already there in the linked list then the node which is currently
the last node of the linked list will become the second last node now.

See the call to the **constructor of the Node class** (**this.prev = prev;**). So the newly created node's prev should store the reference to this second last node and the next of the second last node should store the
reference to the node which is the last node now (**l.next = newNode;**).

### Java LinkedList internal implementation - add(int index, E element) method

**add(int index, E element)** is used to Insert the specified element at the specified position in this list.

public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

Here it calls linkBefore method

void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

And **node(index)** parameter with in the **linkBefore()** method is call to the following method to get the
existing Node at the given index-

/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

I am leaving it to you readers to figure out how **linkBefore()** method is working. It should be easy based on
the explanation already provided for linkFirst() and linkLast() method.

That's all for this topic ** How LinkedList Class Works Internally in Java**. If you have any doubt or any suggestions to make please drop a comment. Thanks!

__Related Topics__

**You may also like- **

awesome explanation, after learning your description for linkFirst() and linkLast() method, I could easily understand linkBefore() method.

ReplyDeletewhat is node(index)

ReplyDeletein add(int index, E element) method

node is actually another method which is used to get the Node at the passed index. I have updated it with in the post too so you can have a look.

DeleteHI there , greate explanation with the detailed internals thank you so much

ReplyDelete