Java Linkedlist

The Java LinkedList class utilizes a doubly linked list for element storage, offering a data structure based on linked lists. This class inherits from the AbstractList class and implements the List and Deque interfaces.

Within Java, a LinkedList is a class that enforces the List interface and embodies a linked list data structure. In contrast to arrays that hold elements in consecutive memory locations, a linked list holds elements as nodes. Each node comprises the element and a reference (or pointer) to the subsequent node in the sequence.

The important points about Java LinkedList are:

• ✅ Java 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 occur.
• ✅ Java LinkedList class can be used as a list, stack or queue.

A significant characteristic of a LinkedList is its ability to adjust its size dynamically, expanding or contracting as necessary. This is made possible by the storage of each element in a separate node, facilitating effective insertion and deletion procedures. Nevertheless, retrieving elements by their index in a LinkedList is not as efficient as with arrays, as it necessitates traversing the list either from the start or the end to access the specific element.

Within Java, the LinkedList class offers a range of functionalities for managing lists. These include actions like inserting or deleting elements, retrieving elements by their position, and locating specific elements. Furthermore, it presents functions for tasks such as appending elements to the start or end of the list, placing elements at particular locations, and deleting elements based on their index or value.

Hierarchy of LinkedList Class

The List interface is an extension of the Collection interface and serves as a structured collection of elements in a specific order. Lists permit the inclusion of duplicate elements and offer functionalities to retrieve elements based on their numerical index. Within the Java programming language, the LinkedList class is responsible for implementing the List interface and embodies a data structure known as a doubly linked list.

A LinkedList is a data structure comprising nodes that point to both the next and previous nodes in the sequence. This design facilitates swift insertion and deletion processes by merely adjusting neighboring nodes' references. Nonetheless, when it comes to accessing elements by index, LinkedList is less efficient than an ArrayList since it mandates traversing the list from either end to locate the specific element.

Doubly Linked List

In the Java programming language, a doubly linked list is a variant of a linked list where each node holds references to both the next node and the previous node in the sequence. This unique feature enables traversal of the list in both forward and backward directions, distinguishing it from a singly linked list that permits traversal in a single direction only.

A benefit of utilizing a doubly linked list is its enhanced efficiency in deleting elements when contrasted with a singly linked list. This is achievable by directly accessing the preceding node of a specified node, simplifying the process of removing elements from the middle of the list without the need to traverse the entire list.

When dealing with a doubly linked list, it is possible to insert or delete elements from either end of the list.

Yet, a downside of a doubly linked list is its increased memory usage when compared to a singly linked list due to each node having an extra pointer to the previous node. Furthermore, the management of these previous pointers introduces intricacy to the list's implementation.

LinkedList Class Declaration

LinkedList, functioning as a List, ensures the preservation of the sequence in which elements are inserted and permits the existence of duplicates. It offers functionalities for inserting, deleting, and retrieving elements at designated indexes within the list. Moreover, operating as a Deque, LinkedList enables actions at both extremities of the list, facilitating the addition and elimination of elements from the start and end of the list.

Let's examine the declaration of the java.util.LinkedList class.

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

Constructors of Java LinkedList

In Java, the LinkedList class offers constructors for generating linked list instances. One of these constructors establishes an empty linked list by setting the size field to zero and assigning null to both the first and last fields, denoting an absence of elements in the list. This constructor becomes handy when there is a need to form a linked list devoid of any starting elements.

An alternative constructor enables the creation of a linked list from a preexisting collection like an ArrayList or a different LinkedList. This constructor starts by establishing an empty linked list and subsequently incorporates all the elements from the collection into the linked list through the addAll method. This constructor proves to be useful when there is a need to transform a collection into a linked list while maintaining the original sequence of elements.

Methods of Java LinkedList Class

Java LinkedList Example

Example

import java.util.*;

public class Main{

 public static void main(String args[]){



  LinkedList<String> al=new LinkedList<String>();

  al.add("Ravi");

  al.add("Vijay");

  al.add("Ravi");

  al.add("Ajay");



  Iterator<String> itr=al.iterator();

  while(itr.hasNext()){

   System.out.println(itr.next());

  }

 }

}

