Skip to main content

LinkedList in Java

LinkedList in Java

In this article, we are going to learn about one more class that implements a linear data structure which is LinkedList in java (do not confuse this article with Linked List Data Structure, this article is all about the LinkedList class provided by the Java Collection Framework). We all have encountered a few instances where we need to use a Linked-List data structure so it is important to understand a pre-developed class provided by the Java Collection Framework that implements this data structure. In this post, we start with what is LinkedList in Java, its hierarchy, methods provided by the LinkedList in java and, etc.


What is LinkedList in Java?

Before going to study LinkedList class, let's first revise the basic definition of the linked list data structure.
"Linked List data structure is a type of linear data structure that stores a group of nodes, where each node contains the data and a link pointing to the next node of the list. Each node instantiated at a distinct memory location and connected through the link pointers.
In contrast to the Linked List, the doubly linked list is the type of linked list where each contains two links one for the previous node and the other for the next node in the list."
LinkedList in java is used to store and retrieve elements like a Linked-List data structure. To provide the support of the linked list data structure, the Doubly-Linked-List is used as the internal data structure and all the operations are implemented as to perform on this Doubly-Linked-List.
LinkedList is part of the Java Collection Framework. It is defined in java.util package and implements java.util.List interface which provides functionalities to perform basic operation like to store, retrieve data from the list and etc.
Each element (node) of this LinkedList contains three-part: one is for the data part and two for the node pointers (prev and next pointers).
LinkedList in java

Important points to remember about the LinkedList in java

  • LinkedList is a Collection and maintain linear data structure (by using doubly-linked-list), all the operations are implemented as to be performed on doubly-linked-list like add(),remove(),get() etc.
  • An index based operation iterate list from start to end, whichever is close to the specified index.
  • LinkedList is not synchronized (i.e., not thread-safe). To use LinkedList in the multithreaded environment we need to make it synchronized externally.
  • Duplicity is allowed i.e., LinkedList in java can contain duplicate elements.
  • Linked in java maintains insertion order.
  • The Iterator of LinkedList is fail-fast i.e., any modification onto the structure of the internal doubly linked list during the iteration causes ConcurrentModificationException to be raised.

Hierarchy of the LinkedList in java

Declaration of LinkedList
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
     ----------------
}

AbstractSequentialList<E>

The AbstractSequentialList<E> provides a basic and abstract implementation of the List Interface to the LinkedList. It is oppose to the AbstractList<E> as it provides the sequential access whereas AbstractList<E> provides the random access.

Deque<E>

The Deque<E> interface is a linear collection and provides the functionality to access the LinkedList from both ends.

Why Cloneable?

"Cloneable is a marker interface and it is a part of java.lang package. If Any class implements this interface then it can call the clone() method of Object class using super keyword i.e., super.clone(); through any method or any constructor. Without this marker interface, if any class invokes the i.e., super.clone(); then java.lang.CloneNotSupportedException will be raised."
LinkedList in Java provides an overrode clone() method that internally calls the actual clone() method of Object class. So, LinkedList needs to implement this marker interface.
Note: The clone() method of Object class is used to create a cloned object.

Why Serializable?

"Serializable is a marker interface and it is a part of java.io package. If Any class implements this interface then the class can be serialized or deserialized. Serialization is a process in which an object is converted into the byte stream and Deserialization is the reverse of serialization i.e., byte stream to java object. Serialization helps us to store and retrieve objects from and to files, databases, networks, etc. The only class marked with the Serializable interface can be serialized or deserialized."
LinkedList in Java often need to store and retrieve the object from the files, databases, etc. That's why LinkedList is implemented as Serializable.

Internal Working of LinkedList in Java

