A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
A linked list is a data structure that consists of a group of nodes which together represent a sequence. Each node contains two fields:
- Data field: Contains the actual data.
- Link field: Contains the address of the next node in the sequence.
The above example shows a linked list with four nodes. The first node is called the head node, and the last node is called the tail node. The head node is the first node in the sequence, and the tail node is the last node in the sequence.
The nodes in a linked list are not stored at contiguous memory locations. The link field of a node contains the address of the next node in the sequence. The first node is pointed to by the head pointer, and the last node is pointed to by the tail pointer.
- Linked lists are dynamic data structures. That is, they can grow and shrink during execution of a program.
- Insertion and deletion operations can be easily implemented in linked lists.
- Linked lists can be easily implemented in different ways. For example, they can be implemented as singly linked lists or doubly linked lists.
- Circular linked lists can be easily implemented in linked lists.
- Random access is not possible in linked lists. We need to access the nodes sequentially from the beginning.
- Extra memory space is required for storing the pointers.
- Arrays have better cache locality that can make them slightly faster.
There are two ways to implement linked lists:
- Singly linked lists: In this type of linked list, each node contains a data field and a link field, which contains the address of the next node in the sequence.
- Doubly linked lists: In this type of linked list, each node contains two link fields, which contain the addresses of the previous and next nodes in the sequence.
The following operations can be performed on a linked list:
- Insertion: Adds a new node to the list.
- Deletion: Deletes a node from the list.
- Traversal: Displays the data stored in the nodes of the list.
- Search: Searches for a given data item in the list.
- Reverse: Reverses the order of the nodes in the list.
There are three ways to insert a node in a linked list:
- Insertion at the beginning of the list: In this type of insertion, the new node is inserted at the beginning of the list.
- Insertion at the end of the list: In this type of insertion, the new node is inserted at the end of the list.
- Insertion in the middle of the list: In this type of insertion, the new node is inserted in the middle of the list.
There are three ways to delete a node in a linked list:
- Deletion at the beginning of the list: In this type of deletion, the node to be deleted is the first node in the list.
- Deletion at the end of the list: In this type of deletion, the node to be deleted is the last node in the list.
- Deletion in the middle of the list: In this type of deletion, the node to be deleted is in the middle of the list.
There are two ways to traverse a linked list:
-
Iterative traversal: In this type of traversal, we use a loop to visit each node of the list.
-
Recursive traversal: In this type of traversal, we use a recursive function to visit each node of the list.
There are two ways to search for a given data item in a linked list:
-
Iterative search: In this type of search, we use a loop to visit each node of the list until we find the desired data item.
-
Recursive search: In this type of search, we use a recursive function to visit each node of the list until we find the desired data item.
There are two ways to reverse a linked list:
-
Iterative method: In this method, we use a loop to reverse the pointers of the nodes in the list.
-
Recursive method: In this method, we use a recursive function to reverse the pointers of the nodes in the list.