LinkedList in java

Introduction

LinkedList also implements List. But unlike its brothers like ArrayList and Vector, it doesn't use arrays as their underlying implementation. In a LinkedList each element has a pointer to the element before it and to the element following it. Because of this LinkedLists and ArrayLists will perform differently from processing time and memory usage standpoints. So it gives kind of sequential access and not random access. See the post – difference between iterator and index access for more.

I am not going to get into all the differences in performance here except to say a LinkedList can add elements very quickly to its beginning or middle, and there is no capacity to manage. Ultimately performance really depends on what you are doing with your collection. When performance is a concern you are best off testing each side by side and seeing which is better for your particular application.

Common methods of LinkedList

A simple example on LinkedList

User-defined implementation of linked list in java

Further you can implement your on linkedList in java.

SimpleSinglyLinkedList implemented in java

SimpleDoublyLinkedList implemented in java

Performance of List implementations in java

Common methods of LinkedList in java

Often LinkedLists are selected for use because of the methods in this class. LinkedList has most of the common methods ArrayList has (add(), get(), set(), remove(), size(), etc) plus a number of new methods that can be very convenient:

addFirst(object) & addLast(object): adds the object to the beginning or end of the LinkedList.

peek(): This just returns the first element of the LinkedList. Appreciate this method name: The language architect here seemed to be feeling cutesy, which you don't see often.

poll():This returns and removes the first element of the LinkedList. Also this will return null if the LinkedListis empty.

offer(): Attempts to add object to the end of the LinkedLists, and returns a Boolean based on weather it was added or not.

removeFirst() & removeLast(): Returns and removes the last element.

List Implementations in java

Being a Collection subtype all methods in the Collection interface are also available in the List interface.

Since List is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following List implementations in the Java Collections API:

 

• java.util.Vector
  Vectors(Java 1.1) (Click on link to see tutorial on it)
  --uses array to implement list
• java.util.ArrayList
  ArrayList (Click on link to see tutorial on it)
  --uses array to implement List
  – not thread-safe, otherwise same as Vector
• java.util.LinkedList
  LinkedList  (Click on link to see tutorial on it)
  --List interface implemented as a doubly-linked list
  – access to elements is not constant time
  – better performance for frequent add/remove operations in middle of List
• java.util.Stack
  Stack

There are also List implementations in the java.util.concurrent package, which we will see later.

Here are a few examples of how to create a List instance:

List listA = new ArrayList();
List listB = new LinkedList();
List listC = new Vector();
List listD = new Stack();    

Performance of List interface implementations

LinkedList

- Performance of get and remove methods is linear time [ Big O Notation is O(n) ] - Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ]

ArrayList

- The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. [ Big O Notation is O(1) ]
- The add operation runs in amortized constant time [ Big O Notation is O(1) ] , but in worst case (since the array must be resized and copied) adding n elements requires linear time [ Big O Notation is O(n) ]
- Performance of remove method is linear time [ Big O Notation is O(n) ]
- All of the other operations run in linear time [ Big O Notation is O(n) ]. The constant factor is low compared to that for the LinkedList implementation.

Difference between ArrayList and LinkedList

java.util.ArrayList and java.util.LinkedList are two Collections classes used for storing lists of object references Here are some differences:

ArrayList	LinkedList
ArrayList uses primitive object array for storing objects.	LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.
ArrayList implements the RandomAccess interface.	LinkedList does not implement RandomAccess interface.
Because of above point its fast to access any element randomly in arraylist. The commonly used ArrayList implementation uses primitive Object array for internal storage. Therefore an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method.	Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there's no fast way to access the Nth element of the list.
Adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward. (Using System.arrayCopy())	Whereas Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.
Uses memory equivalent to element in it.	Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.
ArrayList may also have a performance issue when the internal array fills up. The arrayList has to create a new array and copy all the elements there. The ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer. Hence if we can guess the number of elements that we are going to have, then it makes sense to create a arraylist with that capacity during object creation (using construtor new ArrayList(capacity)).	LinkedLists should not have such capacity issues.

Difference between iterator and index access

Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the ‘n’ location and get the element. It doesnot traverse through n-1 elements. So this is like random access, as it is in case of arrays.

In Iterator based access, the cursor has to traverse through each element to get the desired element.So to reach the ‘n’th element it need to traverse through n-1 elements. So this is the case of linked list, where we have to go through each element to insert something in list.

Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.

Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.

