LinkedList Class

LinkedList is a collection class that implements List, Deque and Queue Interfaces.

Queue stores and removes its elements based on a first-in, first-out(FIFO) principle. As, LinkedList implements Deque interface, so LinkedList can be used to represent a first-in, first-out(FIFO) Queue.
Deque is a double-ended queue i.e. first-in, first-out(FIFO) or last-in, first-out(LIFO) principle. As LinkedList class implements Deque interface, so LinkedList can also be used to depict a Deque or even a Stack(LIFO).

Important features of LinkedList

LinkedList allows storage of duplicate elements in it.
LinkedList maintains an order in which elements are inserted in it.
LinkedList can be used to depict a first-in, first-out(FIFO) or last-in, first-out(LIFO) storage.

Constructors of LinkedList:

1) LinkedList()
This constructor creates an empty LinkedList of a particular object type. Example -

LinkedList<Integer> arrL= new LinkedList<Integer>();

This constructor example creates an ArrayList to hold Integer objects.

2) LinkedList(Collection <? extends E>c)
This constructor creates a LinkedList initialized with the elements of Collection c, with a condition, that Collection c holds similar type of objects as the type declared by the LinkedList. Example -

LinkedList<Integer> arrL1 = new LinkedList<Integer>():
LinkedList<Integer> arrL2 = new LinkedList<Integer>(arrL1);

This constructor example creates a LinkedList arrL2 initialized with the elements of a LinkedList arrL1. Both of the LinkedList hold Integer objects.

Some important methods of LinkedList class

Methods	Description
boolean add(E e)	Inserts the element e at the end of an LinkedList.
void addFirst(E e)	Inserts the element e at the beginning of the LinkedList.
void addLast(E e)	Inserts the element e at the end of LinkedList.
E removeFirst()	Removes the first element of the LinkedList.
E removeLast(E e)	Removes the last element of the LinkedList.
boolean offer(E e)	Inserts the element e at the end of the LinkedList.
E peek()	Returns the head(first) element of the LinkedList, without removing it.
E poll()	Returns and removes the head(first) element of the LinkedList.
int size()	Returns the total number of elements in an ArrayList.
void clear()	Removes all of the elements from the ArrayList
E get(int index)	Returns the element at the specified index in an ArrayList.
E remove(int index)	Removes an element at a specified index in an ArrayList.
boolean remove(Object o)	Removes the first occurrence of an Object from the ArrayList, if it is present.
Object[] toArray()	Returns an Object array containing all the elements of an ArrayList.
Iterator iterator()	Returns an Iterator to iterate over elements of an ArrayList.
ListIterator listIterator()	Returns a ListIterator to iterate over elements of an ArrayList.

Creating a LinkedList and displaying its features.

In this program, we have created a LinkedList to hold <String> objects and we will add/remove some elements from this list and use it to initialize a new LinkedList.

import java.util.*;

class LinkedList1
{
public static void main(String... ar)
{
LinkedList<String> link= new LinkedList<String>();

link.add("B");
link.add("3");
link.add("B");
link.add("2");
link.addFirst("c");
link.addLast("1");


System.out.println("Linkedlist after adding objects = " + link);
System.out.println("Size of LinkedList = "+ link.size());

link.removeFirst();
System.out.println("After removing first element, LinkedList is = "+ link);

link.removeLast();
System.out.println("After removing Last element, LinkedList is = "+ link);
 
link.remove("2");
System.out.println("After removing 2, LinkedList is = "+ link);

LinkedList<String> link2 = new LinkedList<String>(link);
System.out.println("New LinkedList created from an existing LinkedList" + link2);
}
}

Output is - :

LinkedList after adding objects = [c, B, 3, B, 2, 1]
Size of LinkedList = 6
After removing first element, LinkedList is  = [B, 3, B, 2, 1]
After removing Last element, LinkedList is = [B, 3, B, 2]
After removing element 2, LinkedList is = [B, 3, B]
New LinkedList created from an existing LinkedList[B, 3, B]

Program Analysis

