LinkedList

LinkedList Java Example (with video)

In this article, we will use examples in order to understand Linked lists in Java. The Java LinkedList class can be considered as an alternative to ArrayList class. It uses a doubly linked list to store the elements in a Java program. It inherits the AbstractList class and implements List and Deque interfaces.

Also, the LinkedList allows the usage of iterators, so that you can iterate the list forwards or backwards and declare the exact position of the starting node.

You can also check this tutorial in the following video:

Java LinkedList Tutorial – video

You can see the relations between LinkedList and other classes in the following diagram:

LinkedList Java - diagram
LinkedList diagram

1. How a LinkedList works?

Internally LinkedList class in Java uses objects of type Node to store the added elements. Node is implemented as a static class within 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.

What does a doubly-linked list mean?

It means each node stores reference to the next as well as previous nodes.

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

1.1 LinkedList class declaration

Let’s see the declaration for java.util.LinkedList class.

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable

1.2 Constructors of Java LinkedList

Constructor Description
LinkedList() It is used to construct an empty list.
LinkedList(Collection<? extends E> c) It is used to construct a list containing the elements of the specified collection, in the order, they are returned by the collection’s iterator.

1.3 Methods of Java LinkedList

Method Description
boolean add(E e)It is used to append the specified element to the end of a list.
void add(int index, E element)It is used to insert the specified element at the specified position index in a list.
boolean addAll(Collection<? extends E> c)It is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.
boolean addAll(Collection<? extends E> c)It is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator.
boolean addAll(int index, Collection<? extends E> c)It is used to append all the elements in the specified collection, starting at the specified position of the list.
void addFirst(E e)It is used to insert the given element at the beginning of a list.
void addLast(E e)It is used to append the given element to the end of a list.
void clear()It is used to remove all the elements from a list.
Object clone()It is used to return a shallow copy of an ArrayList.
boolean contains(Object o)It is used to return true if a list contains a specified element.
Iterator<E> descendingIterator()It is used to return an iterator over the elements in a deque in reverse sequential order.
E element()It is used to retrieve the first element of a list.
E get(int index)It is used to return the element at the specified position in a list.
E getFirst()It is used to return the first element in a list.
E getLast()It is used to return the last element in a list.
int indexOf(Object o)It is used to return the index in a list of the first occurrence of the specified element, or -1 if the list does not contain any element.
int lastIndexOf(Object o)It is used to return the index in a list of the last occurrence of the specified element, or -1 if the list does not contain any element.
ListIterator<E> listIterator(int index)It is used to return a list-iterator of the elements in proper sequence, starting at the specified position in the list.
boolean offer(E e)It adds the specified element as the last element of a list.
boolean offerFirst(E e)It inserts the specified element at the front of a list.
boolean offerLast(E e)It inserts the specified element at the end of a list.
E peek()It retrieves the first element of a list
E peekFirst()It retrieves the first element of a list or returns null if a list is empty.
E peekLast()It retrieves the last element of a list or returns null if a list is empty.
E poll()It retrieves and removes the first element of a list.
E pollFirst()It retrieves and removes the first element of a list, or returns null if a list is empty.
E pollLast()It retrieves and removes the last element of a list, or returns null if a list is empty.
E pop()It pops an element from the stack represented by a list.
void push(E e)It pushes an element onto the stack represented by a list.
E remove()It is used to retrieve and removes the first element of a list.
E remove(int index)It is used to remove the element at the specified position in a list.
boolean remove(Object o)It is used to remove the first occurrence of the specified element in a list.
E removeFirst()It removes and returns the first element from a list.
boolean removeFirstOccurrence(Object o)It is used to remove the first occurrence of the specified element in a list (when traversing the list from head to tail).
E removeLast()It removes and returns the last element from a list.
boolean removeLastOccurrence(Object o)It removes the last occurrence of the specified element in a list (when traversing the list from head to tail).
E set(int index, E element)It replaces the element at the specified position in a list with the specified element.
Object[] toArray()It is used to return an array containing all the elements in a list in proper sequence (from first to the last element).
<T> T[] toArray(T[] a)It returns an array containing all the elements in the proper sequence (from first to the last element); the runtime type of the returned array is that of the specified array.
int size()It is used to return the number of elements in a list.

