# Data Structures

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

### Queue

A queue, like a real-life queue (as in a line), is a FIFO (first-in first-out) data structure. Generally it has two methods: `enqueue`

for putting stuff into the queue, and `dequeue`

for taking stuff off the queue. Also `peek`

to see what is at the front of the queue.

```
interface Queue<T> {
enqueue(item: T): void
dequeue(): T
peek(): T
}
```

### Stack

Stack is just like queue, but LIFO (last-in first-out). It’s like a stack of plates in a kitchen — last one added to the pile is the first one you take off the top.

```
interface Stack<T> {
push(item: T): void
pop(item: T): T
head: T
}
```

### Graph

A graph is a non-directional collection of nodes(vertices) that are related to eachother. Each relation between nodes is known as an edge.

```
interface GraphNode<T> {
value: T;
neighbors: Set<GraphNode<T>>;
}
interface Graph<T> {
vertices: GraphNode<T>[];// set of vertices (nodes)
hasNode(node: GraphNode<T>): boolean;
addVertex(value: T): void; // Add a vertex to the graph
addEdge(vertex1: GraphNode<T>, vertex2: GraphNode<T>): void; // Add an edge between two vertices
removeVertex(value: T): void; // Remove a vertex from the graph
removeEdge(vertex1: GraphNode<T>, vertex2: GraphNode<T>): void; // Remove an edge between two vertices
getNeighbors(value: T): Set<T>; // Get the set of neighboring vertices for a given vertex
size(): number; // Get the number of vertices in the graph
}
```

### 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

### Binary Tree

TODO

### Heap

TODO

### Hash-Set, Hash-Table, Hash-Map

TODO

*Last modified: March 10, 2023*