Learn Linked List (1)
Published: 2024-05-20 18:26:28





## what is linked list

Linear collection of data elements (aka Node), In which linear order is not given by their physical placement in memory. Instead each element points to the next element. It is a data structure consisting of a group of nodes that together represent a sequence.

## what are the advantages
- Efficient Deletion of Known Nodes / O(1)
- Efficient Insertion / O(1)
- Dynamic Size
- Linked lists do not require contiguous memory allocation like Array

## what are the disadvantages
- Sequential Access / O(n)
- Memory Overhead, as each node in a linked list requires additional memory for the pointer/reference to the next node.

## when to use
- Implementing a Queue or Stack / O(1)
- Undo Mechanisms
- Frequent Insertions/Deletions in Middle/ O(1)

## Example

structure of a single node : 
```javascript
class LinkedListNode {
    constructor(value, next = null){
        this.value = value;
        this.next = next
    }
}
```

*Figure 1: This is an example of a node.*


structure of linked list : 
```javascript
class LinkedList {
    constructor () {
        this.head = null;
        this.tail = null;
    }
}
```
*Figure 2: This is an example of a nodelist.*
![Figure 3: This is an example of visual representation of Node List.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fx1fff5vdz2jz4yps0ht.png)
*Figure 3: This is an example of visual representation of Node List.*


## Basic Operation

### Append

#### PseudoCode

```
Append(value)
    pre : value is the value to add in the list
    post : value has beed added at the tail of the list

newNode ⟵ node(value)

if(head = Ø) :
    head ← newNode
    tail ← newNode
else
    tail.next ← newNode
    tail ← newNode

end Append
```
*Figure 4: This is an example of a nodelist append pseudocode.*

#### Javascript Implementaion
```javascript
append (value) {
        let lastNode = new LinkedListNode(value)

        if(!this.head){
            this.head = lastNode;
            this.tail = lastNode;
            return this;
        }else{
          //here this.tail is the previous last node
            this.tail.next = lastNode; //add the current lastNode reference to the previous last node next property
            this.tail = lastNode;   // change the reference of the tail to the current lastNode.
            return this;
        }
    }
```
*Figure 5: This is an example of a nodelist append method implementation.*
#### Visual Example
![Figure 6: This is an example of visual representation of Node List Appending.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/30pslie1n7nnjs0o43av.png)
*Figure 6: This is an example of visual representation of Node List Appending.*


### Prepend
#### PseudoCode
```
  Prepend(value)
  pre : value is the value to add in the list.
  post : value added as the head of the list

  newNode ← node(value)
  newNode.next ← head

  head ← newNode
  if(tail = Ø)
    tail ← newNode

end Prepend
```
*Figure 7: This is an example of a nodelist prepend pseudocode.*
```javascript
  prepend(value){
    //create a node whose next property point to the previous head
    const newHead = node(value, this.head)  
    this.head = newHead 
    if(!this.tail){
      this.tail = newHead
    }
  }
  ```
  *Figure 8: This is an example of a nodelist prepend method implementation.*
![Figure 9: This is an example of visual representation of Node List Prepending.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wz6fyeu57ow4qy0cm3t9.png)
*Figure 9: This is an example of visual representation of Node List Prepending.*