Operations in Linked List in Java

Table of Contents

Introduction

You, along with three of your friends who are all beginner level programmers, are given the responsibility of implementing a Student Record Management System wherein the faculty should be able to Insert a Student Record, Delete a record, Modify a record and iterate over all the records.

You, along with your three friends, mutually agree to use a Linked List for this purpose. Consider the name of your team members to be A, B, C, and D, respectively. The work division is as follows:

A -> Insertion of Records
B -> Deletion of Records
C -> Updation of Records
D -> Iteration of Records

Now four of you are working independently. There are issues related to time complexity of the code, space complexity, further optimization of code, and so on and so forth. Situations like these can be easily resolved when working on smaller projects. However, when you are working on larger projects, the concern is on other factors and not just the usual implementation of Data structures and commonly used algorithms.

In such cases, Collection Framework in Java came to the rescue. The collection framework in Java provides a direct implementation of various data structures and algorithms using a set of classes and Interfaces. In this article, the Linked List data structure is discussed using the LinkedList class of the Collection Framework. Various operations in Linked List in Java are also discussed.

Collection Framework

In Java, the collection framework is a collection of interfaces and classes which helps in the storage and processing of data efficiently and effectively. The framework provides an architecture for the development work. The collection framework in Java has several useful classes and interfaces that make a programmer’s life easy by providing direct implementation of various data structures and algorithms, so you don’t have to implement them from scratch and increases performance by providing optimized implementations.

All the classes and interfaces of the collection framework are inside the Java.util package. Inside the collection framework, there is a Collection interface which further has three interfaces, namely List, Queue, and Set, respectively.

The complete hierarchy of Java Collections Framework is depicted below:

LinkedList Class

LinkedList class is an implementation of the Linked List data structure. Linked List is a linear data structure, unlike arrays, the elements are not stored at contiguous memory locations, but at separate memory locations. Each of the memory blocks is linked to each other, hence the name linked List. Each node has a data part and reference to the next node in the sequence.

LinkedList class inherits the AbstractList class and implements the List and deque interface.

Following is the Declaration of LinkedList class

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

To create a LinkedList, we need to create an object of the LinkedList class. The LinkedList class consists of various constructors that allow the creation of a Linked List.

LinkedList()	This constructor is used to create an empty Linked List
LinkedList(Collection<? Extends E> c)	This constructor is used to construct an ordered list containing the elements of the collection in order as they are returned by the collection’s iterator.

The above program will create an empty Linked List. The output of the above program is:

Studying Operations in Linked List in JavaEmpty Linked List created

Some important points about the LinkedList class in Java are as follows:-

LinkedList class internally uses a doubly linked list data structure for storing elements.
Java LinkedList class can contain duplicate elements
Java LinkedList class inherits the AbstractList class and implements the List and deque interface.

As with any Linear data structure, in LinkedList, the following operations can be performed:-

Adding Elements
Deletion of Elements
Modifying Existing Elements

Adding Elements

As with the normal implementation of Linked List, using LinkedList class we can insert data to the starting, ending, and at any random position in the Linked List. There are various methods for inserting/adding elements in Linked List in Java.

Method	Description
boolean add(E e)	Adds an element to the end of the List. This method returns true after execution
void add(int index, E element)	Adds an element at the specified index by shifting the elements currently at that position(if any) and other elements to the right. This method does not return any value. An exception will be raised if the specified index is out of range.
boolean addAll(Collection<? extends E> c)	Appends all the elements to the end in the order returned by the collection’s iterator. The parameter C is a collection of ArrayList. The method returns True if at least one action of insertion is performed. NullPointerException will be raised if the specified collection is empty
boolean addAll(int index, Collection<? extends E> c)	Adds all the elements in the specified collection at the specified index. The parameter C is a collection of ArrayList. The method returns True if at least one action of insertion is performed.
void addFirst(E e)	Add the element at the beginning of the List, and the remaining elements will be shifted one place to the right. This method does not return any value.
void addLast(E e)	Add the element at the end of the List.This method does not return any value.

Note: The syntax ? extends E means “some type that either is E or a subtype of E”. The ? is a wildcard.