1.4 First and Last variables

first and last variables are for holding the reference of the first and last nodes of the linked list:

first and last nodes:

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

1.5 Adding elements in LinkedList

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).

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). 

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

1.6 moving elements from Linkedlist

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.

LinkedList Java - Removing a node
Removing a node

1.7 Getting a specific node

In the case of get() method again there are getFirst() and getLast() method too. In case of get() method it has to get the node for the passed index and return the node.item.

implementation of get() method

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

2. Example of a Java LinkedList

LinkedListExample.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.javacodegeeks.corejava.linkedlist;
 
import java.util.LinkedList;
import java.util.ListIterator;
 
public class LinkedListExample {
 
    public static void main(String args[]) {
        // create a linked list
        LinkedList list = new LinkedList();
 
        // add elements to the linked list
        list.add("One");
        list.add("Two");
        list.add("Three");
        list.add("Four");
        list.add("Five");
 
        // create a list iterator
        ListIterator lit = list.listIterator();
        System.out.println("Initial list: ");
 
        while (lit.hasNext()) {
            System.out.println(lit.next() + " ");
        }
 
        // add elements in the beginning and in the end of the list
        list.addFirst("Zero");
        list.addLast("Six");
 
        System.out
                .println("Updated List after insertion in the first and last position: ");
        lit = list.listIterator();
        while (lit.hasNext()) {
            System.out.println(lit.next() + " ");
        }
 
        System.out.println("Check if list contains the element Four: "
                + list.contains("Four"));
 
        System.out.println("The position of the element \"One\" is: "
                + list.indexOf("One"));
 
        System.out.println("Get the element in third position of the list: "
                + list.get(2));
 
        int size = list.size();
        System.out.println("The size of list is: " + size);
 
        System.out.println("Iterate List in reverse order: ");
        lit = list.listIterator(size);
        while (lit.hasPrevious()) {
            System.out.println(lit.previous() + " ");
        }
        // remove elements from the linked list
        list.remove("Three");
        list.removeFirst();
        list.removeLast();
        System.out
                .println("Updated List after deletion of the first element, the last element and the element \"Three\": ");
        lit = list.listIterator();
        while (lit.hasNext()) {
            System.out.println(lit.next() + " ");
        }
 
    }
 
}

Let’s explain the above code. First, we create a linked list of strings and we add items in it. Then, we create a list iterator that will iterate the elements in the list, starting from the beginning. After that, we insert again two elements but in the beginning and in the end of the list, respectively.

As you can see we have used some already known methods from the List class. For example, we use contains method to examine whether a specific element is included in the list, then we use the indexOf method so as to find the position of a specific item, finally, we use the size method so as to retrieve the size of the list. Then, we use again the iterator of the list but at this time, we define the exact position of the starting node of the iteration. In particular, we start from the end of the list, so as to iterate the list in reverse order. Then, we delete a specified element in the list and after that, we delete the first and the last item in the list. Finally, we iterate once again the list so as to depict the final version of the list.

If we run the above code, we will have the following results:

Output:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Initial list:
One
Two
Three
Four
Five
Updated List after insertion in the first and last position:
Zero
One
Two
Three
Four
Five
Six
Check if list contains the element Four: true
The position of the element "One" is: 1
Get the element in third position of the list: Two
The size of list is: 7
Iterate List in reverse order:
Six
Five
Four
Three
Two
One
Zero
Updated List after deletion of the first element, the last element and the element "Three":
One
Two
Four
Five

4. Download the source code

This was an example of how to use the class LinkedList.

Download
You can download the Eclipse project of this tutorial here: LinkedList Java Example

Last updated on Apr. 27th, 2021

Firouzeh hejazi

A self-motivated and hard-working developer with more than 4 years of extensive experience in developing software in java platforms. A multi-skilled and problem-solving engineer who has participated in implementing a range of applications in different roles. Possess a MSc in Knowledge Engineering and Decision Science.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button