For a better understanding of LinkedList in java, we should also understand the internal working of LinkedList. As we studied earlier, the LinkedList class is internally backed by the doubly-linked-list. If you look into the source code of LinkedList class, you will notice that two non-static variables defined into it as:
Code Snippet of LinkedList
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
     ----------------
     ----------------
     transient Node<E> first;
     transient Node<E> last;
     ----------------
     ----------------
}
To maintain a doubly-linked-list, two-pointer variables are "first" and "last" need to be maintained which point at the beginning and ending of Doubly-Linked-List respectively. The "first" pointer variable is used to traverse the doubly-linked-list from the beginning and the "last" pointer variable is used to traverse from the end.
Each node consists of three parts: one part for the data and the other two parts are the node pointers (prev and next pointers) which is used to store the location of previous and next node respectively, as we know in case of linked list node are created at the separate location and connected by the pointer variables.
Just have a look at the pictorial representation of the doubly-linked-list:
LinkedList in java
Random placement of nodes represents the distinct memory location allotted to the node at the time of node creation.

How to instantiated LinkedList in java?

Till now, we have studied LinkedList in java theoretically. Now move on to some actual programming in java. It is good to start with "how to instantiate the LinkedList in java?". There are we have two constructors through which we can create an instance of LinkedList.

Using Default Constructor

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

Using Constructor which require another Collection:

A LinkedList in Java can be created from another Collection and Collection can be a List, Set, etc.
ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("Programming In Java");
arrayList.add("Learn ReactJs");
arrayList.add("Introduction to Algorithms");
arrayList.add("Data Structures");
LinkedList<String> linkedList = new LinkedList<String>(arrayList);

How to add elements into LinkedList in java?

We have several ways to add elements into the LinkedList class, there are exists plenty of methods to add data into the LinkedList and we can use any one of them according to our needs. Have a look at those various methods:
  • add(): add elements at the last position
  • addFirst(): add elements at the first position
  • addLast(): add elements at the last position or same as add() method
  • add(index, element): insert the element at the specified position

Java LinkedList Example 1: variant of add() method in LinkedList

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

System.out.println("> add(element) method");
bookList.add("Programming In Java");
bookList.add("Learn ReactJs");
System.out.println(bookList);
System.out.println();

System.out.println("> addFirst(element) method");
bookList.addFirst("Computer Networks");
bookList.addFirst("Introduction to Database");
System.out.println(bookList);
System.out.println();

System.out.println("> addLast(element) method");
bookList.addLast("A Guide to Kafka");
System.out.println(bookList);
System.out.println();

System.out.println("> add(index, element) method");
bookList.add(3 , "Basics of Microservice");
bookList.add(3 , "Mastering Algorithms");
System.out.println(bookList);
Output
> add(element) method
[Programming In Java, Learn ReactJs]

> addFirst(element) method
[Introduction to Database, Computer Networks, Programming In Java, Learn ReactJs]

> addLast(element) method
[Introduction to Database, Computer Networks, Programming In Java, Learn ReactJs, A Guide to Kafka]

> add(index, element) method
[Introduction to Database, Computer Networks, Programming In Java, Basics of Microservice, Learn ReactJs, Mastering Algorithms, A Guide to Kafka]

How to iterate LinkedList in Java?

In java, there are exist plenty of approaches to iterate LinkedList in Java. Let's look at a few of them which come in our day-to-day programming practices.

Using for-each loop

Java LinkedList Example 2: Iterate the LinkedList using for each loop

for(String element : bookList) {
      System.out.println(element);
}
Output
Introduction to Database
Computer Networks
Programming In Java
Basics of Microservice
Learn ReactJs
Mastering Algorithms
A Guide to Kafka

Using Iterators

Java LinkedList Example 3: Iterate the LinkedList using iterators

Iterator<String> iterator = bookList.iterator();
while(iterator.hasNext()){
      String element = iterator.next();
      System.out.println(element);
}
Output
Introduction to Database
Computer Networks
Programming In Java
Basics of Microservice
Learn ReactJs
Mastering Algorithms
A Guide to Kafka

Using forEach() method

Java LinkedList Example 4: Iterate the LinkedList using forEach() method

// Using Lambda Expression
bookList.forEach(element -> System.out.println(element));
// Or, Using Method Reference 
bookList.forEach(System.out::println);
Output
Introduction to Database
Computer Networks
Programming In Java
Basics of Microservice
Learn ReactJs
Mastering Algorithms
A Guide to Kafka

Iterate in reverse order

