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)