ELI5: Data Structures Basics
What are data structures and why does it matter for coding?
When given a set of data values, the data can be formatted to fit certain parameters (or structures) to improve data access, manipulation, and modification. By focusing on these aspects, the user benefits from efficient and quick responses from a software system.
Amongst the variety of data structures, eight are commonly implemented — arrays, linked lists, stacks, queues, hash tables, trees, binary search trees, heaps, and graphs.
Arrays: a collection of variables (all the same data type) stored contiguously and sequentially in memory; each element has a specific index that allows it to be identified and accessed. Arrays have a fixed length of elements (static array) but can be expanded by creating a copy of the elements and increasing the capacity (dynamic array).
Linked Lists: a chain of nodes composed of its data and a pointer referring to its succeeding node. Aside from a node’s pointer, the linked list contains a head pointer indicating where the start of the list exists; if the list is empty the head pointer points to null. Linked lists are applied to implement file systems, hash tables, and adjacency lists.
Stacks: a linear data structure that follows the last-in-first-out (LIFO)/ first-in-last-out (FILO) method; a real-life example is if your favorite book were in the middle of a stack of books, all the books “pushed” onto the stack after it needs to be popped off before your favorite book can be accessed.
Queues: a linear data structure that follows the first-in-first-out (FIFO) method.
Hash Tables: one definition of hash is “to chop and mix” — in this case, data inputs are “chopped” into pieces and “mixed” into your data table non-sequentially and non-contiguously., The data is accessible through the use of key:value pairs in a table and improves the average time complexity to O(1) for search, insert, and delete methods.
Trees: a nonlinear data structure with nodes connected by directed or undirected edges. One node is designated as the root and the tree expands from parent to child. At the end of the tree are leaf nodes which have no child notes.
Binary Search Tree (BST): a type of tree with the left child node holding keys lesser than the parent node and the right child node holding keys greater than the parent node. Binary search trees can be balanced (applying a data algorithm to rearrange the nodes to prevent poor data arrangement [ex. formatting data to look like a linked list which has a less ideal search complexity of O(n)]. An advantage of a BST is quick lookup, addition and removal of data items, and implementation of data sets and lookup tables; the order of the nodes in a BST allows for comparison algorithms to skip about half of the tree nodes.
Heaps: another type of tree-based data structure that holds a heap property (can be thought of as a rule for the tree’s construction). Common heaps are max heaps and min heaps. The max heap’s root node holds the key with the highest value and the min heap’s root node holds the key with the lowest value. This heap property holds true recursively for sub-trees in the heap.
Graphs: a non-linear/network-like data structure with nodes that are connected to each other by edges (lines). Examples of graph-usage include paths in a city or a telephone network.
References:
1 https://www.bigocheatsheet.com/
2 https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
3https://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_1.htm
https://www.cs.cmu.edu/~rdriley/121/notes/hashtables.html
https://www.cs.cmu.edu/~tcortina/15-121sp10/Unit06A.pdf
https://www.freecodecamp.org/news/hash-tables/
https://www.freecodecamp.org/news/the-top-data-structures-you-should-know-for-your-next-coding-interview
https://www.geeksforgeeks.org/binary-search-tree-data-structure/
https://www.geeksforgeeks.org/binary-tree-data-structure/
https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
https://www.geeksforgeeks.org/heap-data-structure/
https://www.geeksforgeeks.org/data-structures/linked-list/
https://www.geeksforgeeks.org/stack-data-structure/
https://www.geeksforgeeks.org/queue-data-structure/
http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/09/basics.html
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec08.pdf
https://softwareengineering.stackexchange.com/questions/108124/why-it-is-called-hash-table-or-hash-function-hash-doesnt-make-any-sense-t
https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42
https://en.wikipedia.org/wiki/Binary_search_tree
https://en.wikipedia.org/wiki/Heap_(data_structure)
