Data Structures
TBD. All sorts of fun data structures. Discussion on memory management.
The best reference for Data Structures and Algorithms is "the big book" aka: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. If you ever want to be any good at software development read this. It can even be found for free online eg. here or here. But if you're going to program a bunch, bite the bullet and get yourself a copy (new or used).
Note: The cool thing about data structures is that they are completely independent of programming. They're representations for ways of working with data, and can be envisioned and constructed even if the hardware doesn't (yet) exist, or isn't advanced enough to implement. For example, we can envision data structure - and subsequently algorithms for - mainstream quantum computers even though we haven't got them mainstream yet.
⏵ Simple Structures
Stacks
- Last In, First Out (eg. Pringles chip box)
Queues
- FIFO: First In, First Out (eg. waiting in line at the store)
Linked Lists
- Node stores value and next node. Datastructure stores pointer to first node. Last node's next node points to nullptr
Double Linked List
- Node stores value, next node, and previous node. Datastructure (normally) stores pointer to first node. First and last point to nullptr for their previous node, and next node respectively.
Circular Linked Lists
- Node stores value and next node. Data structure stores pointer to one of the nodes. Each node has a valid (non-null) next node.
- Be mindful of memory management - easy to leak!
Trees
- Node stores value, and children nodes. Data structure points to the root node of the tree. A "leaf" in a tree, is a node which has no children.
- Usually trees are "DAGs" (directed, acyclic graphs). ie. They don't point back on themselves, or to other nodes in the tree - they all flow one way. Exceptions include doubly-linked trees, but in that case it a node stores a value, children nodes, and a reference back to its parent (parent node). These are still considered DAGs.
⏵ Hashing Structures
Direct-Address Tables
Hash Tables
⏵ Intermediate Trees
Binary Search Trees
- A node has at most two children. Often used for log(n) access, and sorting algorithms.
- There is the concept of "balancing" a tree, which means to organize the tree so that for any node, the number of children on the "right" is roughly equal to the number of children on the "left". This improves access times and avoids worse-case scenarios (when eg. all nodes live down a single branch, degenerating into a linked list).