A linked list is a linear data structure consisting of a group of nodes where each node points to the next node by means of a pointer.
Each node is composed of data and a reference to the next node in the sequence. The last node has a reference to null which indicates the end of the linked list.
Head node is the starting node of the linked list(first node) and it contains the reference to the next node in the list. The head node will have a null reference when the list is empty. The below image gives you an idea of how a Linked List looks.
Why Linked lists?
- One advantage of the linked lists is that elements can be added to it indefinitely without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory. while an array will eventually get filled or have to be resized for making an insertion whenever needed (a costly operation that isn't always possible).
- Elements are also be easily removed from linked lists whereas removing elements from an array leaves empty spaces that are a waste of computer memory or performing a shift operation in arrays increases the cost thus makes it expensive.
Types of Linked Lists
There are three different types of Linked Lists. They are as follows.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Representation of Linked Lists
a) Singly Linked Lists
- The first node is the head node and it points to next node in the sequence.
- The last node’s reference is null indicating the end of the list.
b) Doubly Linked Lists
- Every node has two pointers, one for pointing to next node and the other for pointing to the previous node.
- The next pointer of the last node and the previous pointer of the first node (head) are null.
c) Circular Linked Lists
- Circular Linked List is very similar to a singly linked list except that, here the last node points to the first node making it a circular list as shown below.
Operations of Linked List
The following are the basic operations supported by linked lists.
- Insertion − Inserts an element at specified positions in the list.
- Deletion − Deletes an element at specified positions in the list.
- Search − Searches an element using the given value.
- Update − Update an element at specified position with the given value