Linked Lists
Linked Lists
At its simplest, a linked list is a data structure that contains a series of nodes, where each node is linked to the next node in the list. Each node contains two main parts: the actual data that we want to store, and a pointer to the next node in the list.
Linked lists are dynamic data structures, which means that we can add or remove nodes from the list at any time. This makes them very flexible and efficient for certain types of operations, like inserting or deleting elements.
SLL
Singly Linked List
A singly linked list is a data structure that consists of a sequence of nodes, where each node stores a piece of data and a pointer to the next node in the list. In other words, each node contains two parts: the actual data that we want to store and a reference (or pointer) to the next node in the list.
DLL
Doubly Linked List
A doubly linked list is a type of data structure that consists of a sequence of nodes, where each node stores a piece of data and two pointers: one to the next node in the list, and one to the previous node in the list. In other words, each node contains three parts: the actual data that we want to store, a pointer to the next node in the list, and a pointer to the previous node in the list.
This extra pointer to the previous node makes doubly linked lists more versatile than singly linked lists. With a doubly linked list, we can traverse the list in either direction, from the head to the tail or from the tail to the head, making it easier to perform certain types of operations, like searching for a specific element.
Circular SLL
Circular Singly Linked List
A circularly linked list is a type of data structure that is similar to a singly linked list, but with one key difference: instead of having the last node point to null (signifying the end of the list), the last node in the list points back to the first node, forming a circle.
This circular structure allows for some interesting properties. For example, we can traverse the list in a loop, continuously visiting each node in the list. Additionally, we no longer need to keep track of the head or tail of the list, since every node in the list can be treated as both the head and the tail.
Circular DLL
Circular Doubly Linked List
circularly doubly linked list is a type of data structure that combines the features of both a circularly linked list and a doubly linked list. It is similar to a circularly linked list, with each node pointing to the next node in the list and the last node pointing back to the first node, forming a circle. However, each node also contains a pointer to the previous node in the list, creating a two-way connection between nodes.
This two-way connection allows for some additional functionality compared to a regular circularly linked list. For example, we can traverse the list in either direction, from the head to the tail or from the tail to the head. We can also easily insert or delete elements from the middle of the list, since each node has pointers to both the previous and next nodes.
Circularly doubly linked lists can be useful in many scenarios, such as implementing a queue, a stack, or a doubly ended queue (deque). However, they do require more memory than regular circularly linked lists, since each node needs to store an extra pointer.