In the post ArrayList Internal Implementation in Java we have already seen the internal implementation details of one of the implementation of the List interface – **ArrayList**. In this post we’ll see **LinkedList internal implementation in Java** which is another implementation of the List interface

Questions that may come up for How LinkedList works internally in Java are as follows-

- How does LinkedList class store its element.
- Is LinkedList class in Java implemented as a singly linked list or a doubly linked list.
- What happens when element is added to the LinkedList. Since it is a LinkedList so what is the implementation for adding element at the first position or at the last.
- How does remove() method works in LinkedList.
- How does get() method work in LinkedList.

In this post let’s try to answer these questions by looking into the internal implementation of LinkedList in Java.

### How does LinkedList class store its element

Internally LinkedList class in Java uses objects of type **Node** to store the added elements. Node is
implemented as a static class with in the LinkedList class. Since *LinkedList class is implemented as a doubly
linked list* so each node stores reference to the next as well as previous nodes along with the added element.

**Node class code in JDK 10**

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; } }

### Is it a doubly linked list

As already shown Java LinkedList class is implemented as a doubly linked list and each node stores reference to the next as well as previous nodes.

### How add() method works in a LinkedList

Since it is a linked list so apart from regular `add()`

method to add sequentially there are
`addFirst()`

and `addLast()`

methods also in Java LinkedList class.

There are also separate variables for holding the reference of the first and last nodes of the linked list.

/** * Pointer to first node. */ transient Node<E> first; /** * Pointer to last node. */ transient Node<E> last;

If you call the regular add() method or addLast() method, internally linkLast() method is called. In this method a new node is created to store the added element and the variable last starts referring to this node (as this new node becomes the last node). There is also a check to see if it is the very first insertion in that case this node is the first node too.

**linkLast() method implementation in the LinkedList class**

/** * 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++; }

If you call **addFirst()** method internally **linkFirst()** method is called. In this
method a new node is created to store the added element and the variable first starts referring to this node
(as this new node becomes the first node). There is also a check to see if it is the very first insertion in
that case this node is the last node too. If it is not the first node then the previous "first" node now comes
at the second position so its prev reference has to refer to the new node.

**LinkFirst() method implementation 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++; }

There is also an add() method to add element at a specific index. If that method is called then the already existing element at the passed index has to be shifted right.

### How remove() method works in Java LinkedList class

Just like add() method for removing an element from the LinkedList apart from regular `remove()`

method (where index or the element is passed) there are also `removeFirst()`

and `removeLast()`

methods.

When remove() method is called then the reference of the nodes at the left and right of the removed nodes have to be changed so that next of the node at left starts referring to the node at the right and the prev of the node at right starts referring to the node at the left of the node to be removed.

Following image will help you understand what actually is needed to be done. Here middle node has to be removed.

### How get() method works in Java LinkedList class

In the case of `get()`

method again there are `getFirst()`

and `getLast()`

methods too. In case of get() method it has to get the node for the passed index and return the node.item.

public E get(int index) { checkElementIndex(index); return node(index).item; }

In case of getFirst() and getLast() reference is also stored in the first and last variables so just need to return the value first.item or last.item.

That's all for the topic **LinkedList Internal Implementation in Java**. If something is missing or you
have something to share about the topic please write a comment.

**You may also like**

## No comments:

## Post a Comment