Thinking about data structure, let's take a closer look at Linked List.
Linked list is one of the most popular and efficient data structures. Basically, Linked List is a collection of "nodes", each node contain data, next and previous, basically next refers to next node and previous refers to the previous node.
We can say that, array and linked list is similar. but in array, elements are stored in a specific location or index.
On the other hand, in Linked List everything works as a separate object. Each element (node) contain few things, data, link to the next node, link to the previous node.
Types of Linked List:
There are three types of linked list,
1. Singly Linked List: Each node contains data and a pointer to the next node. Basically its unidirectional.
Analyzing the above image, it start with Head, so Head is the entry point. If a Linked list is empty then the Head will be null. So Head reference to the first node and Last node points to the null.
const linkedList = {
head: {
value: 5
next: {
value: 7
next: {
value: 2
next: {
value: 15
next: null
}
}
}
}
}
};
Basic example,
// class of node
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
/* LindedList class. remember, if the head node is not passed then head will be null */
class LinkedList {
constructor(head = null) {
this.head = head
}
}
/* lets create some nodes */
let node1 = new ListNode(5) // data will be 5
let node2 = new ListNode(7) // data will be 7
let node3 = new ListNode(2) // data will be 2
let node4 = new ListNode(15) // data will be 15
node1.next = node2 // points to the node2
node2.next = node3 // points to the node2
node3.next = node4
let list = new LinkedList(node1) // Linked List completed
Advantage and Uses of Singly Linked List
- Dynamic data structure: Memory is dynamically allocated to the linked List. easily we can add or remove an element. We don't need to think about initial size.
- Implementation: Other data structure can be easily implemented here such as Queues and Stacks.
- Versatility: Lined list can be used to implement a wide range of data structures, such as stacks, queues, graphs, truees and has tables.
Disadvantage of Singly Linked List
- Memoray usage: We need to store address of the next data, so it takes more memory.
- Accessing an element: Its impossible to access any element directly. If we need to find nth value, then we need to traverse until nth element found.
- Reverse traversal: It impossible for the Singly linked List. Because we don't have the memory address of the previous pointer.
- More complex implementation: Similar to Array, Its implementation is very complex. We need to understand dynamic memory location and pointer manipulation.
- Lack of cache locality: It may not take advantage of the caching mechanisms in modern processors. Its slower in performance.
2. Doubly Linked List: Each node contains two pointers one for next node and one for previous node.
in the above image, we understand that,
- prev: refers to the previous node
- data: data item
- next: address to the next node
below image shows us representation of doubly Linked list, Here each node contain next _and _prev to point next node and prev node
Basic example
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
this.previous = null;
}
}
class DoublyLinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
previous: null
};
this.length = 0;
this.tail = this.head;
}
// Insert node at end of the list
add(newNode) {
this.tail.next = newNode;
newNode.previous = this.tail;
this.tail = newNode;
this.length++;
}
printList() {
let current = this.head;
let result = [];
while (current !== null) {
result.push(current.value);
current = current.next;
}
console.log(result.join(' '));
return this;
}
}
let numList = new DoublyLinkedList();
numList.add(new ListNode (12));
numList.add(new ListNode (13));
numList.add(new ListNode (14));
numList.add(new ListNode (15));
numList.add(new ListNode (16));
numList.add(new ListNode (17));
numList.printList();
console.log(numList)
console.log(numList.head)
Advantage of Doubly Linked List:
- Reversing: Reversing the doubly linked list is very easy.
-Traversal: The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
-Deletion: Deletion of nodes is easy as compared to a Singly Linked List.
Disadvantage of Doubly Linked List:
- It uses extra memory when compared to the array and singly linked list.
- Traversing a doubly linked list can be slower than traversing a singly linked list
- Implementing and maintaining doubly linked lists can be more complex than singly linked lists.
Uses of Doubly Linked List:
- Navigation Systems: It is used in the navigation systems where front and back navigation is required.
- Undo and Redo: It is also used by various applications to implement undo and redo functionality.
- MRU/LRU: Doubly Linked List is also used in constructing MRU/LRU (Most/least recently used) cache.
- Thread Scheduler: Also in many operating systems, the thread scheduler(the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.
- Browser: next and previous page.
- Image viewer: next and previous image
- Implementing **Graph **algorithms
3. Circular Linked Lists: Its different than others, its last node points to the first nor or any other node before it.
It has two types,
- Circular Singly Linked List
- Circular Doubly Linked List
We will learn Circular Linked List in the next. that's it for today. See yaaa.
Top comments (0)