Haemin Park | DS & A

What is a linked list?

A data structure that contains a head, tail and length property. Linked lists consist of nodes (elements), and each node has a value and a pointer to another node or null.

Since there are no indices, we have to go over each element one by one. Nodes in a singly linked list are connected to only one other node.

Lists

Do not have indexes
Connected via nodes with a next pointer
Random access is not allowed (let's say we want the 10th item. Then we'd have to traverse to the 10th item).

Arrays

Indexed in order
Insertion and deletion can be expensive (because every other element has to be re-indexed)
Can quickly be accessed at a specific index

Pushing

In a singly linked list, we can push new nodes in the list like this:

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
 
class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }
  push(val) {
    let newNode = new Node(val)
    if (!this.head) { // if it's the first element being pushed in the list
      this.head = newNode
      this.tail = this.head
    } else {
      this.tail.next = newNode;
      this.tail = newNode
    }
    this.length++
    return this;
  }
}

let list = new SinglyLinkedList()
console.log(list)
list.push("HELLO")
console.log(list)
list.push("HOW ARE YOU?")
console.log(list)
list.push("I'm TIM")
console.log(list)

SinglyLinkedList { length: 0, head: null, tail: null }
SinglyLinkedList {
  length: 1,
  head: Node { val: 'HELLO', next: null },
  tail: Node { val: 'HELLO', next: null }
}
SinglyLinkedList {
  length: 2,
  head: Node { val: 'HELLO', next: Node { val: 'HOW ARE YOU?', next: null } },
  tail: Node { val: 'HOW ARE YOU?', next: null }
}
SinglyLinkedList {
  length: 3,
  head: Node {
    val: 'HELLO',
    next: Node { val: 'HOW ARE YOU?', next: [Node] }
  },
  tail: Node { val: "I'm TIM", next: null }
}

We can see that the nodes are being added nicely.

Singly Linked Lists

What is a linked list?

Pushing