Linked List Data Structure
Tags: algorithms, beginners, javascript
Published: 2021-06-13 19:58:58

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](https://gist.github.com/bradtraversy/c38f029e5f9e56a19c393d3a3b1e1544)

```javascript
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](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.geeksforgeeks.org/data-structures/linked-list/)
+ [https://www.freecodecamp.org/news/data-structures-explained-with-examples-linked-list/] (https://www.freecodecamp.org/news/data-structures-explained-with-examples-linked-list/)
+ [https://youtu.be/ZBdE8DElQQU](https://youtu.be/ZBdE8DElQQU)
+ [https://youtu.be/9YddVVsdG5A](https://youtu.be/9YddVVsdG5A)
+ [https://www.youtube.com/watch?v=CJRxkfKXB7g](https://www.youtube.com/watch?v=CJRxkfKXB7g)
+ [https://www.geeksforgeeks.org/linked-list-set-1-introduction/](https://www.geeksforgeeks.org/linked-list-set-1-introduction/)

I am grateful for your time :)
\#day_1