Linked lists are a fundamental data structure used to represent a collection of elements in a sequence. They are referred to as a sequential data structure, with each element in a link list referred to as a node.
A node consists of a value and a pointer to the next value (or two pointers pointing to the next value as well as the previous value in the case of doubly linked lists). Referring to the illustration above, we can see that there are three nodes in the linked list. The first node has a value of 5 and points to the second node which has a value of 9 and points to the third node. Since each node points to the next, we can move from one node to the adjacent one sequentially.
Now that we know that each element in a linked list is called a node and that each node consists of a value and a pointer to the next node, let's discuss two special nodes in a linked list: head node and tail node.
The first node in a linked list is referred to as a head node or the head. The last node in a linked list is referred to as a tail node or simply as the tail. While the head points to the second node, the tail points to null to indicate the end of the linked list. The previous illustration has been updated with head and tail labels.
Until now, what we have discussed is in reference to a single linked list. With the knowledge of node, head, and tail in mind, let's explore other types of linked lists.
Doubly Linked List
In a doubly linked list, a node has two pointers that point to the previous and the next nodes. This means that at any point in a doubly linked list, one can move forward or backward to reach a specific node.
Unlike in a single linked list, the head node in a doubly linked list points to null as a previous value.
Circular Linked List
A circular linked list is another type of linked list where the last node needs to point back to the first node, hence allowing for a circular traversal of the linked list.
A circular linked list can be either single or doubly linked. In a singly linked circular linked list, each node only has a single pointer to the next node in the list, and the last node points back to the first node to form a cycle. In a doubly linked circular linked list, each node has both a forward and a backward pointer, so each node points to the next and previous nodes in the list. Like the singly linked circular linked list, the last node points back to the first node to form a cycle.
Use Cases
Single linked lists: These are often used in situations where data only needs to be accessed in a forward direction, such as in a queue or a stack. For example, a printer spooler may use a single linked list to store a queue of print jobs, where each new job is added to the end of the list and the first job is printed first.
Doubly linked lists: These are useful in situations where data needs to be accessed in both directions, such as in a music playlist where the user may want to go back and forth between songs. Another example is a web browser's history list, where each page is stored as a node and the user can navigate forward and backward through their browsing history.
Circular linked lists: These can be useful in situations where the last node needs to point back to the first node, such as in a round-robin scheduling algorithm. For example, in a tournament where every team plays against each other, a circular linked list can be used to determine the order of the matches, where each node represents a team and the last node points back to the first node to create a cycle.
Conclusion
Linked lists are a fundamental data structure in software development with a wide range of applications. This article aims to provide you with an initial understanding of what they are. In the future, I will delve into why linked lists are used, as well as provide information on implementing them in code.