Java LinkedList

LinkedList is doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.

The LinkedList class extends AbstractSequentialList and implements the List, Deque, and Queue interfaces. It provides a linked-list data structure.

LinkedList is a generic class that has this declaration:

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Here, E specifies the type of objects that the list will hold.

• Java LinkedList inherits AbstractSequentialList and implements List and Deque interfaces.
• Java LinkedList maintains insertion order.
• Java LinkedList can contain duplicate elements.
• Java LinkedList is not synchronized.
• Manupulation in Java LinkedList is fast because no shifting needs to be occured.
• Java LinkedList can be used as List, Stack, Queue, and Deque.
• Java LinkedList can not be used for primitive types, like int, char, etc. We need to use wrapper classes.
• The iterators return by java LinkedList's Iterator() and listIterator () methods are fail-fast. If the list structure is modified after creating the iterator in any other way except the iterator add or remove methods, it will throw ConcurrentModificationException.

Java LinkedList constructors

There are two constructors in Java LinkedList.

Constructor	Description
public LinkedList()	This LinkedList constructor will return an empty linked list.
public LinkedList(Collection<? extends E> c)	This Java LinkedList constructor return a list containing the elements of the specified collection c, in the order they are returned by the collection's iterator. It will throws NullPointerException if the specified collection c is null

Below is a simple code snippet showing Java LinkedList constructors.

// Java LinkedList default constructor
LinkedList<String> vowels = new LinkedList<String>();
vowels.add("A");
vowels.add("E");
vowels.add("I");
vowels.add("O");
vowels.add("U");

// creating a linked list from the existing collection
LinkedList<String> list = new LinkedList<String>(vowels);

Java LinkedList methods

Method	Description
public boolean add(E e)	Appends the specified element to the end of this list.
public void add(int index, E element)	Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).
public boolean addAll(Collection<? extends E> c)	Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. Throws NullPointerException if the specified collection is null.
public boolean addAll(int index, Collection<? extends E> c)	Inserts all of the elements in the specified collection into this list, starting at the specified position. Shifts the element currently at that position (if any) and any subsequent elements to the right. The new elements will appear in the list in the order that they are returned by the specified collection's iterator. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()). Throws NullPointerException if the specified collection is null.
public E get(int index)	Returns the element at the specified position in this list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).
public E getFirst()	Returns the first element in this list. Throws NoSuchElementException if this list is empty.
public E getLast()	Returns the last element in this list. Throws NoSuchElementException if this list is empty.
public boolean remove(Object o)	Removes the first occurrence of the specified element from this list, if it is present. If this list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))). Returns true if this list contained the specified element.
public E remove(int index)	Removes the element at the specified position in this list. Shifts any subsequent elements to the left. Returns the element that was removed from the list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).
public E removeFirst()	Removes and returns the first element from this list. Throws NoSuchElementException if this list is empty.
public E removeLast()	Removes and returns the last element from this list. Throws NoSuchElementException if this list is empty.
public void addFirst(E e)	Inserts the specified element at the beginning of this list.
public void addLast(E e)	Appends the specified element to the end of this list.
public boolean contains(Object o)	Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).
public int size()	Returns the number of elements in this list.
public void clear()	Removes all of the elements from this list.
public E set(int index, E element)	Replaces the element at the specified position in this list with the specified element. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index > size()).
public int indexOf(Object o)	Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
public int lastIndexOf(Object o)	Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
public E peek()	Retrieves, but does not remove, the head (first element) of this list. Returns null if this list is empty.
public E element()	Retrieves, but does not remove, the head (first element) of this list. Throws NoSuchElementException if this list is empty.
public E poll()	Retrieves and removes the head (first element) of this list. Returns null if this list is empty.
public E remove()	Retrieves and removes the head (first element) of this list. Throws NoSuchElementException if this list is empty.
public boolean offer(E e)	Adds the specified element as the tail (last element) of this list.
public boolean offerFirst(E e)	Inserts the specified element at the front of this list.
public boolean offerLast(E e)	Inserts the specified element at the end of this list.
public E peekFirst()	Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
public E peekLast()	Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
public E pollFirst()	Retrieves and removes the first element of this list, or returns null if this list is empty.
public E pollLast()	Retrieves and removes the last element of this list, or returns null if this list is empty.
public void push(E e)	Pushes an element onto the stack represented by this list. In other words, inserts the element at the front of this list. This method is equivalent to addFirst.
public E pop()	Pops an element from the stack represented by this list. In other words, removes and returns the first element of this list. This method is equivalent to removeFirst(). Throws NoSuchElementException if this list is empty.
public boolean removeFirstOccurrence(Object o)	Removes the first occurrence of the specified element in this list (when traversing the list from head to tail). If the list does not contain the element, it is unchanged. Returns true if the list contained the specified element.
public boolean removeLastOccurrence(Object o)	Removes the last occurrence of the specified element in this list (when traversing the list from head to tail). If the list does not contain the element, it is unchanged. Returns true if the list contained the specified element.
public ListIterator<E> listIterator(int index)	Returns a list-iterator of the elements in this list (in proper * sequence), starting at the specified position in the list. Throws IndexOutOfBoundsException if the specified index is out of range (index < 0 || index >= size()).
public Iterator<E> descendingIterator()	Returns an iterator over the elements in this deque in reverse sequential order. The elements will be returned in order from last (tail) to first (head).
public Object clone()	Returns a shallow copy of this LinkedList.
public Object[] toArray()	Returns an array containing all of the elements in this list in proper sequence
public <T> T[] toArray(T[] a)	Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

