➲ Java LinkedList is a linear data structure that uses a doubly linked list to store the elements. A doubly linked list consists of a group of nodes that together represents a sequence in the list.
Each node contains three fields: a data field that contains data stored in the node, left and right fields contain references or pointers that point to the previous and next node in the list. A pointer indicates the addresses of the next node and the previous node.
➲ Since the previous field of the first node and the next field of the last node does not point to anything, we must set it with the null value.
➲ When we store a new element in the linked list, a new node is created. Its size will grow with the addition of each and every element. Therefore, its initial capacity is zero.
➲ Elements in the linked list are called nodes.
➲ In the Linked List, the elements are not stored in the consecutive memory location. An element (often called node) can be located anywhere in the free space of the memory by connecting each other using the left and right side of the node portion.
An array representation of linear doubly LinkedList in Java is shown in the below figure.
Thus, It avoids rearrangement of elements required but requires that each element is connected to the next and previous by a link. Therefore, a LinkedList is often better choice if elements are added or removed from intermediate locations within the list.
The right side of the node contains address of the next element and left side of the node contains address of the previous element in the list.
Hierarchy Diagram of Java LinkedList class
LinkedList class implements List and Deque interface. It extends AbstractSequentialList. It also implements marker interfaces such as serializable and cloneable but does not implement random access interface. The hierarchy diagram of the LinkedList class can be shown in below figure.
Features of LinkedList class in Java
The main features of Java LinkedList class are as follows:
1. The underlying data structure of LinkedList is Doubly LinkedList structure.
2. Java LinkedList class allows storing duplicate elements.
3. Null elements can be added in the LinkedList.
4. Heterogeneous elements are allowed in LinkedList.
5. Java LinkedList is not synchronized. So, multiple threads can access the same LinkedList object at the same time. Therefore, It is not thread-safe. Since LinkedList is not synchronized. Hence, its operation is faster.
6. Insertion and Removal of the elements in the LinkedList are fast because, in the LinkedList, there is no shifting of elements after each adding and removal. The only reference for next and previous elements changed.
7. LinkedList is the best choice if your frequent operation is insertion or deletion in the middle.
8. Retrieval(getting) of elements is very slow in LinkedList because it traverses from the beginning or ending to reach the element.
9. The LinkedList can be used as “stack“. It has pop() and push() methods which make it function as a stack.
10. Java LinkedList does not implement random access interface. So, the element cannot be accessed (getting) randomly. To access the given element, we have to traverse from the beginning or ending to reach elements in the LinkedList.
11. We can iterate linked list elements by using ListIterator.
How does Insertion work in Java LinkedList?
In the Java LinkedList, we can perform insertion (addition) operation without affecting any of data items already stored in the list. Let’s take an example to understand this concept.
1. Let us assume that our initial LinkedList has the following data as shown in the below picture.
2. Now we will perform insertion operation on this LinkedList. We will add an element G at index position 2 using add() method. The syntax for adding element G is as follow:
When the insertion operation takes place in the linked list, Internally, LinkedList will create one node with G element at anywhere available space in the memory and changes the next and previous pointer only without shifting of any element in the list. Look at the updated LinkedList in the above picture.
How does Deletion work in Java LinkedList?
In the previous section, we have already seen how linked list performs insertion operation internally. Now we will discuss how Java linked list performs deletion operation internally step by step.
1. Let us assume that our initial LinkedList has the following data.
2. We will perform deletion operation on this LinkedList. Suppose we want to remove or delete an element B from the index position 1. The syntax to delete element B is as follows:
When deletion operation takes place, the node with element B is deleted with changing the next and previous pointer. The deleted node becomes unused memory, and Java will clean up the unused memory space using the garbage collection.
What is the best case scenario to use LinkedList in Java?
What is the worst case scenario to use LinkedList in Java?
Java LinkedList is the worst choice to use when your frequent operation is retrieval (getting) of elements from the linked list because retrieval of elements is very slow in the LinkedList as compared to ArrayList.
Since LinkedList does not implement Random Access Interface. Therefore, an element cannot be accessed (getting) randomly. We will have to traverse from the beginning or ending to reach elements in the linked list.
Let us consider an example scenario to understand this concept. Assume that there are ten elements in the list. Suppose that LinkedList accesses the first element in one second from the list and retrieves the element.
Since the address of second element is available in the first node. So, it will take two seconds time to access and get the second element.
Similarly, if we want to get 9th element from the list then LinkedList will take 9 sec time to get element. Why?
This is because the address of 9th element is available in 8th node. The address of 8th node is available in 7th node and so on.
But if there are one crore elements in the list and we want to get 50th lakhs element from the list, may be linked list will take one year time to access and getting 50th lakhs element. Therefore, LinkedList is the worst choice for the retrieval or searching of elements from the linked list.
In this case, ArrayList is the best choice to use for getting elements from the list because ArrayList implements random access interface. So, we can get an element from the array list from any arbitrary position.
Java LinkedList Constructors
Like ArrayList class, LinkedList class consists of two constructors. They are listed in the below table.
|1.||LinkedList()||It is used to create an empty LinkedList object.|
|2.||LinkedList(Collection c)||It is used to construct a list containing the elements of the given collection.|
Java LinkedList Methods
Java LinkedList has defined several useful methods that are inherited from List or Collection interface. They are listed in the below table:
|1.||boolean add(Object o)||It is used to add the specified element to the end of a list.|
|2.||void add(int index, Object o)||It is used to insert the specified element at the specified position in a list.|
|3.||boolean addAll(Collection c)||It is used to add all of the elements in the specified collection to the end of this list|
|4.||boolean addAll(int index, Collection c)||It is used to add all the elements of the specified collection at specified index position in the list.|
|5.||void clear()||It is used to remove or delete all the elements from a list.|
|6.||boolean contains(Object o)||It returns true if a list contains a specified element.|
|7.||int size()||It is used to get the number of elements in a list.|
|8.||Object toArray()||It returns an array containing all the elements in a list in proper sequence|
|9.||Object clone()||This method is used to return a shallow copy of an ArrayList.|
|10.||boolean remove(Object o)||This method is used to remove the first occurrence of the specified element in the linked list.|
|11.||Element remove(int index)||This method is used to remove the element at the specified position in the linked list.|
|12.||Element element()||This method is used to retrieve the first element of the linked list.|
|13.||E get(int index)||It is used to get the element at the specified position in a list.|
|14.||Element set(int index, E element)||It is used to replace the element at the specified position in a list with the specified element.|
|15.||int indexOf(Object o)||It is used to get the index of the first occurrence of the specified element in the list. It returns -1 if the list does not contain any element.|
|16.||int lastIndexOf(Object o)||It is used to get the index of the last occurrence of the specified element in a list. It returns -1 if the list does not contain any element.|
|17.||Iterator iterator()||This method returns an iterator over the elements in a proper sequence in the linked list.|
|18.||ListIterator listIterator(int index)||This method returns a list-iterator of the elements in a proper sequence, starting at the specified position in the list.|
Java LinkedList Deque Methods
Java LinkedList class has also various specific methods that are inherited from Deque interface. They are listed in the below table:
|1.||void addFirst(Object o)||It is used to add the specified element at the first position of the Linkedlist.|
|2.||void addLast(Object o)||It is used to add the specified element to the end of the Linkedlist.|
|3.||Object getFirst()||This method is used to return the first element from the list.|
|4.||Object getLast()||It is used to get the last element from the list.|
|5.||Object removeFirst()||It removes the first element from the linked list and returns it.|
|6.||Object removeLast()||It removes the last element from the linked list and returns it.|
|7.||boolean offerFirst(Object o)||It is used to insert the specified element at the front of a list.|
|8.||boolean offerLast(Object o)||It is used to insert the specified element at the end of a list.|
|9.||Object peek()||It retrieves the first element from the linked list|
|10.||Object peekFirst()||It is used to retrieve the first element from the linked list. It will return null if the list is empty.|
|11.||Object peekLast()||It is used to retrieve the last element from the linked list. It will return null if the list is empty.|
|12.||Object poll()||It retrieves and removes the first element from the linked list.|
|13.||Object pollFirst()||It retrieves and removes the first element from the linked list. It returns null if a list is empty.|
|14.||Object pollLast()||It retrieves and removes the last element from the linked list. It returns null if a list is empty.|
|15.||Object pop()||This method is used to pop an element from the stack represented by a list.|
|16.||void push(Object o)||This method is used to push an element onto the stack represented by a list.|
If you want to get more details about these methods, you click here Javadocs.
Hope that this tutorial has covered almost all the important topics related to LinkedList in Java and its various methods with some example. In the next tutorial, we will discuss Linked list example programs in an easy way and step by step.