Below is the list of important data structures
- Simple Data Structures
- Primitive Data Types
- Boolean
- Numbers
- String
- Structures (structs)
- Points (x & y coordinates), Color (red, green, blue, alpha)
- Objects (Custom Data Types)
- Collections
- Arrays
- single -dimensional arrays
- multi-dimensional arrays
- two-dimensional arrays (rectangular),
- three-dimensional arrays,
- and so on...
- Jagged arrays (ex. daily sales per month )
- Lists
- ArrayList (resizable, dynamic or mutable arrays)
- Vector
- Operations
- Appending (Push) - adding an element at the end
- Insertion / Add - adding in the middle at a specified index
- Removing (Pop) - deleting an element at the end
- Deletion - removing an element at a specified index
- Splice - (adding and removing)
- Search / Find / Contains - searching for an item and returning location
- Sort - ordering the data
- Linked List
- Singly Linked List
- Definition: A data structure consisting of a group of nodes where each node is composed of data and a reference (or a link) to the next node in the sequence.
- Operations
- Insertion
- Deletion
- Find / Search
- Traversal
- Iterative
- Recursive
- Reversal
- Iterative
- Recursive
- Doubly Linked List
- Definition: A data structure consisting of a group of nodes where each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
- The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
- Operations
- Insertion
- Deletion
- Traversal
- Reverse Traversal
- Circular Linked List
- Abstract Data Type
- Queue - First In, First Out
- Examples - Job Queue
- Operations
- Enqueue - adding an element at Last
- Dequeue - removing an element from Front
- Stack - Last In, First Out
- Operations
- Push
- Pop
- Peek
- Priority Queue
- Double-ended Queue (Deque) - supports adding deletion from both ends
- Hash-Based Data Structures
 |
hash table illustration, with three keys, funcbox, sparse range, no collisions, only the values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 3 -funcbox 1 -sparse 1 -keys 0 -values 1 -collisions 0 -links 0 -overflow SP (Photo credit: Wikipedia)  hash table illustration, with three keys, sparse range, buckets are links, collisions resolved by separate chaining, keys and values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 5 -funcbox 0 -sparse 1 -keys 1 -values 1 -collisions 1 -links 1 -overflow LL (Photo credit: Wikipedia) |
- Associative Arrays
- Invariants
- Unique Keys
- Operations
- Add
- Remove
- Hash Tables / Hash Map / Dictionaries
- create with an initial capacity
- Hash Collision
- separate chaining
- Set / HashSet
- unordered collection of objects
- No sequence
- No duplicates
- Fast lookup - for checking membership, not retrieval
- Operations
- add
- remove
- contains
- Tree
- Binary Tree
 A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. (Photo credit: Wikipedia) |
- Binary Search Tree
- invariants
- no duplicates
- operations
- add
- delete
- find
- traverse
- pre-order
- in-order
- post-order
- Self Balancing Trees
- AVL Tree
- Red-Black Tree - (implementation of TreeMap in Java uses this)
- Scapegoat Trees
- Splay Trees
- Segment Tree (for min/max/sum range queries)
- Fenwick Tree (Binary Indexed Tree)
- Heap (Min Heap or Max Heap)
 | |
|
Related articles
Singly Linked List class using Collection hierarchy C++(stackoverflow.com)
Five Myths about Hash Tables(hughewilliams.com)
Open Data Structures: an open content textbook(opendatastructures.org)
Implementing a binary tree using linear linked lists(en.nerdaholyc.com)
No comments:
Post a Comment