LinkedList in Java
FREE
Overview
A Linked List is a linear data structure, in which elements are represented as objects and stored in non-contiguous memory locations. Linked List in Java can be implemented using a custom class or using the Collection framework present in java.util package. This LinkedList class implements the List, Queue, and Deque interfaces.
Introduction to Linked List in Java
Many times it is possible that we don't know the number of elements that will be stored in the array or we don't have enough contiguous memory for initializing the array. Linked List saves us in both cases.
A Linked List is a linear data structure in which each element is stored as an object in non-contiguous memory locations. Each object stores two things, one is the data (value) and the second is the memory location of the next or previous or both the next and previous object's address. As the name indicates Linked List, means multiple objects are linked together to act as a linear data structure.
The first object of the Linked List is known as the head and the last object is known as the tail of the Linked List.
Based on the memory location stored in the object, Linked List is of two types:
- Singly Linked List/ Normal Linked List: Each object stores the data and the memory location of the next or previous object. Hence in a singly linked list traversal is only possible in a single direction that is head to tail, if the object contains the memory location of the next object. Or tail to head, if the object contains the memory location of the previous object.
In the above figure, each object stores two things, data and the location of the next object. The tail of the Linked List stores NULL as the location of the next object to represent that this is the last element of the Linked List.
- Doubly Linked List: As the name indicates, doubly means the linked list which can be traversed in both ways head to tail and tail to head. For this, each object stores the data and memory location of the next object as well as the memory location of the previous object.
In the above figure, each object stores the data, the location of the next thing, and the location of the previous object. For the head location of the previous object is NULL and for the tail, the location of the next object is NULL.
Creating a Linked List in Java
By now you must have understood that we need an object for each element. So before we initialize the object, we must declare a class. Let's name this class Node and this class will have two data members, one is the data and the second one is the location of the next node.
Here, we have declared a class with the name "Node" having two data members one is the data which we have to store, in the above case our data is an integer and the second is the location of next node. Also in the class, we are having a parameterized constructor which initializes the data member "data". By default, the data member "next" is initialized to NULL.
Declaring a class whenever we want to use Linked List is time-consuming, So Java provides us with a class "LinkedList". It is a part of the Collection Framework present in java.util package. This class is a doubly linked list implementation of the Linked List data structure, So we can traverse in both directions.
Hierarchy of LinkedList class in Java
LinkedList class belongs to java.util package and extends the AbstractSequentialList class and implements the List and Deque interfaces.
How Does LinkedList Class in Java works Internally?
Unlike arrays where we have to specify the size of the array before declaration. In Linked List, we don't have to specify the size of the list as a linked list is a dynamic data structure and it automatically changes size when an element is added or removed. Also, the nodes of the linked list are not stored in a contiguous memory location, they are linked to each other with the help of next and previous pointers.
Constructors in the Linked List
When we create a linked list, we first have to create an object that will store the data and the next and previous pointers. LinkedList class in java comes with the following constructors:
LinkedList() - This default constructor is used to create an empty linked list. Suppose we are creating a linked list with the name "ll", then the linked list can be created as:
LinkedList(Collection c) - This parameterized constructor is used to create an ordered list containing elements of the specified collection. The order of the linked list is returned by the collection's iterator. Suppose we are creating a linked list with the name "ll" which will contain the elements of collection c, then the linked list can be created as:
Methods for Linked List in Java
| Method | Description |
|---|---|
| add(int index, E element) | This method is used to insert the element in a specified position in the list. |
| add(E element) | This method appends the element to the end of the list. |
| addAll(int index, Collection c) | This method is used to insert all the elements of the Collection "c" starting from the specified index. |
| addAll(Collection c) | This method appends all the elements of the Collection "c" to the end of the list. |
| addFirst(E element) | This method inserts the desired element in the beginning of the list. |
| addLast(E element) | This method appends the desired element in the end of the list. |
| clear() | This method is used to clear all the elements from the list. |
| clone() | This method returns a shallow copy of the list. |
| contains(Object x) | This method will return true if the specified element is present in the list. |
| descendingIterator() | This method returns an iterator over the elements in the reversed sequential order in deque. |
| element() | This method is used to retrieve the first element or head of the list. |
| get(int index) | This method is used to return the element present at the specified position. |
| getFirst() | This method is used to return the first element of the list. |
| getLast() | This method is used to return the last element of the list. |
| indexOf(Object x) | This method is used to return the index of the first occurrence of the specified element, if the element is not present in the list it will return -1. |
| lastIndexOf(Object x) | This method is used to return the index of the last occurrence of the specified element, if the element is not present in the list it will return -1. |
| listIterator(int index) | This method is used to return the list-iterator of the elements starting from the specified position, in proper sequence. |
| offer(E element) | This method is used to add the specified element as the tail of the list. |
| offerFirst(E element) | This method is used to add the specified element in the front of the list. |
| offerLast(E element) | This method is used to insert the specified element at the end of the list. |
| peek() | This method fetches the head of the list, but doesn't remove it. |
| peekFirst() | This method fetches the head of the list or returns NULL if the list is empty. |
| peekLast() | This method fetches the tail of the list or returns NULL if the list is empty. |
| peekLast() | This method fetches the tail of the list or returns NULL if the list is empty. |
| poll() | This method is used to fetches and removes the first element of the list. |
| pollFirst() | This method fetches and removes the first element of the list or returns null is the list is empty. |
| pollLast() | This method fetches and removes the last element of the list or returns null is the list is empty. |
| pop() | This method is used to pop an element from the stack which is represented as a list. |
| push(E element) | This method is used to push an element onto the stack which is represented as a list. |
| remove() | This method fetches and removes the first element of the list. |
| remove(int index) | This method is used to remove an element at the specified position. |
| remove(Object o) | This method is used to remove the first occurrence of the element if it is present in the list. |
| removeFirst() | This method returns and removes the first element of the list. |
| removeFirstOccurrence(Object o) | This method is used to remove the first occurrence of the specified element when traversing the list from head to tail. |
| removeLast() | This method returns and removes the last element from the list. |
| removeLastOccurrence(Object o) | This method is used to remove the last occurrence of the specified element when traversing the list from head to tail. |
| set(int index, E element) | This method is used to replace the element present at the specified position with the provided element. |
| size() | This method is used to return the number of element in the list. |
| spliterator() | This method is used to create a late-binding and fail-fast Spliterator over the elements in the list. |
| toArray() | This method returns an array having all the elements of the list, following the order of head to tail. |
| toArray(T[] a) | This method returns an array having all the elements of the list, following the order of head to tail. The runtime type of the returned array is decided by the typename provided. |
| toString() | This method is used to return a string having all the elements of the list, in the order of head to tail. Each element is separated by a comma and the string is enclosed in square brackets. |
Example: Linked List implementation in Java
Let's dive into the code now. We are creating a Linked List using the LinkedList class which will store integers.
Output:
Performing Various Operations on Linked List
Now let's learn some key operations on Linked List such as Adding Elements, Updating Elements, Removing Elements, and Iterating over Elements.
Operation 1: Adding Elements
We can use the add() method provided in the LinkedList class. This method is overloaded so that we can perform multiple operations by changing the parameter.
This method adds the specified element to the end of the list.
Output:
add(int index, E element)
This method is used to add the element in the specified position of the Linked List.
Output:
Notice here, we are adding the element at index 4. We specified this index in the parameter of the method.
Operation 2: Updating Elements
Suppose after adding the elements in the linked list, we wish to update an element.
- This method that is used to update the element at the specified index.
Output:
As you can see, at index 3, 40 was present which is later updated to 1000 by the set() method.
Operation 3: Removing Elements
The remove() method is used to remove an element from the linked list. This method is overloaded, hence we can perform multiple operations by changing the parameter of the method.
This method is used to remove the specified object from the linked list. If multiple such objects are present, then this method removes the first occurrence of the object.
Output:
As you can see here the first occurrence of "with" is removed from the list.
remove(int index)
Output:
Here we have removed the element at index 0, "Learning"
Operation 4: Iterating over Elements
We can iterate over the linked list in multiple ways. Two famous ways are using the get(int index) method with for loop and the other is using the for-each loop. Let's have a look at the code.
Output:
The first line is printed using the get() method and for loop, while the second line is printed using the for-each loop.
Java LinkedList as Queue
As you have read, the LinkedList class also implements the Queue interface. Since the queue follows the first in first out (FIFO) order, hence we will be accessing the first element of the list and will be inserting a new element at the end of the list.
LinkedList class contains the methods for the queue interface. Some commonly used methods for queue interface are: peek(), poll(), offer(), etc.
Output:
Java LinkedList as Deque
The Java LinkedList class also contains methods for deque interface. In a deque or double-ended queue, we can insert and access the elements from both ends of the list. LinkedList class also contains the methods for deque interface. Some commonly used methods are: addFirst(), addLast(), getFirst(), getLast().
Output:
Circular Linked List in Java
As the name indicates, a circular linked list is a variation of a linked list in which the last node's next pointer is pointing to the head of the list. Or in other words, there is no starting and ending node in the list. So we can traverse the whole list from any node.
The circular linked list's performance is the same as of the normal linked list except the traversal from tail node to head node can be done in constant time.
Since in circular linked list, we have to change the next pointer of the last node, hence the circular linked list is implemented using the custom linked list class.
The below example demonstrates the implementation of a circular Linked List in Java.
Output:
LinkedList ArrayList
Both LinkedList and ArrayList implement the List interface of the Collection framework. But still, there are some differences between them.
| LinkedList | ArrayList |
|---|---|
| LinkedList implements the List, Queue, and Deque interfaces. | ArrayList implements the List interface. |
| Uses doubly linked list to store the elements. | Uses dynamic array to store the elements. |
| In a single position, it stores 3 values: previous address, data,next address. | In a single position it only stores a single value, that is the data. |
| Elements are accessed by traversing the list from head to the specified element. | Elements are accessed by using the indexes. |
| Manipulating an element is efficient, since it doesn't affect other elements of the list. | Manipulating an element is a bit time consuming, since the array is traversed and the memory bits are shifted. |
Why do we need a Linked List ?
A linked list provides us the ability to use the non-contiguous memory locations as a contiguous memory location. It is a dynamic data structure, hence there is no need to pre-allocate the memory. This results in efficient utilization of the memory. Also unlike the dynamic array, Insertion and deletion at the ends of the linked list are performed in constant time. Concatenation of two linked lists is much more efficient in terms of time as well as in terms of space.
Conclusion.
- A Linked List is a linear and dynamic data structure that allows us to store elements in non-contiguous memory locations.
- In java, Linked List can be implemented using a custom class or by using the LinkedList class present in the Collection framework.
- LinkedList class in the Collection framework implements the List, Queue, and Deque interfaces.
- Linked List provides us efficient manipulation of the elements, but lacks the random access capability.
FAQ's
Q: When is the Linked List used in Java?
A: Linked List is efficient for the manipulation of elements as Linked List provides constant time for addition or removal operations but lacks the random access capability, hence a Linked List should be used for multiple addition or deletion operations.
Linked List should be avoided when we need random access of the elements like in an array where we can access any element in constant time.
Q: What is ListNode?
A: In Java, a ListNode is a simple class that represents information related to a single member or node in a linked list. Each ListNode contains the data and the next or previous or both next and previous node's address.
Q: Does the Linked List allow null values?
A: Yes, the linked list allows an unlimited number of null values.
Q: What is the application of the Linked List?
- "undo" functionality in some famous software like MS-Word, Photoshop, etc. is implemented using the Linked List.
- Stack and Queue data structures are implemented using the Linked List.
- Adjacency list representation of graphs is implemented using the Linked List.
- Circular Linked List is used in the famous CPU scheduling algorithm "Round Robin".
Q: What are the limitations of the Linked List?
- As Linked List is storing another pointer, it is using more memory in comparison to the arrays.
- There is no random access of the elements, for any element list is traversed from the head to the specified element.
- Traversing in the backward direction is difficult in a singly-linked list.
- The access time of an element can be high, as nodes are stored in non-contiguous locations.