Data Structures: Linked List

Big O Notation

• Insertion: O(1)
• Deletion: O(1)
• Lookup: O(n)

Linked List Uses

• Stack
• When doing a lot of insertion
• When you do not need random access
• Javascript doesn't have many uses for linked lists because of the nature of arrays
• See this article: C++ Heap Memory vs Stack Memory

class Node {
  constructor(data, next) {
    this.data = data
    this.next = next || null
  }
}

class LinkedList {
  constructor(){
    this.head = null
    this.count = 0
  }

  insert(val) {
    if (this.count === 0) {
      this.head = new Node(val)
    } else {
      this.head = new Node(val, this.head)
    }
    this.count++
  }

  remove() {
    if(!this.head) {
      err.log('Cannot remove from empty list')
    } else {
      this.head = this.head.next
      count--
    }
  }

  traverse(cb) {
    let iter = this.head
    while (iter) {
      cb(iter.data)
      iter = iter.next
    }
  }
}

Pseudoclassical Style

const Node = function(data, next) {
  this.data = data
  this.next = next || null
}

const LinkedList = function() {
  this.head = null
  this.count = 0
}

LinkedList.prototype.insert(val) {
  if(this.count === 0) {
    this.head = new Node(val)
  } else {
    this.head = new Node(val, this.head)
  }
}

LinkedList.prototype.remove() {
    if(!this.head) {
      err.log('Cannot remove from empty list')
    } else {
      this.head = this.head.next
      count--
    }
}

LinkedList.prototype.traverse(cb) {
  let iter = this.head
  if (!this.head) {
    const err = new err('List is empty!')
  }
  while (iter) {
    cb(iter.data, err)
    iter = iter.next
  }
}