Last Updated: 06 October, 2024 5 Mins
A Linked List is a linear data structure that consists of a collection of elements; each element in a linked list is called a Node. The node contains two parts: the first part contains data, and the second part contains the address of the next node.
In the linked list there is a HEAD pointer, which points to the first element of the linked list, and if the list is empty then it stores NULL and the last node is called the Tail, and it stores NULL in the reference field (next).
A linked list is a dynamic data structure that allocates memory at runtime when required which helps in efficiently memory utilization and also provides flexible insertion and deletion operations.
Linked list elements are not stored in contiguous memory locations and the number of nodes in a linked list is not fixed.
Linked lists can be used to implement many different data structures, including Stacks, Queues, Graphs, Hash Maps, etc.
Head: The reference to the first node in a linked list, or a pointer to it, is called the head of the list. The linked list begins at this pointer.
Node: A node is an entity that consists of two parts: data and pointer (address of the next node).
Data: It contains the actual data (value) of the node.
Next Pointer: It contains the address of the next node of the linked list.
| Operations | Best Case | Average Case | Worst case |
| Traversal | O(n) | O(n) | O(n) |
| Insertion | O(1) | O(1) | O(n) |
| Deletion | O(1) |
O(1) |
O(n) |
| Search | O(1) |
O(n) |
O(n) |
That's all, guys. I hope this article is helpful for you.
Happy Learning... 😀
Please share this article on social media to help others.
feedback@javabytechie.com