Java LinkedList Example

Java LinkedList common operations. Here we will see an example of commonly used method of LinkedList.

package com.walking.techie;

import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo {

 public static void main(String[] args) {
  LinkedList<Integer> numbers = new LinkedList<Integer>();
  // Add elements in LinkedList
  numbers.add(10);
  numbers.add(20);
  numbers.add(30);
  System.out.println("Elements of numbers list " + numbers);

  // Lets add 14 at specified position
  numbers.add(1, 15);
  System.out.println("Elements of numbers list " + numbers);

  // size of array list numbers
  System.out.println("Size of numbers list is " + numbers.size());

  // get operation of array list
  System.out.println("Element in numbers at 1st position is " + numbers.get(1));

  // check array list numbers contain 20
  System.out.println("numbers list contain element 20 ?:  " + numbers.contains(20));

  // check index of 20 in the array list numbers, -1 will return if not
  // present in list
  System.out.println("Index of 15 in numbers list is " + numbers.indexOf(20));

  // get first element of linked list
  System.out.println("First element or head of the linked list: " + numbers.getFirst());

  // get last element of linked list
  System.out.println("Last element or tail of the linked list: " + numbers.getLast());

  // remove first element of the linked list
  System.out.println("First element removed from the list: " + numbers.removeFirst());

  // remove last element of the linked list
  System.out.println("Last element removed from the list: " + numbers.removeLast());

  // creating odd numbers list
  List<Integer> oddNumbers = new LinkedList<Integer>();
  oddNumbers.add(5);
  oddNumbers.add(25);
  oddNumbers.add(9);

  // appending odd numbers list to numbers list
  numbers.addAll(oddNumbers);
  System.out.println("numbers list after appending odd numbers list " + numbers);

  // clear method to empty the odd numbers list
  oddNumbers.clear();
  System.out.println("odd number list " + oddNumbers);

  // set method example
  numbers.set(1, 40);
  System.out.println("numbers list " + numbers);

  // remove method, to remove element of list from 1st index
  numbers.remove(1);
  System.out.println("numbers list after removing 40 " + numbers);

  // remove first occurrence of 5
  boolean isRemoved = numbers.remove(new Integer(5));
  System.out.println("element 5 removed ? " + isRemoved + " numbers contains " + numbers);
 }
}

Output of above program is shown below:

Elements of numbers list [10, 20, 30]
Elements of numbers list [10, 15, 20, 30]
Size of numbers list is 4
Element in numbers at 1st position is 15
numbers list contain element 20 ?:  true
Index of 15 in numbers list is 2
First element or head of the linked list: 10
Last element or tail of the linked list: 30
First element removed from the list: 10
Last element removed from the list: 30
numbers list after appending odd numbers list [15, 20, 5, 25, 9]
odd number list []
numbers list [15, 40, 5, 25, 9]
numbers list after removing 40 [15, 5, 25, 9]
element 5 removed ? true numbers contains [15, 25, 9]

Copy or clone of a Java LinkedList

Here we can see an example for creating a duplicate instance of Java LinkedList using clone() method.

package com.walking.techie;

import java.util.LinkedList;

public class LinkedListCloneDemo {

 public static void main(String[] args) {
  LinkedList<String> list = new LinkedList<String>();
  list.add("first");
  list.add("second");
  list.add("third");
  System.out.println("Actual linked list " + list);
  LinkedList<String> cloneList = (LinkedList<String>) list.clone();
  System.out.println("Cloned linked list " + cloneList);
 }
}

Output of above program is shown below:

Actual linked list [first, second, third]
Cloned linked list [first, second, third]

List of sample examples of Java Linked List

To keep this post short . I am including link of all other examples of linked list. Please click on below link to read further about Java LinkedList.

You can find example of other methods and operations on the Java Linked list here.