Hi, on this beautiful day, we are going to talk about Linked List, we will cover and answer these Questions :
What is a Linked List?
What are the advantages of using Linked List?
What are the negatives of using Linked List?
What are the types of Linked List?
What's the space complexity of Linked List?
What's the time complexity of a singly Linked List?
How can we implement A Singular Linked List using Javascript?
What are some useful and helpful resources to learn Linked List?
Let's start with the first question.
Definition of a Linked List
A linked list is a linear data structure, in which the elements are linked using pointers, additionally, they are not stored at contiguous memory locations. A Linked List consists of Nodes that contain value ( data ) and a pointer to the next node in the chain. The head pointer points to the first node if the list is not empty, and the last element of the list points to null.
Advantages Of using Linked List
- Dynamic Size
- adding and deleting easily nodes without the need for displacement which is an expensive operation in an array
Negatives of using Linked List
- Extra memory space for nodes' pointers
- We have to access elements sequentially starting from the first node to the wanted node.
Types of Linked List
- Singly Linked List
- Doubly Linked List
- Circular Linked List
Space Complexity of Linked List
O(n)
Time Complexity of a singly Linked List
Access | Insertion | Deletion | Search |
---|---|---|---|
O(n) | O(1) | O(n) | O(n) |
Implementation of a Singly Linked List using Javascript from travesy media github
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
// Create/Get/Remove Nodes From Linked List
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Insert first node
insertFirst(data) {
this.head = new Node(data, this.head);
this.size++;
}
// Insert last node
insertLast(data) {
let node = new Node(data);
let current;
// If empty, make head
if (!this.head) {
this.head = node;
} else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
// Insert at index
insertAt(data, index) {
// If index is out of range
if (index > 0 && index > this.size) {
return;
}
// If first index
if (index === 0) {
this.insertFirst(data);
return;
}
const node = new Node(data);
let current, previous;
// Set current to first
current = this.head;
let count = 0;
while (count < index) {
previous = current; // Node before index
count++;
current = current.next; // Node after index
}
node.next = current;
previous.next = node;
this.size++;
}
// Get at index
getAt(index) {
let current = this.head;
let count = 0;
while (current) {
if (count == index) {
console.log(current.data);
}
count++;
current = current.next;
}
return null;
}
// Remove at index
removeAt(index) {
if (index > 0 && index > this.size) {
return;
}
let current = this.head;
let previous;
let count = 0;
// Remove first
if (index === 0) {
this.head = current.next;
} else {
while (count < index) {
count++;
previous = current;
current = current.next;
}
previous.next = current.next;
}
this.size--;
}
// Clear list
clearList() {
this.head = null;
this.size = 0;
}
// Print list data
printListData() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
Exercises
https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-linked-list.php
References and Useful resources
- https://www.geeksforgeeks.org/data-structures/linked-list/
- https://www.freecodecamp.org/news/data-structures-explained-with-examples-linked-list/
- https://youtu.be/ZBdE8DElQQU
- https://youtu.be/9YddVVsdG5A
- https://www.youtube.com/watch?v=CJRxkfKXB7g
- https://www.geeksforgeeks.org/linked-list-set-1-introduction/
I am grateful for your time :)
#day_1
Top comments (0)