Aya Bouchiha

Posted on Jun 13, 2021 • Edited on Jul 8, 2021

Linked List Data Structure

#algorithms #beginners #javascript

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

I am grateful for your time :)
#day_1

DEV Community