LinkedList in Java
Similar to arrays in Java, LinkedList is a linear data structure. However LinkedList elements are not stored in contiguous locations like arrays, they are linked with each other using pointer. Each elemenf of the LinkedList has the refernce(address/pointer) to the next element of the LinedList.
Representation of a LikedList
Each element in the LinkedList is called Node. Each node of the LinkedList contains two items. They are:
1. Content of the Element.
2.Pointer/Address/Reference to the Next Node in the LinkedList.
This is how a LinkedList looks:
Note:
- Head of the LinkedList only contains the address of the First element of the List.
- Where tail is the Last node of LinkedList and points to null because it is the end of the List so it doesn’t point to anything as show in the above diagram.
Types of LinkedList:
- Singly LinkedList
- Doubly LinkedList
- Circular LinkedList
Singly LinkedList:
It is the simplest type of LinkedList in which every node contains some data and a pointer to the next node of the same data type.
The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single LinkedList allows the traversal of data only in one way is as shown in below image.
Doubly LinkedList:
A doubly Linked is also known as two-way LinkedList. This Doubly LinkedList is a more complex type of LinkedList that contains a pointer to the next as well as the previous node in the sequence.
Therefore, it contains three parts of data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well is as shown in below image.
Circular LinkedList:
A circular LinkedList is that in which the last node contains the pointer to the first node of the list.
While traversing a circular LinkedList, we can begin at any node and traverse the list in any direction i.e, both forward & backward direction until we reach the same node we started. Thus, circular LinkedList has no begining and no end as shown in the below image.
Major Operations:
The major operations in the LinkedList are:
- Creation of a list
- Addition of elements into the list
- Retrieval of elements from the list
- Deletion of elements from the list
- Verification of elements in the list
- Updation of elements in the list
