Data Structures

The kind that mostly relevant to interviews, if we’re being honest.

Queue

TODO

Stack

TODO

Graph

TODO

Linked List

Linked lists can be singly linked or doubly linked. Each node in a singly linked linked list has a next property, but no prev property. Therefore, it’s possible to walk forward but not backwards. Each node in a doubly linked linked list has a prev property in addition to next; it is possible to walk backwards from any node.

Strictly speaking, most operations in a linked list are constant time. Adding a node, removing a node, etc. are all constant time ASSUMING you don’t need to walk the list. Walking the list will kill you. Also, if we think about a list as a continguous chunk of memory that we’re dealing with, in the traditional sense, then we can consider different ways of accessing a node apart from walking the list.

Think of linked list operations as exclusive from walking the list.

Tree

TODO