LinkedList is a linear data structure similar to arrays in Java. LinkedList elements, on the other hand, are not kept in contiguous locations like arrays; instead, they are linked together via pointers. Each LinkedList member has a reference (address/pointer) to the next LinkedList element.
The items of the Java LinkedList class are stored as a double-linked list. It uses a linked-list data structure to store information. It implements the List and Deque interfaces and inherits the AbstractList class. The list interface is implemented by the classes AbstractList, CopyOnWriteArrayList, and AbstractSequentialList. Each of the clauses mentioned above has its own set of features. They are as follows:
AbstractList: This class is used to implement an immutable list, and all that is required is to extend it and implement only the get() and size() functions. This class implements the list interface.
CopyOnWriteArrayList: This class implements the list interface. It’s an improved version of ArrayList in which all changes (add, set, delete, and so on) are made by creating a new copy of the list.
The following are the key features of Java LinkedList:
- Duplicate elements are possible in the Java LinkedList class.
- The LinkedList class in Java keeps track of insertion order.
- The LinkedList class in Java is non-synchronized.
- Manipulation in the Java LinkedList class is quick since no shifting is required.
- The LinkedList class in Java is used to create a list, a stack, or a queue.
Representation of LinkedList
- The Node is the name given to each element in the LinkedList. The LinkedList’s Nodes each have two items:
- a) The element’s content
- b) Pointer/Address/Reference to the LinkedList’s Next Node.
- The LinkedList’s Head merely holds the Address of the List’s First Element.
- Because it is the end of the List, the last element of the LinkedList has null in the pointer section of the node, as shown in the diagram.
- The default linked list is a singleton linked list.
- The doubly linked list is a more complex version of LinkedList. Each node in a doubly-linked list is made up of three parts:
- a) A pointer to the linked list’s previous node.
- b) The element’s content
- c) A pointer to the linked list’s next node.
What is the purpose of a Linked List?
You should be familiar with arrays, which are also linear data structures, but they have some limitations, such as:
- The size of an array is fixed, and it is difficult to predict the number of elements ahead of time. If the declared size falls short, we cannot increase an array’s size; if we declare a large size array and do not need to store that many elements, it is a waste of memory.
- To store their values, array elements require contiguous memory regions.
- Inserting an element into an array is slow since it requires shifting other elements to create room for the new element. Let’s imagine we have an array with the following elements: 40, 42, 55, 60, 74, 95, 109. If we want to add a new element 58 after the element with value 42, we must first shift all the elements after 42 to the right to make room for the new element.
Similarly, deleting an element from an array is a time-consuming operation since all elements after the deleted element must be relocated to the left. The Linked List overcomes these constraints by giving the following features:
- Linked lists support dynamic memory allocation, which means the compiler allocates memory at runtime, and we don’t have to provide the list size when declaring the linked list.
- Because elements are linked with each other using the reference component of the node, which provides the address of the next node in the list, linked list elements do not require contiguous memory locations.
- Linked list insert and delete operations are not performance-intensive. Adding and deleting an element from the linked list does not require element shifting. Instead, the pointer to the previous and next node must be changed.
Internally, how does LinkedList work?
Because a LinkedList functions as a dynamic array and we don’t have to define the size when we create it, the list’s size grows as we add and delete items dynamically. Furthermore, the elements are not kept in a continuous state. As a result, there is no need to expand the size.
The doubly linked list data structure is used to implement the LinkedList internally. The fundamental difference between a standard linked list and a doubly-linked list is that the latter has an extra pointer, usually referred to as the previous pointer, in addition to the next pointer and data found in the singly linked list.
Java LinkedList methods
LinkedList has several methods that conduct various actions on linked lists. In this article, we’ll look at four often used LinkedList Operators:
- Addition of elements
- Elements access
- Changing Elements
- Element removal
Addition of elements to a LinkedList
The add() method is used to add an element (node) to the end of a LinkedList. As an example,
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
class CodeMain {
public static void main(String[] args){
// creation of a citiesList linkedlist
LinkedList<String> citiesList = new LinkedList<>();
// add() method without the index parameter
citiesList.add("New York");
citiesList.add("Los Angeles");
citiesList.add("Manchester");
System.out.println("LinkedList: " + citiesList);
// add() method with the index parameter
citiesList.add(1, "Paris");
System.out.println("Updated LinkedList: " + citiesList);
}
}</pre>
</div>
We established a LinkedList named cities in the preceding example. In this example, we’ve used the add() method to add components to cities.
<div class="wp-block-codemirror-blocks-code-block code-block"> <pre>citiesList.add(1, "Paris");</pre> </div>
We’ve used the index number parameter in this case. It’s an optional argument determining where the new element should be placed.
Access to LinkedList elements
To access a LinkedList element, utilize the get() function of the LinkedList class. As an example,
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
class CodeMain {
public static void main(String[] args) {
LinkedList<String> compCompanies = new LinkedList<>();
// add elements in the linked list
compCompanies.add("Microsoft");
compCompanies.add("Apple");
compCompanies.add("Google");
System.out.println("LinkedList: " + compCompanies);
// get the element from the linked list
String strVal = compCompanies.get(1);
System.out.print(" The Item at index 1: " + strVal);
}
}</pre>
</div>
We used the get() method with parameter 1 in the preceding example. The procedure returns the element at index 1 in this case.
Changing a LinkedList’s Elements
The set() function of the LinkedList class is used to modify the LinkedList’s elements. As an example,
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
class CodeMain {
public static void main(String[] args) {
LinkedList<String> clubList = new LinkedList<>();
// add elements in the linked list
clubList.add("Chelsea");
clubList.add("Manchester City");
clubList.add("Liverpool");
languages.add("Manchester United");
System.out.println("The original club LinkedList is: " + clubList);
// changing the elements at the third index
languages.set(3, "Aston Villa");
System.out.println("The updated club LinkedList is : " + clubList);
}
}</pre>
</div>
Delete an item from a LinkedList
The LinkedList class’s remove() method is used to delete an element from the LinkedList. As an example,
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
class CodeMain {
public static void main(String[] args) {
LinkedList<String> fruitList = new LinkedList<>();
// add elements in LinkedList
fruitList.add("Java");
fruitList.add("Python");
fruitList.add("JavaScript");
fruitList.add("Kotlin");
System.out.println("LinkedList: " + fruitList);
// remove elements from index 1
String str = fruitList.remove(1);
System.out.println("Removed Element: " + str);
System.out.println("Updated LinkedList: " + fruitList);
}
}
</pre>
</div>
Additional Methods
- contains() – determines if the element is present in the LinkedList
- indexOf() – returns the index of the element’s first appearance.
- LastIndexOf() – yields the index of the element’s most recent occurrence
- clear() – removes all of the LinkedList’s elements
- iterator() -provides an iterator that is used to loop over the LinkedList.
Deque and Queue for LinkedList
Because the LinkedList class implements both the Queue and Deque interfaces, it can enforce functions from both. Here are a few of the most popular methods:
- addFirst() – adds the specified element to the linked list’s beginning.
- addLast() -adds the supplied entry to the linked list’s end
- getFirst() – responsible for returning the first element
- getLast() – responsible for returning the last element
- removeFirst() – tasked with removing the first item
- removeLast() – tasked with the removal of the last element
- peek() – yields the linked list’s first member (head).
- poll() – retrieves the first entry of the linked list and removes it
- offer() – adds the supplied entry to the linked list’s end
Example: Adding elements to a Java Linked List
The add(), addFirst(), and addLast() methods are used in the following example to add members to the LinkedList at the proper positions. There are several other helpful methods in the LinkedList class that I will describe at the end of this article.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>package com.codeunderscored;
import java.util.*;
public class CodeExampleJava{
public static void main(String args[]){
LinkedList<String> strList=new LinkedList<String>();
//Linked list components are being added.
strList.add("Green");
strList.add("White");
strList.add("Brown");
//Adding a second element to the first
strList.addFirst("Monroe");
//Incorporating a new element into the final position
strList.addLast("Spider");
//Incorporating an element into the third position
strList.add(2, "James");
//LinkedList Iteration
Iterator<String> newIterator=list.iterator();
while(newIterator.hasNext()){
System.out.println(newIterator.next());
}
}
}
</pre>
</div>
Example: LinkedList as Deque
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
import java.util.Deque;
class CodeMain {
public static void main(String[] args){
Deque<String> citiesList = new LinkedList<>();
// adding a new item to citiesList's beginning
citiesList.add("Manchester");
System.out.println("LinkedList: " + citiesList);
citiesList.addFirst("London");
System.out.println("LinkedList after addFirst(): " + citiesList);
// adding a new element to citiesList's end
citiesList.addLast("New York");
System.out.println("LinkedList after addLast(): " + citiesList);
// removing the first element from citiesList
citiesList.removeFirst();
System.out.println("LinkedList after removeFirst(): " + citiesList);
// removal of the last element from citiesList
citiesList.removeLast();
System.out.println("LinkedList after removeLast(): " + citiesList);
}
}</pre>
</div>
Example: Removing elements from a LinkedList
In the following example, we’ll look at a few typical removal methods in the LinkedList that are used to remove elements from specific points in the LinkedList. The separate tutorials provide a detailed description of these strategies and examples.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>package com.codeunderscored;
import java.util.*;
public class CodeExampleJava{
public static void main(String args[]){
LinkedList<String> nameList=new LinkedList<String>();
//Linked list components are being added.
nameList.add("Mike");
nameList.add("Joy");
nameList.add("White");
nameList.add("Monroe");
nameList.add("James");
//Getting rid of the first element
//Same as list.remove(0);
nameList.removeFirst();
//Removing the final component
nameList.removeLast();
//LinkedList Iteration
Iterator<String> newIterator=nameList .iterator();
while(newIterator .hasNext()){
System.out.print(newIterator .next()+" ");
}
//When the second element is removed, the index is reset to zero.
nameList.remove(1);
System.out.print("\nAfter removing second element: ");
//Re-iterating the LinkedList
Iterator<String> secondIterator=nameList .iterator();
while(secondIterator .hasNext()){
System.out.print(secondIterator .next()+" ");
}
}
}</pre>
</div>
Example: Iterating through LinkedList
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
class CodeMain {
public static void main(String[] args) {
// Creating a new linked list
LinkedList<String> flowerList = new LinkedList<>();
flowerList.add("Rose");
flowerList.add("Aster");
flowerList.add("Azalea");
System.out.println("The flowerList LinkedList is: " + flowerList);
// Using the forEach loop
System.out.println("Accessing the flowerList list elements:");
for(String fl: flowerList) {
System.out.print(fl);
System.out.print(", ");
}
}
}</pre>
</div>
Example: LinkedList in Java
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.*;
public class CodeLinkedList {
public static void main(String args[]) {
/* Declaration of a Linked List */
LinkedList<String> strLinkedList = new LinkedList<String>();
/*
* The function add(String Element) adds elements to the linked list.
*/
strLinkedList.add("IBM");
strLinkedList.add("Lenovo");
strLinkedList.add("Toshiba");
strLinkedList.add("Apple");
strLinkedList.add("Microsoft");
/*Display Linked List Content*/
System.out.println("The contents of the Linked List comprise of: " +strLinkedList);
/*Add First and Last Element*/
strLinkedList.addFirst("First Item");
strLinkedList.addLast("Last Item");
System.out.println("Content of the LinkedList once it has been added : " +strLinkedList);
/* This is how you get values and change them. */
Object firstvar = linkedlist.get(0);
System.out.println("The First element is: " +firstvar);
linkedlist.set(0, "The first point has been modified. ");
Object secondVar = linkedlist.get(0);
System.out.println("First element after update by set method: " +secondVar);
/*Remove first and last element*/
strLinkedList.removeFirst();
strLinkedList.removeLast();
System.out.println("LinkedList with the first and last elements removed : " +strLinkedList);
/* Toggle between adding and removing items from a place. */
strLinkedList.add(0, "Item that has recently been added ");
strLinkedList.remove(2);
System.out.println("The comprehensive Content is: " +strLinkedList);
}
}
</pre>
</div>
Example: Java LinkedList as Queue
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>import java.util.LinkedList;
import java.util.Queue;
class CodeMain {
public static void main(String[] args) {
Queue<String> fruitsList = new LinkedList<>();
// add elements
fruitsList.add("Mango");
fruitsList.add("Quava");
fruitsList.add("Apple");
System.out.println("LinkedList: " + fruitsList);
// accessing the fruitsList's first element
String str_one = fruitsList.peek();
System.out.println("Accessed Element: " + str_one);
// accessing and removing the fruitsList's first element
String second_string = fruitsList.poll();
System.out.println("Removed Element: " + second_string);
System.out.println("LinkedList after poll(): " + fruitsList);
// add a new fruits at the end of fruitsList
languages.offer("Banana");
System.out.println("LinkedList after offer(): " + fruitsList);
}
}
</pre>
</div>
Conclusion
This article has explained what a Linked List Data Structure is in Java and how to create, initialize, implement, traverse, reverse, and sort one.
A LinkedList is a data structure in Java that holds elements in a non-contiguous manner. It’s a data structure that’s linear. Each data item is referred to as a ‘Node,’ and each node has two parts: data and address. The address component of the LinkedList stores the link to the next node.
The Collection framework in java.util package includes a Linked List. This class implements the LinkedList data structure, a linear data structure in which the components are not kept in sequential order. Each element is a separate object having a data and address part. Pointers and addresses are used to connect the elements. Every element is referred to as a node.
They are preferable over arrays because of their dynamic nature and ease of insertions and removals. It also has some drawbacks, like unreachable nodes immediately; instead, we must start at the top and follow the link to the desired node.