As we know that LinkedList in java internally backed by the doubly-linked-list, therefore we can iterate also in reverse order. For that LinkedList class provides a method called descendingIterator() method. This method returns an instance of iterator and starts traversing the LinkedList from the "last" pointer and move towards the "first" pointer.

Java LinkedList Example 5: Iterate the LinkedList in reverse order

Iterator<String> iterator = bookList.descendingIterator();
while(iterator.hasNext()){
      String element = iterator.next();
      System.out.println(element);
}
Output
A Guide to Kafka
Mastering Algorithms
Learn ReactJs
Basics of Microservice
Programming In Java
Computer Networks
Introduction to Database

How to get elements from the LinkedList in java?

Java LinkedList Example 6: Get the data from the LinkedList

// get the first element of the list
String firstElement = bookList.getFirst();
System.out.println("First Element: " + firstElement);
  
// get the last element of the list
String lastElement = bookList.getLast();
System.out.println("Last Element: " + lastElement);
  
// get the 3rd element from the list (index is 0th based)
String thirdElement = bookList.get(2 );
System.out.println("Third Element: " + thirdElement);
Output
First Element: Introduction to Database
Last Element: A Guide to Kafka
Third Element: Programming In Java
Note: When using the get(index) method, from which side of the list will be traversed is dependent upon the index is closer to which pointer first or last. If the index value is close to the first pointer then traversing of the list starts from the beginning of the list, otherwise traversing starts from the ending.

How to get the index of given elements from the LinkedList in java?

In the previous section, we have learned how to get the first-n-last element and element-by-index from the LinkedList. In this section, we will read how to get the index of a given element. For this purpose, LinkedList provides two methods are:
  • indexOf(): returns the index of the first occurrence of the given element. Internally, traversing starts from the "first" pointer and move to another node using the "next" pointer till the given element is not found.
  • lastIndexOf(): returns the index of the last occurrence of the given element. Internally, traversing starts from the "last" pointer and move to another node using the "prev" pointer till the given element is not found.
Let's understand how to use them:

Java LinkedList Example 7: Get the index of the given element from the LinkedList

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

bookList.add("Programming In Java");
bookList.add("Learn ReactJs");
bookList.add("Computer Networks");
bookList.add("Introduction to Database");
bookList.add("A Guide to Kafka");
bookList.add("Computer Networks");
bookList.add("Mastering Algorithms");

System.out.println(bookList);

int indexOfComputerNetworks = bookList.indexOf("Computer Networks");
System.out.println("Index of Computer Networks: " + indexOfComputerNetworks);

int lastIndexOfComputerNetworks = bookList.lastIndexOf("Computer Networks");
System.out.println("Last Index of Computer Networks: " + lastIndexOfComputerNetworks);
Output
[Programming In Java, Learn ReactJs, Computer Networks, Introduction to Database, A Guide to Kafka, Computer Networks, Mastering Algorithms]
Index of Computer Networks: 2
Last Index of Computer Networks: 5

How to remove elements from the LinkedList in java?

The linked list data structure is the best data structure when it comes to removing elements as we just need to delete the specified element and connect the previous node to the next node and it becomes very simple in case of doubly-linked-list. The LinkedList class provides a few methods to remove elements.
  • remove() or removeFirstOccurrence(): both methods are used to remove the first occurrence of the specified element. Internally, traversing starts from the "first" pointer and move to another node using the "next" pointer till the given element is not found.
  • removeFirst(): removes the first element.
  • removeLastOccurrence(): used to remove the last occurrence of the specified element. Internally, traversing starts from the "last" pointer and move to another node using the "prev" pointer till the given element is not found.
  • removeLast(): removes the last element.
  • removeIf(): method used to remove all those elements which satisfy the given predicate.

Java LinkedList Example 8: remove elements from the LinkedList

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

bookList.add("Programming In Java");
bookList.add("Learn ReactJs");
bookList.add("Computer Networks");
bookList.add("Introduction to Database");
bookList.add("A Guide to Kafka");
bookList.add("Computer Networks");
bookList.add("Mastering Algorithms");

System.out.println(bookList);
System.out.println();

