LinkedList in java



In this Collection framework tutorial we will learn what is java.util.LinkedList in Collection framework in java.


Contents of page :






1) What is hierarchy of LinkedList in java?
-java.lang.Object
-java.util.AbstractCollection
 -java.util.AbstractList
  -java.util.AbstractSequentialList<E>
   -java.util.LinkedList<E>


For more detailed hierarchy information read : List hierarchy in java


2) java.util.LinkedList
java.util.LinkedList is implemented using Doubly-linked list. It implements java.util.List and Deque interfaces.
A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence in java.


LinkedList extends AbstractSequentialList (abstract class), AbstractSequentialList extends AbstractList in java.


3) Creating java.util.LinkedList (using constructor)
creates empty linkedList.
List<String> linkedList=new LinkedList<String>();
Defining LinkedList<String> means list can be used to store only String types, storing any other type will cause compilation error.


4) Add element in java.util.LinkedList
add(E element)
Adds specified element to the end of LinkedList in java.
linkedList.add("ind");    

add(int index, E element)
Adds specified element in LinkedList at specified index.
Current element is placed at specified index and one is added to indices of subsequent elements on right in java.
linkedList.add(1, "ind");    

addFirst(E element)
Adds specified element at the beginning of LinkedList in java.
linkedList.addFirst("ind");    

addLast(E element)
Adds specified element to the end of LinkedList in java.
linkedList.addLast("ind");    


5) Remove element from java.util.LinkedList


remove()
Method retrieves and removes the first element (head) of this list in java.
   linkedList.remove();


remove(int index)
Removes the element at the specified index in list. And one is subtracted from indices of subsequent elements on left in java.
   linkedList.remove(1);


remove(Object object)
Removes first occurrence of specified object.
linkedList.remove("ind");

removeFirst()
Method removes and returns the first element from this list in java.
linkedList.addFirst("indF");    

removeLast()
Method removes and returns the last element from this list in java.
linkedList.addLast("indL");    

6) Get element from java.util.LinkedList
get(int index)
Method returns element on specified index.


linkedList.get(2);
Method returns element on 2nd index. If position does not exist then throws IndexOutOfBoundsException.


Important to note :
Get method iterates on nodes sequentially to get element on specified index. Hence, offering O(n) complexity.         


7) Size of java.util.LinkedList
size()
Method returns size of LinkedList in java.


System.out.println(linkedList.size());
will print size of linkedList in java.


8) Set element in java.util.LinkedList
set(int index, E element)
Method sets specified element at specified index in java.

9.1) Iterate over elements in java.util.LinkedList using iterator() in java
iterator() method returns iterator to iterate over elements in LinkedList.
Iterator important methods :
hasNext() method returns true if the iteration has more elements. (Traversing/Iteration is  done in forward direction) in java.
next() method - returns next element in iteration in java.
if the iteration has no more elements than NoSuchElementException is thrown.
remove() method - removes last element returned by iterator in java.
Method must always be called after call to next() method else IllegalStateException is thrown in java.


code-
    Iterator<String> iterator=linkedList.iterator();
   while(iterator.hasNext()){
          System.out.println(iterator.next());
   }


Iteration using enhanced for loop in java.
      for(String string:linkedList){
          System.out.println(string);
   }      


iterator returned by LinkedList is fail fast in java. Means any structural modification made to LinkedList like adding or removing elements during Iteration will throw java.util.ConcurrentModificationException.
Removing element by using iterator is allowed.
-set method does not cause structural modification, because size of list remains same.


code-
    Iterator<String> iterator=linkedList.iterator();
   while(iterator.hasNext()){
          System.out.println(iterator.next());
             linkedList.add("ind");    
   }
Element has been added during iteration which will cause ConcurrentModificationException to be thrown in java.

9.2) Iterate over elements in java.util.LinkedList using listIterator() in java
listIterator method returns listIterator to iterate over elements in LinkedList.
ListIterator important methods :
Apart from hasNext(), next() and remove() methods provided by Iterator, ListIterator additionally provides -
hasPrevious()  method returns true if this listIterator has more elements when traversing the list in the reverse direction in java.
previous()  returns previous element in iteration (traversing in backward direction).
if the iteration has no previous elements than NoSuchElementException is thrown in java.


nextIndex()  method returns the index of the element that would be returned by a subsequent call to next() method. If listIterator is at the end of the list than method returns size of list in java.


