Java LinkedList

In Java LinkedList is a class which is available in java.util package. LinkedList class uses a doubly linked list to store the elements. It inherits the AbstractList class and implements List and Deque interfaces.

There are some key points to remember about LinkedList:

  1. ◈ LinkedList class can contain duplicate elements.
  2. ◈ LinkedList class maintains insertion order.
  3. ◈ LinkedList class is non synchronized.
  4. ◈ LinkedList class, manipulation is fast because no shifting needs to occur.
  5. ◈ Java LinkedList class can be used as a list, stack or queue.

Each element in a linked list is known as a node. It consists of 3 fields:

  1. ◈ Prev - stores an address of the previous element in the list. It is null for the first element
  2. ◈ Next - stores an address of the next element in the list. It is null for the last element
  3. ◈ Data - stores the actual data


Working of a Java LinkedList

Elements in linked lists are not stored in sequence. Instead, they are scattered and connected through links (Prev and Next).


Explanation:

  1. ◈ Bus - it is the first element that holds null as previous address and the address of Car as the next address
  2. ◈ Car - it is the second element that holds an address of Bus as the previous address and the address of Bike as the next address
  3. ◈ Bike - it is the last element that holds the address of Car as the previous address and null as the next element

Creating an LinkedList

                        List list = new LinkedList();
                                (or)
                        LinkedList linkedList = new LinkedList();

In above we have created an LinkedList. Inside this LinkedList object we can store multiple types of elements.

Creating an LinkedList of a specific type

                        // create Integer type LinkedList
                        LinkedList<Integer> linkedList = new LinkedList<Integer>();

                        // create String type linkedList
                        LinkedList<String> linkedList = new LinkedList<String>();

In above we have created an LinkedList of two different types integer and string.

  1. ◈ If we create a LinkedList using Integer type then we can store only Integer type of element.
  2. ◈ If we create a LinkedList using String type then we can store only String type of element.

LinkedList constructos

In order to create a LinkedList, we need to create an object of the LinkedList class. The LinkedList class consists of various constructors that allow the possible creation of the list. The following are the constructors available in this class:

Constructor Description Example
LinkedList() This constructor is used to create an empty linked list LinkedList ll = new LinkedList();
LinkedList(Collection C) This constructor is used to create an ordered list that contains all the elements of a specified collection, as returned by the collection’s iterator LinkedList ll = new LinkedList(C);
Methods of LinkedList class

There are some basic commonly used methods are:

Method Name Description
add() This method is use to add the elements to the LinkedList.
get() This method is use to fetch the elements from the LinkedList.
set() This method is use to update the elements in an LinkedList.
remove() This method is use to remove an elements from the LinkedList.
contains() checks if the LinkedList contains the element
indexOf() returns the index of the first occurrence of the element.
lastIndexOf() returns the index of the last occurrence of the element.
clear() removes all the elements of the LinkedList.
iterator() returns an iterator to iterate over LinkedList.
LinkedList as Deque and Queue

Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:

Method Name Description
addFirst() adds the specified element at the beginning of the linked list.
addLast() adds the specified element at the end of the linked list.
getFirst() returns the first element.
getLast() returns the last element.
removeFirst() removes the first element.
removeLast() removes the last element.
peek() returns the first element (head) of the linked list.
poll() returns and removes the first element from the linked list.
offer() adds the specified element at the end of the linked list.
Basic Operations on LinkedList

The LinkedList class provides various methods to perform different operations on LinkedLists. We will look at some commonly used LinkedList operations.

  1. ▪ Add elements
  2. ▪ Access elements
  3. ▪ Change elements
  4. ▪ Remove elements

Add elements:

To add a single element to the LinkedList, we use the add() method of the LinkedList class. For example,


                        import java.util.LinkedList;

                        pubic class LinkedListAddExample {
                        public static void main(String[] args){
                            // create linkedlist
                            LinkedList<String> animals = new LinkedList<String>();

                            // add() method without the index parameter
                            animals.add("Bus");
                            animals.add("Car");
                            animals.add("Bike");
                            System.out.println("LinkedList: " + animals);

                            // add() method with the index parameter
                            animals.add(1, "Cycle");
                            System.out.println("Updated LinkedList: " + animals);
                        }
                        }
