Thursday, September 3, 2015

LinkedList in Java- Implementation, difference with array list, pros cons and example with time complexity

Linked list in Java


Another powerful weapon in Java's Collection API is LinkedList which is Doubly-linked list implementation of the List and Deque interfaces.

There are N number of Collection containers in the whole framework (List, Map, Etc ...), but choosing the right container for your data is the toughest job than operating it.


Here are the reason's to choose LinkedList over other containers 


1) When you want to add or remove the elements from the container over the time. This is the case when you don't exactly know the number of elements before in hand. You can choose ArrayList also as it also accepts the no of elements overtime but you don't see the performance differences under the hood.

2) If you are sure that you are not going to access the elements with Random index which costs O(n) [read big O notation to understand what is O(n)]. That means you are getting the elements only in sequential order all the time.

3) When you want overtime iterations, Linked lists are really cheap to do that.



LinkedList implementation type 


Java used doubly linked list implementation where the consumer have a choice to move and backward direction. If it is Singly linked list implementation you cannot have a choice of iterate over the list is reverse. 

In Doubly Linked list implementation each Node of data consists the information of it's next and previous Nodes. If you remove any Node in between, the previous and next will gets updates as required. Look at source of Linked List implementation.



Example to LinkedList 


public static void main(String args[]) {  
      List<String> linkedlist = new LinkedList<String>(); 
      //adding elements to LinkedList 
      linkedlist.add("string1");  
      linkedlist.add("string2");  
      linkedlist.add("string3");  
      //Adding First and Last Elements  in LinkedList
      linkedlist.addFirst("FirstString");  
      linkedlist.addLast("LastString"); 
      //This is how to get with index  
      linkedlist.get(1);  
      //This is how to set with index  in LinkedList
      linkedlist.set(1, "NewFirstString");  
      // Removing first and last elements from LinkedList  
      linkedlist.removeFirst();  
      linkedlist.removeLast();  
     // Removing elements from LinkedList with index  
      linkedlist.remove(2);  
    }

Pro's of LinkedList


LinkedList class can contain duplicate elements.
Java LinkedList class maintains insertion order.
Java LinkedList class is non synchronized.
In Java LinkedList class, manipulation is fast because no shifting needs to be occurred.
ava LinkedList class can be used as list, stack or queue.


Con's of LinkedList:


LinkedList cannot be accessed Randomly
Extra storage space for a pointer is required in case of linked lists
Reverse Traversing is difficult (If singly LinkedList)
Access time for Individual Element is O(n) whereas in Array it is O(1).



Post a Comment