DEV Community

Cover image for Linked List Data Structure
Aya Bouchiha
Aya Bouchiha

Posted on • Updated on

Linked List Data Structure

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;
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)