Scientech Easy LinkedList in Java | LinkedList Methods & Example | Scientech Easy

Sunday, December 2, 2018

LinkedList in Java | LinkedList Methods & Example

In this tutorial, we will learn another important and interesting topic LinkedList class in Java which is the second implementation of java.util.list interface

Java LinkedList


 Java LinkedList class 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 which 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 a 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 as shown in the below picture. 
LinkedList in Java
Doubly LinkedList in Java

The right side of the node contains the address of the next element and the left side of the node contains the address of the previous element in the list.

Thus, It avoids the rearrangement of the elements required but requires that each element is connected to the next and previous by a link. Therefore, A LinkedList is often the better choice if the elements are added or removed from intermediate locations within the list.

Hierarchy Diagram of LinkedList class in Java


LinkedList class implements List and Deque interface and extends AbstractSequentialList. It also implements marker interface such as Serializable and Cloneable but does not implement Random Access interface. The hierarchy diagram of the LinkedList class can be shown in the below picture.
Java LinkedList Hierarchy Diagram

Features of LinkedList class in Java


The main features of Java LinkedList 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 the 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 of 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 the pop() and push() method which makes 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 the data items already stored in the list. Let's see an example to understand this concept.
1. Let us assume that our initial LinkedList has the following data as shown in the below picture.
How does Insertion works in LinkedList in Java?

2. Now we will perform Insertion operation on this LinkedList. We will add an element G at index position 2 like this:
    linkedlist.add(2,"G");
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 the previous pointer only without shifting of any element in the list. You can see the updated LinkedList in the above picture. 

How does Deletion work in Java LinkedList? 

We have already seen that how linked list performs insertion operation internally. Now we will discuss how Java linked list performs deletion operation internally in step by step.
1. Let us assume that our initial LinkedList has the following Data.
How Deletion works in Java LinkedList?

2. We will perform Deletion operation on this LinkedList. Suppose we want to remove or delete an element B from the index position 1.
    linkedlist.remove(1); 
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 the LinkedList in Java?

Java LinkedList is the best choice to use when your frequent operation is adding or removing of the elements in the middle of the list because the adding and removing of the elements in the linked list is faster as compared to ArrayList. Let's see an example.
Suppose there are 100 elements in the ArrayList. If we remove the 50th element from the array list then the 51st element will go to the 50th position, 52nd element to the 51st position and similarly for other elements that will consume a lot of time due to which the manipulation will be slow but in the case of LinkedList, if we remove the 50th element from the LinkedList, No shifting of elements will take place after removal. Only the reference of the next and previous node will change.  

What is the worst case scenario to use the LinkedList in Java? 

Java LinkedList is the worst choice to use when your frequent operation is the 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, the element cannot be accessed (getting) randomly. We will have to traverse from the beginning or ending to reach the elements in the linked list. Let's see an example.

Let us 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 the second element is available in the first node. So it will take two seconds time to access and getting the second element. 
Similarly, if we want to get the 9th element from the list then linked list will take 9 sec time to get the element. why? because the address of the 9th element is available in the 8th node, the address of the 8th node is available in the 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, maybe linked list will take one year time to access and getting the 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 the elements from the list because array list implements Random access interface. So, we can get an element from the array list from any arbitrary position.

Java LinkedList Constructors


Like the ArrayList class, The LinkedList class consists of two constructors. They are listed in the below table.
SN Constructor Description
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 List Methods


Java LinkedList has defined several useful methods which are inherited from the List or Collection interface. They are listed in the below table:
SN Method Description
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 which are inherited from the Deque interface. They are listed in the below table:
SN Methods Description
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.

Final words 
We hope that this article has covered almost all the important topics related to the Java LinkedList 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.


Popular