previousIndex()  method returns the index of the element that would be returned by a subsequent call to previous() method. If listIterator is at the start of the list than method returns -1 in java.


add(E element)
Method inserts the specified element into the list in java.
The element is inserted immediately before the element that would be returned by next (So, subsequent call to next would be unaffected), if any, and after the element that would be returned by previous (So,subsequent call to previous would return the new element), if any.
If the list does not contain any element than new element will be the sole element in the list.


set(E element)
Method replaces the last element returned by next() or previous() method with the specified element. This call can be made only if neither remove nor add have been called after the last call to next or previous.
If call to set() method is followed up by any call made to remove() or add() method after next() or previous() than UnsupportedOperationException is thrown.


ListIterator returned by LinkedList is also fail fast. Means any modification made to LinkedList during Iteration will throw ConcurrentModificationException in java.


ListIterator<String> listIterator=linkedList.listIterator();


9.3) Iterate over elements in list using enumeration in java
  Enumeration<String> listEnum=Collections.enumeration(linkedList);
   while(listEnum.hasMoreElements()){
      System.out.println(listEnum.nextElement());
   }
enumeration is also fail-fast.


10) Some other important methods of java.util.LinkedList in java
toArray() method converts and returns all elements of list in array. (Sequence of elements is maintained) in java


clear() method removes all elements from list in java.


11) synchronizing java.util.LinkedList in java
We can synchronize linkedList by using Collections’s class synchronizedList method.
List list = Collections.synchronizedList(linkedList);
Now, no 2 threads can access same instance of list concurrently in java.


12) Complexity of methods of LinkedList in java
Operation/ method
Worst case
Best case
add(E element)
O(1), Adds specified element to the end of LinkedList.
O(1), Adds specified element to the end of LinkedList.
add(int index, E element)
O(n), because iteration is done on all elements one by one to find out specified index.
Current element is placed at specified index and one is added to indices of subsequent elements on right.
O(n)
addFirst(E element)
O(1)
O(1)
addLast(E element)
O(1)
O(1)



remove()
O(1), Method retrieves and removes the first element (head) of this list.
O(1)
remove(int index)
O(n), because iteration is done on all elements one by one to find out specified index.
one is subtracted from indices of subsequent elements on right.
O(n)
remove(Object object)
O(n), because iteration is done on all elements one by one to find out specified object.
one is subtracted from indices of subsequent elements on right.
O(n)
removeFirst()
O(1)
O(1)
removeLast()
O(1)
O(1)
iterator
O(n), because ireation is done over each and every element.
O(n), because ireation is done over each and every element.
listIterator
O(n), its same as iterator.
O(n), its same as iterator.
enumeration
O(n), its same as iterator.
O(n), its same as iterator.

13) Features of java.util.LinkedList in java
  1. LinkedList  is implementation of the java.util.List interface in java


  1. Nodes : A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence in java.


  1. extends AbstractSequentialList - LinkedList extends AbstractSequentialList (abstract class), AbstractSequentialList extends AbstractList.
In LinkedList, data is accessed sequentially, so for obtaining data at specific index, iteration is done on nodes sequentially in java.


  1. Duplicate elements - LinkedList allows to store duplicate elements in java.


  1. Null elements -Null elements can be added in LinkedList in java.
  2. Insertion order - LinkedList maintains insertion order if all elements are added using add or addLast method because both method adds elements add element at end of LinkedList.
Example in java-
Let’s say we add 3 elements in linkedList
linkedList.add("ind");    
linkedList.add("aus");    
linkedList.add("sa");

On displaying insertion order will be maintained i.e.
ind
aus
sa

  1. synchronized - It is not synchronized (because 2 threads on same LinkedList object can access it at same time) in java.


  1. Performance - LinkedList is not synchronized, hence its operations are faster as compared to some other synchronized implementation of List interface in java.

14) When to use java.util.LinkedList in java
  1. LinkedList can be used when we want to store duplicate elements in java.


  1. We must prefer LinkedList for when add and remove operations are more as compared to get operations in java, and


  1. LinkedList can be used when we are not working in multithreading environment in java.

So in this Collection framework tutorial we learned what is java.util.LinkedList in Collection framework in java.

Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.


/** JavaMadeSoEasy.com */



RELATED LINKS>

Collection in java



ArrayList in java



HashSet in java

HashMap in java

ArrayList - add, add element at specific index methods program


eEdit
Must read for you :