# Data Structures

## Linked List

A Linked list is a group of nodes which together represent a sequence. linked list contains 2 things.

- The actual data being stored
- The next location or pointer to the next node

`head['data', pointer(1)]`

-> `1['data', pointer(2)]`

-> `tail['data', null]`

Code:

```
function linkedList() {
let size = 0; //size of our linked list
let head = null; // pointer to next location
// create new node
const Node = function(element) {
this.element = element;
this.next = null;
}
this.size = (() => {
return size;
});
this.head = (() => {
return head;
});
this.add = ((element) => {
const node = new Node(element);
if (head === null) {
head = node;
} else {
let currentNode = head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
size++;
});
this.remove = ((element) => {
let currentNode = head;
let previousNode;
if (currentNode.element === element) {
head = currentNode.next;
} else {
while (currentNode.element !== element && currentNode.next) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
size--;
});
this.empty = (() => {
return size === 0;
});
this.indexOf = ((element) => {
let currentNode = head;
let index = -1;
while (currentNode) {
index++;
if (currentNode.element === element) return index;
currentNode = currentNode.next;
}
return -1;
});
this.elementOf = ((index) => {
let currentNode = head;
let count = 0;
while (index > count) {
currentNode = currentNode.next;
count++;
}
return currentNode.element;
});
}
```

## Stacks

A stack is a basic data structure where things can only be added or removed from the top. First in Last out approach and this is how recursion fundamentally works.

Methods:

- Push -> Insert onto the stack
- Pop -> Remove from the stack
- Pip -> View the stack

```
function stack() {
this.count = 0;
this.data = {};
this.push = function(value) {
this.data[this.count] = value;
this.count++;
};
this.pop = function() {
if (this.count === 0) return undefined;
this.count--;
const result = this.data[this.count];
delete this.data[this.count];
return result;
};
this.pip = function() {
return this.data[this.count-1];
};
this.length = function() {
return this.count;
};
}
```

## Queue

A Queue is essentially a waiting line. First in, First out approach.

Methods:

- Enqueue -> insert to the queue
- Dequeue -> remove from the queue

```
function queue(){
const que = [];
this.enqueue = ((element) => {
que.push(element);
});
this.dequeue = (() => {
return que.shift();
});
this.length = (() => {
return que.length;
});
}
```

## Sets

The set data structure stores values without any particular order with no repeated values.

Methods:

- Add
- Remove
- Union -> Combines all elements from 2 different sets -> returns new deduped set.
- Intersection -> Compares 2 or more sets and returns a new set with items that are in all sets.
- Difference -> Returns new set with items that are not in a different set.
- Subset -> returns a boolean if all items in Set A are in Set B

## Maps

A map is a data structure that stores data in key value pairs. Maps are sometimes referred to as dictionaries.

Methods:

Crud

```
function map(){
let data = {};
let count = 0;
this.add = ((key, value) => {
console.log(value);
data[key] = value;
count++;
});
this.has = ((key) => {
return (data[key] !== undefined);
});
this.get = ((key) => {
return data[key];
});
}
```

## Hash Table

A hash table is a map or array data structure that uses a hash function to locate the index of the requested data in an array.

String -> hashFunction(string) -> Array(int). See more on hashe tables here

## Binary Search Tree

A tree is a data structure consisting of nodes. Each tree has a root node and each child has 0 or more children. Each child also has 0 or more children. See more on binary trees here

## Trie

A prefixed tree is a kind of search tree. Trie stores data in steps where each step is a node in the tree. Trie are most commonly used to store words for quick lookup, such as auto-complete or auto-correct features we all love and hate. Each node contains 2 things.

- The data like the letter "A"
- Boolean value signaling a stopping point like the end of a word

The Root of the trie is almost always blank and works from top down.

## Binary Heap

Tree data structure, every node at most has 2 children and is filled from left to right. Read more about how a heap can be used to sort data here