Access elements:

The get() method of the LinkedList class is used to access an element from the LinkedList. For example,


                        import java.util.LinkedList;

                        public class LinkedListAccessExample {
                        public static void main(String[] args) {
                            LinkedList<String> languages = new LinkedList<String>();

                            // add elements in the linked list
                            languages.add("Python");
                            languages.add("Java");
                            languages.add("JavaScript");
                            System.out.println("LinkedList: " + languages);

                            // get the element from the linked list
                            String str = languages.get(1);
                            System.out.print("Element at index 1: " + str);
                        }
                        }
Change elements:

The set() method of LinkedList class is used to change elements of the LinkedList. For example,


                        import java.util.LinkedList;

                        public class LinkedListChangeExample {
                        public static void main(String[] args) {
                            LinkedList<String> languages = new LinkedList<String>();

                            // add elements in the linked list
                            languages.add("Java");
                            languages.add("Python");
                            languages.add("JavaScript");
                            languages.add("Java");
                            System.out.println("LinkedList: " + languages);

                            // change elements at index 3
                            languages.set(3, "Kotlin");
                            System.out.println("Updated LinkedList: " + languages);
                        }
                        }
Remove elements:

The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,


                        import java.util.LinkedList;

                        public class LinkedListRemoveExample {
                            public static void main(String[] args) {
                                LinkedList<String> languages = new LinkedList<String>();

                                // add elements in LinkedList
                                languages.add("Java");
                                languages.add("Python");
                                languages.add("JavaScript");
                                languages.add("Kotlin");
                                System.out.println("LinkedList: " + languages);

                                // remove elements from index 1
                                String str = languages.remove(1);
                                System.out.println("Removed Element: " + str);

                                System.out.println("Updated LinkedList: " + languages);
                            }
                        }
Example: Java LinkedList as Queue

                        import java.util.LinkedList;
                        import java.util.Queue;

                        public class LinkedListQueueExample {
                            public static void main(String[] args) {
                                Queue<String> languages = new LinkedList<String>();

                                // add elements
                                languages.add("Python");
                                languages.add("Java");
                                languages.add("C");
                                System.out.println("LinkedList: " + languages);

                                // access the first element
                                String str1 = languages.peek();
                                System.out.println("Accessed Element: " + str1);

                                // access and remove the first element
                                String str2 = languages.poll();
                                System.out.println("Removed Element: " + str2);
                                System.out.println("LinkedList after poll(): " + languages);

                                // add element at the end
                                languages.offer("Swift");
                                System.out.println("LinkedList after offer(): " + languages);
                            }
                        }
Example: LinkedList as Deque

                        import java.util.LinkedList;
                        import java.util.Deque;

                        public class LinkedListDeque {
                            public static void main(String[] args){
                                Deque<String> animals = new LinkedList<String>();

                                // add element at the beginning
                                animals.add("Cow");
                                System.out.println("LinkedList: " + animals);

                                animals.addFirst("Dog");
                                System.out.println("LinkedList after addFirst(): " + animals);

                                // add elements at the end
                                animals.addLast("Zebra");
                                System.out.println("LinkedList after addLast(): " + animals);

                                // remove the first element
                                animals.removeFirst();
                                System.out.println("LinkedList after removeFirst(): " + animals);

                                // remove the last element
                                animals.removeLast();
                                System.out.println("LinkedList after removeLast(): " + animals);
                            }
                        }
Differences between LinkedList and ArrayList:
LinkedList ArrayList
LinkedList implements List, Queue, and Deque interfaces. ArrayList implements List interface.
LinkedList stores 3 values (previous address, data, and next address) in a single position. ArrayList stores a single value in a single position.
LinkedList provides the doubly-linked list implementation. ArrayList provides a resizable array implementation.
In LinkedList whenever an element is added, prev and next address are changed. In ArrayList whenever an element is added, all elements after that position are shifted.
In LinkedList to access an element, we need to iterate from the beginning to the element. ArrayList can randomly access elements using indexes.