Data Structures everyone should know
- Contains VALUE and POINTER
x, y are of type ListNode. NOT in an Array
Ex: [x, ..., y]
-- Head node is "x"
---- Head node's "next" points to next Node
-- Tail node is "y"
---- Tail node's "next" points to null
PROS: Good at adding new nodes and deleting nodes
CONS: Retrieval
- Continuous block of cells in computer memory side-by-side
PROS: Retrieval
CONS: Adding elements, Searching
- Uses hashing functions to store in memory
- Blocks of memory don't have to be next to each other, can be stored anywhere
PROS: Retrieval, Adding/Removing keys
CONS: Collisions
- Last IN / First OUT
- push(n) IN, then pop() OFF the TOP
- Every language keeps track of the functions that have been called with a call stack.
- Important for Depth-first search (DFS)
- First IN / First OUT (like a real-life queue)
- Adding an item to the end is called enqueue-ing and removing it from the front is called dequeue-ing
- Used for Breadth-first search (BFS)
PROS: efficient to add & remove
CONS: limited use cases
- "Graph Theory"
- Similar to linked list, where we have NODES pointing to other NODES. Except in this case, the pointers are called EDGES.
- Edges can also have WEIGHTS assigned to them
- Example: Two cities can be NODES, while the distance between them is an EDGE
- Example: Social media networks can/are stored as graphs in order to facilitate complex user relationships
- A special kind of hierarchical graph called a TREE, in which the data expands out in ONE DIRECTION.
- Example: like an HTML tree with nexted elements:
<div id="parent">
<p id="child1">Hello</p>
<p id="child2">World</p>
</div>
- Has specific rules that let us do efficient searching
- Rules
- 0, 1, or 2 children (left or right, or both)
- Left Child Node < Parent Node
- Right Child Node > Parent Node
- We can traverse through a tree and always know where an element is
- BST is not the perfect data structure
- If you add elements in a weird order, it can get very "one-sided" (or imbalanced)
- However, self-balancing trees exist (these are advanced data structures):