Diving into Singly Linked Lists

Diving into Singly Linked Lists

Alanna M.'s photo
Alanna M.
·

3 min read

Linked lists are a linear data structure consisting of nodes that are not stored contiguously (right next to each other) in memory.

Each node of the linked list consists of data and a next pointer. Since (unlike the array) a linked list is not stored contiguously, the purpose of the next pointer is to provide a reference or link to the next node in the sequence. Hence the term "linked" list.

1_iiEWrP2IznA6HbmuIdK0lQ.png

As seen in the image above, the last node's next pointer always points to null. This is how we know we've reached the end of the list.

Head is the name given to the first node in the list Tail is the name given to the last node in the list

Pros of linked list

  • insertion and deletion are done in O(1)
  • not stored contiguously in memory
  • dynamic (linked lists grow/shrink at runtime depending on its size)

Cons of linked list

  • uses more memory than an array
  • traversal is more time consuming compared to an array since there is no direct (index) access
  • in a SLL, reverse traversing is not possible
  • random access is not possible because there are no indices

Stepping away from linked lists for a while, when we think of the array in JavaScript, there are methods that allow us to interact and modify the array. Think, push(), shift(), etc. Similarly, there are linked list methods allowing us the ability to interact with and modify it. The only difference is that they're not built-in; we have to create them ourselves.

These methods include

  • addToEnd() or push(): adds a node to the end of the list
  • addToStart() or unshift(): adds a node to the start of the list
  • deleteFromEnd() or pop(): deletes a node from the end of the list
  • deleteFromStart() or shift(): deletes a node from start of the list
  • length(): returns the length of the linked list

Implementing a linked list node:

Remember, a node consists of data (val) and a next pointer which is initialized to null since the linked list will be empty when we start.

class Node {
  constructor(val) {
    this.value = val;
    this.next = null;
  }
}

Implementing a linked list:

Remember, the first node is called the head and the last node is called the tail. We have instant access to the first and last node which is why insertion and deletion is O(1). Also, the linked list will be empty initially, so both head and tail are initialized with null.

class LinkedList {
  constructor(){
    this.head = null
    this.tail = null
    this.length = 0;
  }

  addToEnd(val) {
    let node = new Node(val)
    if(!this.head) {
      this.head = node
      this.tail = node
    }
    this.tail.next = node
    this.tail = node

    this.length++
    return this;
  }

  deleteFromEnd() {
    if(!this.head) return undefined
    let curr = this.head
    let newTail = curr

    while(curr.next) {
      newTail = curr
      curr = curr.next
    }
    newTail.next = null
    this.tail = newTail

    this.length--

    if(this.length === 0) {
      this.head = null;
      this.tail = null
    }
    return curr;
  }

  addToStart(val) {
    let node = new Node(val)

    if(!this.head) {
      this.head = node
      this.tail = node
    }
    node.next = this.head
    this.head = node

    this.length++

    return this;
  }

  deleteFromStart() {
    if(!this.head) return undefined

    let curr = this.head
    this.head = curr.next

    this.length--

    if(this.length === 0) {
      this.head = null
      this.tail = null
    }
    return null
  }

}
// creating a new instantiation of our linked list class called list.

let list = new LinkedList();
list.addToEnd(21)
list.addToEnd(24)
list.addToEnd(35)
list.addToStart(99)
list.deleteFromEnd()
console.log(list)
data structures