Linked List in Java

LinkedList in java is linear data structures in which element are stored in the different locations and element that are stored in the different location of memory are called as node.

LinkedList Node are connected to each other using the pointers, Each element of the LinkedList has the reference address or pointer to the next element of the LinkedList.

public class LinkedList

    extends AbstractSequentialList

    implements List, Deque, Cloneable, java.io.Serializable

LinkedList in Java - techfloaters.blogspot.com

Features of LinkedList class

• LinkedList class implements List interface so it also contains duplicate element.
• LinkedList class can follow the insertion order.
• LinkedList class is not thread safe. It means LinkedList is not synchronized.

·         If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

·         A structural modification is any operation that adds or deletes one or more elements

      List list = Collections.synchronizedList(new LinkedList(...));

• In java LinkedList class node remove and add (manipulation) is fast because there is no need to shift element like ArrayList.
• The iterators returned by this class's iterator and listIterator methods are fail-fast.
• If the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. 

Time Complexity   of java LinkedList 

1] For Access element – 0(n)

A linked list can typically only be accessed via its head node. From there you can only traverse from node to node until you reach the node you seek. Thus access is O(n).

2] For search element – 0(n)

Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus search is O(n).

3] For Insertion element – 0(1)

Inserting into a linked list requires re-pointing the previous node (the node before the insertion point) to the inserted node, and pointing the newly-inserted node to the next node. Thus insertion is O(1).

4] For deletion element – 0(1)

Deleting from a linked list requires re-pointing the previous node (the node before the deleted node) to the next node (the node after the deleted node). Thus deletion is O(1).

Example of LinkedList

package com.vr.techfloaters;

import java.util.LinkedList;

public class LinkedListDemo {

     public static void main(String[] args) {

           // Creating object of class linked list

           LinkedList list = new LinkedList();

           // Adding elements to the linked list

           list.add("AA");

           list.add("BB");

           list.add(1, "EE");

           list.addLast("CC");

           list.addFirst("DD");

           list.add("FF");

           System.out.println("Linked list :" + list);

           // Finding elements in the linked list

           boolean isPresent = list.contains("BB");

           System.out.println("BB is present in in List:" + isPresent);

           // Removing elements from the linked list

           list.remove("BB");

           list.remove(2);

           list.removeFirst();

           list.removeLast();

           System.out.println("Linked list after element deletion: " + list);

           // size in the linked list

           int size = list.size();

           System.out.println("Size of linked list = " + size);

           // Get from LinkedList

           Object obj = list.get(1);

           System.out.println("Element returned by get() : " + obj);

           // set elements from LinkedList

           list.set(1, "AV");

           System.out.println("Linked list after change : " + list);

     }

}

Output

Linked list :[DD, AA, EE, BB, CC, FF]

BB is present in in List:true

Linked list after element deletion: [AA, CC]

Size of linked list = 2

Element returned by get() : CC

Linked list after change : [AA, AV]