The below program illustrates commonly used methods for inserting elements in a LinkedList

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
public class Demo{
    public static void main(String []args)
{
System.out.println(“Studying Operations in Linked List in Java”);
// Constructor for creating an empty Linked List

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

       // add(), addFirst() and addLast() method
ll.add(24); // 24        ll.add(48); // 24 48
ll.add(2, 72); // 24 48 72        ll.addFirst(0);

// 0 24 48 72        ll.addFirst(99); // 99 0 24 48 72        ll.addLast(200); // 99 0 24 48 72 200

System.out.println(“\nThe Linked list is: ” + ll);

    // addAll() method

Collection<Integer> coll = new ArrayList<Integer>();
coll.add(1);
coll.add(2);
coll.add(3);
coll.add(4);
// Appending the collection to the list
ll.addAll(3, coll);
// Printing the new Linked List

System.out.println(“The modified linked list is: ” + ll);
}
}

The output of the above program is:

Studying Operations in Linked List in Java
The Linked list is: [99, 0, 24, 48, 72, 200]The modified linked list is: [99, 0, 24, 1, 2, 3, 4, 48, 72, 200]

Modifying Elements

Many times wrong data is inserted in the List. A LinkedList is indexed, so the element which needs to be changed is referenced by the index of the element in the set() method.

The method returns the previous value from the linked List that is replaced with the new value.

The function accepts two parameters:-

index: The integer index referring to the position of the element that is to be replaced.
element: It is the new element by which the existing element will be replaced.

The below program illustrates the set() method in Java

import java.util.LinkedList;
public class Demo
{
    public static void main(String []args)
{
System.out.println(“Studying Operations in Linked List in Java”);
// Constructor for creating an empty Linked List

LinkedList<String> ll = new LinkedList<>();
ll.add(“ABC”);        ll.add(“DEF”);        ll.add(“GHI”);
System.out.println(“Printing the original list”);
System.out.println(ll); // Using the set() method here

System.out.println(“Element to be replaced is: ” + ll.set(1, “XYZ”));

System.out.println(“Element to be replaced is: ” + ll.set(0, “PQR”));

System.out.println(“Printing the modified list”);

System.out.println(ll);

}
}

The output of the above program is:

Studying Operations in Linked List in JavaPrinting the original list[ABC, DEF, GHI]Element to be replaced is: DEFElement to be replaced is: ABCPrinting the modified list[PQR, XYZ, GHI]

Deleting Elements

There are various methods for deleting an element from a list, as described below:

Method	Description
void clear()	This method is used to remove all the elements from a list
E poll()	This method is used to retrieve and remove the first element(head) from a list. This method returns the head of the list or null if the list is empty.
E pollFirst()	This method returns and removes the first element of a list. In case of an empty list, null will be returned. This method returns the first element of the list or null if the list is empty
E pollLast()	This method returns and removes the last element of a list. In case of an empty list, null will be returned.
E remove()	This method returns and removes the first element or head of a list.
E remove(int index)	This method removes the element at the specified index. All the subsequent elements are shifted to the left. The method returns the element that was removed from the list.

The below program illustrates the deletion of elements from a list.

import java.util.*;
public class Demo
{
    public static void main(String []args)
{
System.out.println(“Studying Operations in Linked List in Java”);
LinkedList<String> ll = new LinkedList<String>();
ll.add(“Operations”);      ll.add(“on”);      ll.add(“LinkedList”);
ll.add(“in”);      ll.add(“java”);
System.out.println(“Original List of elements: ” + ll);
// REMOVING ELEMENTS
ll.remove(“on”); // Removing specific element
System.out.println(“List of elements after invoking remove(object) method : ” + ll);
ll.poll(); // Removing first element
System.out.println(“List of elements after invoking poll() method : ” + ll);
ll.remove(1); // Removing element by index
System.out.println(“List of elements after invoking remove(int index) method : “+ll);

ll.removeLast();
System.out.println(“List of elements after invoking removeLast() method : ” + ll);
       }
}

The output of the above program is:

Studying Operations in Linked List in JavaOriginal List of elements: [Operations, on, Linked List, in, Java]
List of elements after invoking remove(object) method : [Operations, Linked List, in, Java]
List of elements after invoking poll() method : [Linked List, in, java]
List of elements after invoking remove(int index) method : [Linked List, Java]
List of elements after invoking removeLast() method : [Linked List]

There are various other methods used in the deletion of elements; you can refer to the documentation for more details.

Till now you have studied basic methods for performing various operations in Linked List in Java. There are many other methods as well; you can explore them in the documentation.

Key Takeaways

In this article, Collection Frameworks were introduced. The LinkedList class was discussed along with the operations in Linked List in Java with examples.

With this done, you can now switch to learn more about the Java programming language. Collection Framework and its classes are frequently used in competitive programming as well. You can practice questions on Codestudio, read interview experiences, explore the articles on various topics to solidify your understanding of Computer Science Fundamentals.