---
# System prepended metadata

title: Linked List
tags: [linked list]

---

# Linked List
###### tags: `linked list`
![conga line](https://i.imgur.com/lf9SUhi.png)

A linked list is **a linear data structure** in which elements are linked using pointers.
:::info
**[A linear data structure](https://www.educative.io/answers/what-are-linear-data-structures)**
A linear data structure **has data elements connected to each other** so that elements are arranged in a sequential manner and each element is connected to the element in front of it and behind it. This way, the structure can be traversed in a single run.
:::
It consists of nodes where each **node** contains **a data field** and **a reference(link or pointer)** to the next node in the list.

![](https://i.imgur.com/gq20JlX.png)

:::spoiler **Detail**
![](https://i.imgur.com/lYCLpAm.png)
:::

### Advantages
- Nodes **==can easily be removed or added==** from a linked list without reorganizing the entire data structure. **(O(1))**
- Is **==a dynamic structure==**.
![](https://i.imgur.com/bzeZFoW.jpg)

### Disadvantages
- **==Search operations are slow==** in linked lists.(O(n)) Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
- It **==uses more memory==** than arrays because of the storage of the **pointers**.
### Implementing Linked List
```javascript=
class Node {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}
class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}
```
```javascript=

// create node1 & 2 and linked them up
let node1 = new Node(2)
let node2 = new Node(5)
node1.next = node2

// create a Linked list with the node1
let list = new LinkedList(node1)

// access node
console.log(list.head.next.data) //returns 5
```

### Commom mathods
#### size()
This method returns the number of nodes present in the linked list.
```javascript=
size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}
```
#### clear()
This method empties out the list.
```javascript=
clear() {
    this.head = null;
}
```
#### getLast()
This method returns the last node of the linked list.
```javascript=
getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}
```
#### getFirst()
This method returns the first node of the linked list.
```javascript=
getFirst() {
    return this.head;
}
```
### Others
#### Circular list
![](https://i.imgur.com/OqDVaHY.jpg)

#### Bidirectional list
![](https://i.imgur.com/eAQ1pc0.jpg)


