linkedlist

LinkedList is an implementation of the List interface. As with all the list interfaces, this collection maintains the insertion order.

The LinkedList also implements a Deque interface. So a LinkedList represents a Deque and a List.

As the names suggests, this collection arranges elements similar to a linked list data structure. In a linked list data structure, each element has a previous and next reference, similarly in LinkedList, each element in the list is represented by a Node Object as below.

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

So each element is represented by the field “item” in the Node object of LinkedList class and it is the single element in the collection, whereas the field “prev” and “next” point to the Node object of previous element and the next element in the collection. Hmm, lets look at a visual representation of a linked list for a clearer picture if you have forgotten a linked list. Actually it really is a double linked list.

so the above diagram is an example of linked list. Each element represent a node in the LinkedList. Apple being the first element in the list does not have a previous element linked to it. Every other element except the last element has previous and next element reference to navigate. The last element does not have any next element reference as it is the last element in the list.

So, how does the insertion work in case of linked list. So if I have to add an element to the list, a new “Node” object is created and the “prev” field is updated in the Node object to point to the last element in the list. So unlike an ArrayList a collection does not require a continuous allocation memory, it can create a node object anywhere and update its references.

So in the above diagram, we are adding “Peach” to the collection, so we just create new Node object and reference the last object in the “Prev” of the last element and the new element added becomes the last element in the collection. The LinkedList maintains the position of the first element and the last element the list.

A Deletion happens by traversing in the list and then updating the references of the prev element and the next element. Take a look at the representation below

So we have removed the element “Lemon” by removing its references from the Previous and its next element. The dotted line represent old references. So now when we traverse, the element Lemon will never come into the picture.

Traversal is linear in case of a linked list, we cannot jump with index to a particular position as we can do with an ArrayList. Although the api provides us a way to fetch by index, but the retrieval is linear so it might take o(n) complexity to fetch an element. So compared to an ArrayList, fetching by index is slow.

	Insert	Delete	Retrieval
Complexity	o(1)	o(n/4)	o(n/4)

Basic linked list example

        List<String> linkedList = new LinkedList<>();
        linkedList.add("apple");
        linkedList.add("orange");
        linkedList.add("peach");

Please refer below java doc location for detailed description of the api

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html