Linked Lists

read this

it's a great, simple introduction to what a linked list is: https://medium.com/@ConnorFinnegan/a-beginners-guide-to-linked-lists-f047a4f929ae

but to sum it up, let's try and think of it compare to an array.

example of a linked list in action

ref

this is how to make a linked list:

// essentially it's a thing that holds two things
// 1. singly linked list
class LinkedListNode {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

// create the first node
const head = new LinkedListNode(12) // by convention it's just called a head

// add a second node
head.next = new LinkedListNode(99)

// add a third node
head.next.next = new LinkedListNode(37)

and this is how you traverse (read stuff)

let current = head
while (current !== null) {
  console.log(current.data)
  current = current.next
}

Most linked list operations use this traversal algorithm or something similar, so understanding this algorithm is important to understanding linked lists in general. - humanwhocodes author

that's it!

// an array looks like this
const array = [1, 3, 4]

// the internals of a linked list SHOULD look like this i think
const linkedListItem0 = { data: 1, next: linkedListItem1 }
const linkedListItem1 = { data: 3, next: linkedListItem2 }
const linkedListItem2 = { data: 4, next: null }

how to add an item in between two items in a linked list

// [1,3,4]
const linkedListItem0 = { data: 1, next: linkedListItem1 }
const linkedListItem1 = { data: 3, next: linkedListItem2 }
const linkedListItem2 = { data: 4, next: null }

// 1. make object
const linkedListItemZ = { data: 2, next: null } // new
// 2. link object to next item
const linkedListItemZ = { data: 2, next: linkedListItem1 } // new
// 3. edit previous item to point to new item
// const linkedListItem0 = { data: 1, next: linkedListItem1 }
const linkedListItem0 = { data: 1, next: linkedListItemZ } // update item 0 to point to Z
const linkedListItemZ = { data: 2, next: linkedListItem1 } // new
const linkedListItem1 = { data: 3, next: linkedListItem2 }
const linkedListItem2 = { data: 4, next: null }
// [1,2,3,4]