The second datastructure!

This should be a time filled with exuberance!

I said something weird earlier.

I said that JavaScript arrays, const a = []; is not an array. We know have a solid definition of an array, is it an array (yes someone answer)? And why not?

Next you are going to say HTML isn't a programming language

  • neovim is the only true editor
  • rust is the greatest language
  • linux is the only machine you should develop on

So lets go to our real first data structure

Its hard to call Array a data structure because its so fundamental. Its something that is available in every language except the one in this course because... JavaScript.

So what sucks about an Array?

  • Deletion (why?)
  • Insertion (why?)
  • Its ungrowable (why?)

Lets talk LinkedList

So how does it work? (whiteboard)

  • Singly Linked
  • Doubly Linked

Lets talk time / space complexity

  • prepend / append
  • Insertion in the middle
  • Deletion from ends
  • Deletion in the middle
  • Get head / tail
  • Get in general

We wont implement unless we have lots of time

But here is the api

interface LinkedList<T> {
    get length(): number;
    insertAt(item: T, index: number): void;
    remove(item: T): T | undefined;
    removeAt(index: number): T | undefined;
    append(item: T): void;
    prepend(item: T): void;
    get(index: number): T | undefined;