Output:

Ravi

Vijay

Ravi

Ajay

Java LinkedList example to add elements

Here, we see different ways to add elements.

Example

import java.util.*;

public class Main{

 public static void main(String args[]){

 LinkedList<String> ll=new LinkedList<String>();

		   System.out.println("Initial list of elements: "+ll);

		   ll.add("Ravi");

		   ll.add("Vijay");

		   ll.add("Ajay");

		   System.out.println("After invoking add(E e) method: "+ll);

		   //Adding an element at the specific position

		   ll.add(1, "Gaurav");

    	   System.out.println("After invoking add(int index, E element) method: "+ll);

    	   LinkedList<String> ll2=new LinkedList<String>();

    	   ll2.add("Sonoo");

		   ll2.add("Hanumat");

		   //Adding second list elements to the first list

		   ll.addAll(ll2);

		   System.out.println("After invoking addAll(Collection<? extends E> c) method: "+ll);

    	   LinkedList<String> ll3=new LinkedList<String>();

    	   ll3.add("John");

		   ll3.add("Rahul");

		   //Adding second list elements to the first list at specific position

		   ll.addAll(1, ll3);

		   System.out.println("After invoking addAll(int index, Collection<? extends E> c) method: "+ll);

    	   //Adding an element at the first position

		   ll.addFirst("Lokesh");

		   System.out.println("After invoking addFirst(E e) method: "+ll);

		   //Adding an element at the last position

    	   ll.addLast("Harsh");

    	   System.out.println("After invoking addLast(E e) method: "+ll);

		   

 }

}

Output:

Initial list of elements: []

After invoking add(E e) method: [Ravi, Vijay, Ajay]

After invoking add(int index, E element) method: [Ravi, Gaurav, Vijay, Ajay]

After invoking addAll(Collection<? extends E> c) method: 

[Ravi, Gaurav, Vijay, Ajay, Sonoo, Hanumat]

After invoking addAll(int index, Collection<? extends E> c) method: 

[Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat]

After invoking addFirst(E e) method: 

[Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat]

After invoking addLast(E e) method: 

[Lokesh, Ravi, John, Rahul, Gaurav, Vijay, Ajay, Sonoo, Hanumat, Harsh]

Java LinkedList example to remove elements

Here, we see different ways to remove an element.

Example

import java.util.*;

public class Main {



	    public static void main(String [] args)

	    {

	       LinkedList<String> ll=new LinkedList<String>();

		   ll.add("Ravi");

		   ll.add("Vijay");

		   ll.add("Ajay");

		   ll.add("Anuj");

		   ll.add("Gaurav");

		   ll.add("Harsh");

		   ll.add("Virat");

		   ll.add("Gaurav");

		   ll.add("Harsh");

		   ll.add("Amit");

		   System.out.println("Initial list of elements: "+ll);

		 //Removing specific element from arraylist

		      ll.remove("Vijay");

		      System.out.println("After invoking remove(object) method: "+ll); 

		 //Removing element on the basis of specific position

		      ll.remove(0);

		      System.out.println("After invoking remove(index) method: "+ll); 

		      LinkedList<String> ll2=new LinkedList<String>();

		      ll2.add("Ravi");

		      ll2.add("Hanumat");

		 // Adding new elements to arraylist

		      ll.addAll(ll2);

		      System.out.println("Updated list : "+ll); 

		 //Removing all the new elements from arraylist

		      ll.removeAll(ll2);

		      System.out.println("After invoking removeAll() method: "+ll); 

		 //Removing first element from the list

		      ll.removeFirst();

		      System.out.println("After invoking removeFirst() method: "+ll);

		  //Removing first element from the list

		      ll.removeLast();

		      System.out.println("After invoking removeLast() method: "+ll);

		  //Removing first occurrence of element from the list

		      ll.removeFirstOccurrence("Gaurav");

		      System.out.println("After invoking removeFirstOccurrence() method: "+ll);

		  //Removing last occurrence of element from the list

		      ll.removeLastOccurrence("Harsh");

		      System.out.println("After invoking removeLastOccurrence() method: "+ll);



		      //Removing all the elements available in the list     

		      ll.clear();

		      System.out.println("After invoking clear() method: "+ll); 

	   }

	}

