Linked List

Introduction

The LinkedListclass is a collection that can contain many objects of the same type, just like the ArrayList.

The LinkedList class has all of the same methods as the ArrayList class because they both implement the List interface. This means you can add items, change items, remove items, and clear the list similarly.

However, while the ArrayList class and the LinkedList class can be used in the same way, they are built very differently. 

The important points about Java LinkedList are:

• Java LinkedList class uses a doubly linked list to store the elements. 

• Java LinkedList class can contain duplicate elements.

• Java LinkedList class maintains insertion order.

• Java LinkedList class is non-synchronized.

• In the Java LinkedList class, manipulation is fast because no shifting needs to occur.

• Java LinkedList class can be used as a list, stack, or queue.

How the ArrayList works

The ArrayList class has a regular array inside it. When an element is added, it is placed into the array. If the array is not big enough, a new, larger array is created to replace the old one, and the old one is removed.

How the LinkedList works

The LinkedList stores its items in "containers." The list has a link to the first container and each container has a link to the next container. To add an element to the list, the element is placed into a new container and linked to one of the other containers in the list.

When To Use

Use an ArrayList for storing and accessing data, and LinkedList to manipulate data.

LinkedList Methods

For many cases, the ArrayList is more efficient as it is common to need access to random items in the list, but the LinkedList provides several methods to do certain operations more efficiently:

• addFirst() - Adds an item to the beginning of the list.

• addLast() - Add an item to the end of the list

• removeFirst() - Remove an item from the beginning of the list.

• removeLast() - Remove an item from the end of the list

• getFirst() - Get the item at the beginning of the list

• getLast() - Get the item at the end of the list

Create LinkedList

Example: Cars3

import java.util.*;  

public class Cars3{  

public static void main(String args[]){  

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

al.add("Volvo");  

al.add("BMW");  

al.add("Ford");  

al.add("Mazda");  

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

while(itr.hasNext()){  

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

}  

}  

}  

The output will be:

Volvo

BMW

Ford

Mazda

LinkedList Methods

Example:

import java.util.*; 

public class StudentList{ 

public static void main(String args[]){ 

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

// initial list

student.add("Rizq"); 

student.add("Luth"); 

student.add("Hud"); 

student.add("Eidris"); 

student.add("Adam"); 

System.out.println("Initial list: " + student); 

        //Removing specific element from arraylist 

student.remove("Adam"); 

        System.out.println("After removed-1: " + student);

       //Removing element on the basis of specific position 

       student.remove(0); 

       System.out.println("After removed-2: "+student);  

       // Create second linked list

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

       newStudent.add("Ismael"); 

       newStudent.add("Ibrahim"); 

       System.out.println("newStudent list : " + newStudent);  

       // Adding new elements to student Linkedlist

       student.addAll(newStudent); 

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

       //Removing all the new elements from arraylist 

       student.removeAll(newStudent); 

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

       //Removing first element from the list 

       student.removeFirst(); 

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

       //Removing first element from the list 

       student.removeLast(); 

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

} 

} 

Output:

Initial list: [Rizq, Luth, Hud, Eidris, Adam]

After removed-1: [Rizq, Luth, Hud, Eidris]

After removed-2: [Luth, Hud, Eidris]

newStudent list : [Ismael, Ibrahim]

Updated list : [Luth, Hud, Eidris, Ismael, Ibrahim]

After invoking removeAll() method: [Luth, Hud, Eidris]

After invoking removeFirst() method: [Hud, Eidris]

After invoking removeLast() method: [Hud]

Java LinkedList Example to reverse a list of elements

Example:

import java.util.*; 

public class ReverseOrder{ 

public static void main(String args[]){ 

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

color.add("Red"); 

color.add("Blue"); 

color.add("Yellow"); 

System.out.println("Initial list: " + color); 

//Traversing the list of elements in reverse order 

Iterator<String> i = color.descendingIterator(); 

while(i.hasNext())  { 

System.out.print(i.next() + " "); 

} 

} 

} 

Output:

Initial list: [Red, Blue, Yellow]

Yellow Blue Red