Java LinkedList and linked list implementation in java

Like An ArrayList in java, LinkedList class in java is also a famous data structure. But Java LinkedList doesn’t store elements in contiguous locations like ArrayList. In Java LinkedList, each element linked with each other using pointers. In this post, we will discuss LinkedList class in java and also discuss some example using LinkedList in java

Here is the table content of the article will we will cover this topic.
1. What is the Java LinkedList class?
2. Type of Linked List Structure?
i). Singly LinkedList
ii). Doubly LinkedList
3. Important points about Java LinkedList?
4. How To Create A Linked List In Java?
5. LinkedList implementation in java?
6. Why do we need a Linked List?
8. Java linked list methods?
7. How to do LinkedList insertion?
8. How to perform deletion in linked list?
9. How to get the element from LinkedList?
10. Traverse a linked list java?
11. Searching in linked list
12. How to convert linked list to array in java
13. How to perform linked list sorting?
14. How to remove duplicates from linked list?
15. Difference between ArrayList and LinkedList?

1. What is the Java LinkedList class

The LinkedList class in java is a part of the Java Collection Framework which implements the List interface, Deque interface, and extends the AbstractList class. It also implements the Cloneable and Serializable interface.

Java LinkedList is a part of the Collection framework that can store any number of elements/objects. Like an ArrayList class, LinkedList also has the dynamic size, it means its size automatically grows or shrinks when the object is added or removed.
The Java LinkedList class uses the LinkedList data structure. By use of linear data structure(LinkedList data structure) the element linked with other elements instead of contiguous locations. In LinkedList, each object has a data part and address part. The data part contains the data of the object and the address part stores the address of the other elements. The element of LinkedList is known as Node. Due to the linked structure, the insertion or deletion of elements is easy. We will discuss it later. But there is also a disadvantage like the elements can’t access directly. Instead, we need to start from the head and move forward until we reach a node that we want to access.

2. Type of Linked List Structure

i). Singly Linked List

In the above example, you can see each element has two-part, its data part, and a pointer to the location of the next element. It is singly linked list java

ii). Doubly Linked List

A doubly linked list a node has three parts that are previous node link, data part, and next node link. It is doubly linked list implementation in java.

LinkedList class uses the doubly linked list structure internally to maintain the element.

3. Important points about Java LinkedList

1. Like an ArrayList, A LinkedList can contain duplicate elements. Because each element stored as a separate node and there can be multiple nodes with the same data.
2. The LinkedList maintains the order of insertion. Each and every element stores the address of the next element.
3. The Head is the first element of the LinkedList and the last element is known as Tail. The Head object doesn’t have a previous address and Tail object doesn’t have next
3. A LinkedList can contain any number of null values.
4. LinkedList class is non synchronized.
5. LinkedList only constructs the empty list without any initial capacity. It means it doesn’t provide the default capacity.
6. LinkedList can’t be used for primitive types (like int, char, etc).
7. LinkedList doesn’t allows us to randomly access the list. Because it doesn’t implement the RandomAccess interface.
8. LinkedList is fast in manipulation because no shifting needs to occur.

4. How To Create A Linked List In Java?

To create a Java LinkedList we have two constructors one is default constructor and another is parameterized constructor. The LinkedList class supports the generic concept, so we provide the data type that type of objects we want to store. Here we have two constructors to create linked list java
1. LinkedList()
2. LinkedList(Collection c)

LinkedList()

It is a default constructor of the LinkedList class. It is used to create an empty LinkedList. It doesn’t provide the initial capacity to LinkedList. A LinkedList doesn’t have default capacity because it doesn’t make sense to create empty links. A LinkedList makes its links when we add the element.

LinkedList<E> NameOfLinkedList =  new LinkedList<E>();

Where, E represents the type of elements in LinkedList.

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

import java.util.LinkedList;
public class ExampleOfLinkedList 
{
    public static void main(String[] args) 
    {
        LinkedList<String> listOfNames = new LinkedList<String>();
        listOfNames.add("JAVA");
        listOfNames.add("GOAL");
        listOfNames.add("Webiste");
        listOfNames.add("Java");
        listOfNames.add("Learning");
        
        System.out.println("Elements:" + listOfNames);
    }
}

Output: Elements:[JAVA, GOAL, Webiste, Java, Learning]

LinkedList(Collection c)

In java LinkedList class has a parameterized constructor that is used to create a LinkedList containing the elements in the specified collection. The LinkedList maintains the order of elements that comes from a specified collection.

LinkedList<E> NameOfLinkedList =  new LinkedList <E>(collectionName c);

Where E represents the type of elements in LinkedList.
c, Where is the collection that we want to place in LinkedList.
throw NullPointerException, If specified collection is null

  LinkedList<String> listOfNames2 =  new LinkedList <String>( listOfNames);

import java.util.LinkedList;
public class ExampleOfLinkedList 
{
  public static void main(String[] args) 
  {
    LinkedList<String> firstList = new LinkedList<String>();
    firstList.add("JAVA");
    firstList.add("GOAL");
    firstList.add("Website");
        
    LinkedList<String> secondList = new LinkedList<String>(firstList);
    secondList.add("Learning");
    
    System.out.println("Element from firstList: " + firstList);
    System.out.println("Element from secondList: " + secondList);
   }
}

Output: Element from firstList: [JAVA, GOAL, Website]
Element from secondList: [JAVA, GOAL, Website, Learning]

5. LinkedList implementation in java

In the above sections, we have seen how to create a LinkedList and it differs from other collections. Let’s see how we can use the LinkedList java and the LinkedList implementation in java. Let’s see the LinkedList in java program or linked list program in java

import java.util.LinkedList;
public class ExampleOfLinkedList 
{
  public static void main(String[] args) 
  {
	// Creating a empty LinkedList  
    LinkedList<String> firstList = new LinkedList<String>();
    
    // Adding object in LinkedList
    firstList.add("Java");
    firstList.add("Goal");
    firstList.add("Website");
    
    // Removing object from LinkedList
    firstList.remove("Goal");
    
    System.out.println("Elements: "+ firstList);
   }
}

Output: Elements: [Java, Website]

As we know LinkedList uses the doubly LinkedList to maintain the data. Let’s see how does add operation and remove operation works.

firstList.add("Java");

firstList.add("Goal");

firstList.add("Website");

firstList.remove("Goal");

6. Why do we need a Linked List?

As we know Array and ArrayList are two other popular data structure. Both can store objects in continuous memory allocation, but LinkedList data structure has some different implementation.

1) The Size of the array is fixed that must be decide when we create an array. Many times, we can’t predict the number of elements in advance.
But ArrayList has dynamic size that can increase or decrease during manipulation.

A LinkedList has also dynamic size but it doesn’t waste the space as like ArrayList. Because an ArrayList creates a new object of ArrayList and copy all the content from old object of ArrayList.

2) Array and ArrayList stores in contiguous memory locations to store their values. So, if we add or remove an element from a particular index, it shifts all the elements to fill the position and this affects the performance

Suppose we have an Array or ArrayList or 100 elements. Now we want to add an element of 50th position, when we call add(index i, element e) method it shifts all the elements after the 49th position to their right to make space for the new element.
A LinkedList is faster than ArrayList to perform manipulation operation. Because in LinkedList if we add or remove any element then JVM just makes or breaks the links internally nodes. We will discuss it later.