LinkedList class example in java

LinkedList is the Linked list implementation of the List interface. This class Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).

All of the stack/queue/deque operations could be easily recast in terms of the standard list operations. They’re included here primarily for convenience, though they may run slightly faster than the equivalent List operations.

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

There are two constructors in LinkedList class

LinkedList()

Constructs an empty list.

LinkedList(Collection c)

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.

When to use LinkedList class

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

get is O(n)

add is O(1)

remove is O(n)

Iterator.remove is O(1)

LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.

The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens – The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:

Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantaneous. Change two links, and you have a new value anywhere you want it.

No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.

LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes

Example of LinkedList

The below is the example code of LinkedList class.

package com.java.connect.collection;
 
import java.util.LinkedList;
 
public class LinkedListExample {
    public static void main(String[] args) {
        // Create an object of linked list
        LinkedList<string> linkedList = new LinkedList<string>();
        // Add elements to the linked list one by one
        linkedList.add("TEST1");
        linkedList.add("TEST2");
        linkedList.add("TEST3");
        linkedList.add("TEST4");
        linkedList.add("TEST5");
        linkedList.add("TEST6");
        linkedList.add("TEST7");
        linkedList.addLast("LAST");
        // ADD the element in first node
        linkedList.addFirst("FIRST");
        // ADD the element in last node
        linkedList.add(1, "NUMBER1");
 
        System.out.println("Original contents of linkedList : " + linkedList);
        // Itreate all the element one by one
        for (String string : linkedList) {
            System.out.println("The element is " + string);
        }
        // remove elements from the linked list
        linkedList.remove("TEST4");
        linkedList.remove(2);
        System.out.println("Contents of linkedList after deletion: " + linkedList);
        // remove first and last elements
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println("linkedList after deleting first and last: " + linkedList);
        // get and set a value
        String value = linkedList.get(2);
        linkedList.set(2, value + " Has been updated");
        System.out.println("linkedList after update: " + linkedList);
    }
}

The output of the above code will be as:

Original contents of linkedList : [FIRST, NUMBER1, TEST1, TEST2, TEST3, TEST4, TEST5, TEST6, TEST7, LAST]
The element is FIRST
The element is NUMBER1
The element is TEST1
The element is TEST2
The element is TEST3
The element is TEST4
The element is TEST5
The element is TEST6
The element is TEST7
The element is LAST
Contents of linkedList after deletion: [FIRST, NUMBER1, TEST2, TEST3, TEST5, TEST6, TEST7, LAST]
linkedList after deleting first and last: [NUMBER1, TEST2, TEST3, TEST5, TEST6, TEST7]
linkedList after update: [NUMBER1, TEST2, TEST3 Has been updated, TEST5, TEST6, TEST7]