The method add() is called to add the String objects to end of LinkedList(link).
The method addFirst() method is called to add String object to the head/beginning of the LinkedList.
The method addLast() is called to add a String object to the end/tail of the LinkedList
The method removeFirst() is called to remove the first element in the LinkedList.
The method removeLast() is called to remove the last element in the LinkedList.
The method remove(Object o) is called to remove the Integer object(2).

Creating a new LinkedList from an existing LinkedList

In this program, we will create a LinkedList that holds <Integer> objects. We will create and initialize a new LinkedList using the contents of an existing LinkedList.

import java.util.*;

class LinkedList1
{
public static void main(String... ar)
{
LinkedList<Integer> link1= new LinkedList<String>();

link1.add(4);
link1.add(1);
link1.add(5);
link1.add(2);
link1.add(3);


System.out.println("LinkedList after adding objects = " + link1);
System.out.println("Size of LinkedList = "+ link1.size());

System.out.println("Creating a new LinkedList created from an existing one");

LinkedList<Integer> link2= new LinkedList<Integer>(link1);
System.out.println("Contents of new LinkedList : " + link2);
System.out.println("Size of new LinkedList = "+ link2.size());
}

}

Output is - :

LinkedList after adding objects = [4, 1, 5, 2, 3]
Size of LinkedList = 5
Creating a new LinkedList created from an existing LinkedList
Contents of new LinkedList : [4, 1, 5, 2, 3]
Size of new LinkedList = 5

Using LinkedList(link1) a new LinkedList(link2) is created, this will initialize new LinkedList(link2) with the elements of existing LinkedList(link1).

Converting an LinkedList to an Object array using toArray() method.

import java.util.*;

class LinkedList1
{
public static void main(String... ar)
{
LinkedList<Integer> link1= new LinkedList<Integer>();

link1.add(40);
link1.add(10);
link1.add(50);
link1.add(20);
link1.add(30);


System.out.println("LinkedList after adding objects = " + link1);
System.out.println("Size of LinkedList = "+ link1.size());

//Converting an LinkedList to an Object array.
Object[] a = link1.toArray();

System.out.print("Contents of an Object Array created from LinkedList - ");

/Iterating over the elements of Object array
for(Object element : a)
System.out.print(element + " " );

}
}

Output is - :

LinkedList after adding objects = [40, 10, 50, 20, 30]
Size of LinkedList = 5
Contents of an Object Array after created from LinkedList - 40 10 50 20 30

We have created an Object array from an existing LinkedList using toArray() method of LinkedList class. We have displayed the elements in this Object array using a for-each loop.

Difference between ArrayList and LinkedList

ArrayList implements only List interface, whereas LinkedList implements List, Queue, and Deque interfaces.

ArrayList is internally an implementation of an array which is dynamic in nature, where as LinkedList is internally a double-ended linked list with each element maintaining links to its left and right neighbours.

ArrayList supports faster search and iteration of elements than LinkedList because ArrayList is internally an array which maintains indexes of its all elements stored contiguously in the memory. whereas, in LinkedList, elements are not stored contiguously in the memory, hence search in LinkedList is slower because it results in traversing the entire linked list starting from the first element at its beginning and then moving on to next linked element which could be at some other memory location and then to the next linked element until the searched element is found.

ArrayList supports slower insertion and deletion of elements than LinkedList because if a new element is inserted in an ArrayList, the rest of elements after it are shifted down and when an element is deleted, the rest of element after the deleted element are shifted up.
whereas in LinkedList, elements are linked to one another, hence, no such shifting of elements takes place when an element is inserted/deleted but only the links between a few neighbouring elements around the inserted/deleted element are modified.

ArrayList implements RandomAccess interface, hence ArrayList is efficient at random access of an element than LinkedList.

As ArrayList is not a double-ended storage, hence it only provides a direct method for insertion of an element at its end and it doesn't provide a direct method for insertion of an element at its beginning, whereas, LinkedList being a double-ended storage, provides direct methods for insertion and deletion of an element not just at its end but also at its beginning.

Please share this article -

Please Subscribe

Please subscribe to our social media channels for daily updates.

Notifications

Please check our latest addition

C#, PYTHON and DJANGO