Linked Lists (Singly, Doubly, and Circularly)
Linked Lists, another primitive datastructure with significant importance. It is a linear collection of data elements, slightly similar to arrays, the difference is the operations done on it.
A linked list is like a train when you think about it, such that each element is a block that is chained to the block next to it and so on. A linked list is a collection of blocks or nodes in this case such that each node carries some data and a pointer that points to the next node, and so on.
Although both linked lists and arrays are linear collections of data, they differ in the following
- Arrays have random access element such that an element can be accessed by its position (index), while a linked list has to go from the first node all the way to the nth node to access that nth element.
- Statically defined Arrays can not add more elements that exceeds its pre-defined size, while a linked lists is dynamic in the sense that a block can be added anywhere with no more than two pointer manipulation. It is a dynamic linear datastructure.
Usually when working with linked lists, when we point at the first node we often refer to it as the head, while pointing at the last node is often called the tail. It is a common practice so that we know if we want to traverse the list, we start from the head all the way to the tail.
There are 3 variations of a Linked List:-
- Singly list:- a list that has only one pointer called
next , pointing to the next node. Last node in the list points to NULL. - Doubly list:- a list that has two pointers
(next, prev) pointing to both the next node and the previous node of the current one. Last node'snext points to NULL, and the first block'sprev points to NULL. - Circularly list:- it is the same as a doubly list except that the last node points back to the first node (head) and head's
prev pointer points to the last node (tail), thus forming a cycle.
template <typename T>
class SingleListNode {
public:
T data;
SingleListNode *next;
SingleListNode(const T& d) : data(d), next(NULL) {}
};
template<typename T>
class DoublyListNode {
public:
T data;
DoublyListNode *next, *prev;
DoublyListNode(const T& d) : data(d), next(NULL), prev(NULL) {}
};