Traversal or search in index based datastructure is faster.

ArrayList is index access and LinkedList is iterator access.

LinkedList example in java

This program does the same thing as above using java.util.LinkedList, which hides the linking infrastructure and extra class. It is a doubly-linked list so moving in both directions is possible.

package linkedlistexamples;
import java.util.*;
public class LibraryLinkedList {
    public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         LinkedList lst = new LinkedList();
           //... Read and build list of words.
         while (in.hasNext()) {
            String word = in.next();
            lst.add(word);
        }
            //... Enhanced for loop to print list forward.
        //    Could also use an Iterator (forward only) or
        //    ListIterator (forward or backward).
        System.out.println("*** Print words in order of entry");
        for (String s : lst) {
            System.out.println(s);
        }
                //... Use ListIterator go to backward.  Start at end. 
        System.out.println("*** Print words in reverse order of entry");
        for (ListIterator lit = lst.listIterator(lst.size());
                            lit.hasPrevious();) {
            System.out.println(lit.previous());
        }
    }
}

SimpleDoublyLinkedList.java–Implementing a doubly linked link list in java

// Purpose: Shows a simple doubly-linked list.  Very few changes
//          from singly-linked, but allows backwards traversal and
//          easier insertion and deletion.
//          Main builds list of words, prints it forward and backward.
// Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

package linkedlistexamples;

import java.util.Scanner;

public class SimpleDoublyLinkedList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        Elem2 front = null;    // First element of list.
        Elem2 back  = null;    // Last element of list.
        
        //... Read a list of words.
        while (in.hasNext()) {
            String word = in.next();
            
            Elem2 e = new Elem2();     // Create a new list element.
            e.data = word;           // Set the data field.
            
            //... Two cases must be handled differently
            if (front == null) {
                //... When the list is empty, we have to set the front pointer.
                front = e;            // Back element will be set below.
            } else {
                //... When we already have elements, we need to link to it.
                back.next = e;       // Link last elem to new element.
            }
            e.prev = back;
            back = e;                // Update back to link to new element.
        }
        
        System.out.println("*** Print words in order of entry");
        for (Elem2 e = front; e != null; e = e.next) {
            System.out.println(e.data);
        }
        
        System.out.println("*** Print words in reverse order of entry");
        for (Elem2 e = back; e != null; e = e.prev) {
            System.out.println(e.data);
        }
    }
}

////////////////////////////////////////////////////////////////////////// Elem2
// Simple classes to hold data are sometimes defined with public fields.
// This practice isn't good, but was done here for simplicity.
class Elem2 {
    public Elem2 next;   // Link to next element in the list.
    public Elem2 prev;   // Link to the previous element.
    public String data;  // Reference to the data.
}

SimpleSinglyLinkedList.java --- Implementing singly linked link-list in java

This shows three programs.

• A simple singly-linked list. This shows the basics.
• A doubly-linked list. This is almost as simple as the singly-linked list, but makes some operations easier.
• Use of the java.util.LinkedList class, which is easy to use because it hides the details.

import java.util.Scanner;

public class SimpleSinglyLinkedList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        Elem front = null;    // First element of list.
        Elem back  = null;    // Last element of list.
        
        //... Read a list of words.
        while (in.hasNext()) {
            String word = in.next();
            
            Elem e = new Elem();     // Create a new list element.
            e.data = word;           // Set the data field.
            
            //... Two cases must be handled differently
            if (front == null) {
                //... When the list is empty, we have to set the front pointer.
                front = e;            // Back element will be set below.
            } else {
                //... When we already have elements, we need to link to it.
                back.next = e;       // Link last elem to new element.
            }
            back = e;                // Update back to link to new element.
        }
        
        //... While loop to print list in forward order.
        System.out.println("*** Print words in order of entry");
        Elem curr = front;
        while (curr != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
        
        System.out.println("*** Print words in order of entry");
        for (Elem e = front; e != null; e = e.next) {
            System.out.println(e.data);
        }
        
        //... Printing list in backward order is an interesting exercise.
        //    But too much for here.
    }
}

////////////////////////////////////////////////////////////////////////// Elem
// Simple class to hold data are sometimes defined with public fields.
// This practice isn't good, but was done here for simplicity.
class Elem {
    public Elem next;    // Link to next element in the list.
    public String data;  // Reference to the data.
}