System.out.println("> remove the first occurrence of Computer Networks");
bookList.remove("Computer Networks");
System.out.println(bookList);
System.out.println();

System.out.println("> remove the last occurrence of Computer Networks");
bookList.removeLastOccurence("Computer Networks");
System.out.println(bookList);
System.out.println();

System.out.println("> remove the first element of the list");
bookList.removeFirst();
System.out.println(bookList);
System.out.println();

System.out.println("> remove the last element of the list");
bookList.removeLast();
System.out.println(bookList);
System.out.println();

System.out.println("> removes all the element contains 'Database'");
bookList.removeIf(element -> element.contains("Database"));
System.out.println(bookList);
Output
[Programming In Java, Learn ReactJs, Computer Networks, Introduction to Database, A Guide to Kafka, Computer Networks, Mastering Algorithms]

> remove the first occurrence of Computer Networks
[Programming In Java, Learn ReactJs, Introduction to Database, A Guide to Kafka, Computer Networks, Mastering Algorithms]

> remove the last occurrence of Computer Networks
[Programming In Java, Learn ReactJs, Introduction to Database, A Guide to Kafka, Mastering Algorithms]

> remove the first element of the list
[Learn ReactJs, Introduction to Database, A Guide to Kafka, Mastering Algorithms]

> remove the last element of the list
[Learn ReactJs, Introduction to Database, A Guide to Kafka]

> removes all the element contains 'Database'
[Learn ReactJs, A Guide to Kafka]

Comments

Popular posts from this blog

How HashMap works internally in java

How Hashmap works Internally in Java In this article, we are going to see how HashMap internally works in java. Also, we will have a look at what Java 8 made changes on the internal working of Hashmap to make it faster. What is Hashmap and Hashing in java? How Hashmap works Internally in Java is majorly dependent upon the Hashing Principle. So, Before going to learn how HashMap works internally in java, lets first understand what is HashMap and hashing. HashMap : A HashMap is a map used to store mappings of key-value pairs. Also, it works on the Principle of Hashing. To know more about the HashMap, visit this article: HashMap in Java Hashing Principle : Simply, Hashing is a method used to produce an integer value from an object and this integer value known as the hash value. In HashMap, the key object is used for Hashing.
Internal Struture of the HashMap in java For internal working of HashMap, HashMap maintains an array of bucket, each bucket is a linked-list and linked list is a li…

HashMap in Java

HashMap in Java In this article, we are going to learn about the most important class of Java known as HashMap. HashMap in java is the most used map interface and it is used in our regular or day-to-day programming practices.
What is HashMap in java? Lets first start with basic definition of HashMap,
HashMap is a map which store key-value pair, where each key is mapped with a value.
HashMap defined in java.util package and implements map interface which provides functionalities to perform basic operation like store, retrieve, size of the map etc. It is a part of Java Collection Framework. Time complexity of HashMap in Java? : Time complexity to store and retrieve data from the HashMap is O(1) in the Best Case. But it can be O(n) in the worst case and after the changes made in Java 8 the worst case time complexity can be O(log n) atmost. Internal working of HashMap in java HashMap maintains an array of the buckets, where each bucket is a linked-list and the linked list is a list of…

ArrayList in Java

ArrayList in Java In this article, we are going to discuss ArrayList in Java. ArrayList is a class from the Java Collection Framework and widely in our programs. We use ArrayList as a substitute for the array. So, it is important to know ArrayList in detail. We are going to see what is ArrayList in Java, how we can create the instance of ArrayList and the methods provided by the ArrayList in Java.

If you already familiar to ArrayList, you may learn common programs related to ArrayList.
Table of ContentsWhat is ArrayList in Java?Hierarchy of the ArrayList in java?How to create objects of ArrayList in Java?How to create an ArrayList of Custom Objects?How to iterate ArrayList in Java?How to get the elements by index from ArrayList in Java?How to check whether an elements is stored in the ArrayList in Java?How to remove elements from the ArrayList in Java?Few more methods of ArrayList in Java?
What is ArrayList in Java? ArrayList in Java is a List in which we can store and retrieve elemen…