Output:

Initial list of elements: [Ravi, Vijay, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]

After invoking remove(object) method: [Ravi, Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]

After invoking remove(index) method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]

Updated list : [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit, Ravi, Hanumat]

After invoking removeAll() method: [Ajay, Anuj, Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]

After invoking removeFirst() method: [Gaurav, Harsh, Virat, Gaurav, Harsh, Amit]

After invoking removeLast() method: [Gaurav, Harsh, Virat, Gaurav, Harsh]

After invoking removeFirstOccurrence() method: [Harsh, Virat, Gaurav, Harsh]

After invoking removeLastOccurrence() method: [Harsh, Virat, Gaurav]

After invoking clear() method: []

Java LinkedList Example to reverse a list of elements

Example

import java.util.*;

public class Main{

 public static void main(String args[]){



  LinkedList<String> ll=new LinkedList<String>();

		   ll.add("Ravi");

		   ll.add("Vijay");

		   ll.add("Ajay");

		   //Traversing the list of elements in reverse order

		   Iterator i=ll.descendingIterator();

		   while(i.hasNext())

		   {

			   System.out.println(i.next());

		   }

		   

 }

}

Output:

Ajay

Vijay

Ravi

Java LinkedList Example: Book

Example

import java.util.*;

class Book {

int id;

String name,author,publisher;

int quantity;

public Book(int id, String name, String author, String publisher, int quantity) {

	this.id = id;

	this.name = name;

	this.author = author;

	this.publisher = publisher;

	this.quantity = quantity;

}

}

public class Main {

public static void main(String[] args) {

	//Creating list of Books

	List<Book> list=new LinkedList<Book>();

	//Creating Books

	Book b1=new Book(101,"Let us C","Yashwant Kanetkar","BPB",8);

	Book b2=new Book(102,"Data Communications & Networking","Forouzan","Mc Graw Hill",4);

	Book b3=new Book(103,"Operating System","Galvin","Wiley",6);

	//Adding Books to list

	list.add(b1);

	list.add(b2);

	list.add(b3);

	//Traversing list

	for(Book b:list){

	System.out.println(b.id+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity);

	}

}

}

Output:

101 Let us C Yashwant Kanetkar BPB 8

102 Data Communications & Networking Forouzan Mc Graw Hill 4

103 Operating System Galvin Wiley 6

Java LinkedList MCQ

1. Which interface does the LinkedList class implement in Java?

• ✅ List
• ✅ Deque
• ✅ Queue
• ✅ All of the above

Explanation: The LinkedList class in Java implements the List, Deque, and Queue interfaces, allowing it to be used as a list, double-ended queue, or queue.

1. What is the time complexity of inserting an element at the beginning of a LinkedList in Java?

• ✅ O(1)
• ✅ O(log n)
• ✅ O(n)
• ✅ O(n log n)

Explanation: Inserting an element at the beginning of a LinkedList in Java has a time complexity of O(1) because it only involves adjusting the nodes' pointers.

1. Which method is used to retrieve, but not remove, the head of a LinkedList in Java?

• ✅ poll
• ✅ peek
• ✅ remove
• ✅ get

The peek function in LinkedList fetches the first element in the list without deleting it. In case the list is empty, it will return null.

What is the expected result of the code below?

LinkedList<String> list = new LinkedList<>();

list.add("A");

list.add("B");

list.add("C");

list.addFirst("D");

System.out.println(list);

• ✅ [A, B, C, D]
• ✅ [D, A, B, C]
• ✅ [A, D, B, C]
• ✅ [D, B, C, A]

Explanation: The addFirst method inserts the specified element at the beginning of the list. Thus, "D" is added at the start, resulting in [D, A, B, C].

1. Which method can be used to add an element to the end of a LinkedList in Java?

• ✅ add
• ✅ addLast
• ✅ offer
• ✅ All of the above

In the context of adding an element to the end of a LinkedList, various methods can be employed. The add method originates from the List interface, addLast is associated with the Deque interface, while offer pertains to the Queue interface.