by Yung L. Leung
Real world data structures: tables and graphs in JavaScript
An aerial view of boxes with addresses, each containing people & various items, shows neighborhoods connected by their roads. Viewed up close, you may say that we have a hash table. But, when viewed from afar, you might see a graph. Advancing from linear (linked lists, stacks & queues) and binary (binary search trees, binary heaps) data structures, hash tables, and graphs are steps towards a greater diversity of real-world applications.
Tables
A hash table represents data (key-value pairs) tabulated by indexes.
Each unique key is used to generate an index (hash function). A hash function can generate the same index for several unique keys (collision). A solution to this problem is to store the data sets under the same index (chaining).
So, you can imagine a hash table being a system for shelving similar items together. Simply enter the item name into a hash function and all the greenish type items will be assigned a shelf space, i.e. 4.
In general, a key-value pair insert requires generating an index (shelf number), checking whether that shelf exists, and placing the item (data) on the shelf. Suppose I had bananas and apples on the bottom shelf (index 0) and red wine on my top shelf (index 2).
If my index generator (hash function) returned an index 2 for my 2 “rotisserie chickens,” to insert that data requires checking for and creating shelf space.
To get a value (item) requires inputting its name (key) to generate its index (shelf number) and retrieving all items on that shelf. Then searching for the exact item (its name or key) and retrieving it (return value). So, to find how many apples are in stock (20) requires iterating through my shelf of fruits.
To get a list of all keys or values requires searching through each existing shelf, logging it into your manifest (push into an array), and submitting the documents (return keys or values array).
The complexity to insert a key-value pair or access a value is, in general, a constant time (O(1)). A good hash function evenly distributes all items to all available shelves. So, insertion or access does not require looping through all existing “shelves” for storage or retrieval of data.
Because cataloging (keys or values) requires going through all shelves, it has a complexity O(n). For n different data sets (for 4 different items), requires n steps to perform a catalog (requires looking through all 4 items to document its name or its quantity).
Graphs
A graph is nodes (vertices) of data related by their connections (edges). A road map of cities connected by their roads is a graph. A graph of connected users from a social media app is another example.
To add a vertex and an edge requires storing them as key-value pairs in an adjacency list. So a vertex (New York) can be connected to other vertices (New Jersey & Pennsylvania) by making “New York” a key to an array containing “New Jersey,” “Pennsylvania.”
The reverse must also be implemented, i.e.: “New Jersey” pointing to an array of “New York,” “Pennsylvania,” and so forth. So the result is an adjacency list of keys (“New York,” “New Jersey,” “Pennsylvania”), each pointing to arrays of their corresponding connections.
To remove edge requires removing vertex1’s connection to vertex2 and the reverse. So, to remove New York’s connection to New Jersey requires, also, removing New Jersey’s connection to New York.
To remove a vertex requires iterating through its connections. Removing its edges, before finally deleting the vertex from the adjacency list. So, to remove New York requires disconnecting it from its neighbors before deleting from the list.
Relative to a starting point, a depth-first traversal involves visiting a neighbor and its neighbors, before proceeding with the next immediate neighbor. A breadth-first traversal involves visiting all immediate neighbors before distant neighbors.
So for a graph with New York, New Jersey, Pennsylvania & Virginia as vertices, a depth-first traversal starting from New Jersey would be [“New Jersey”, “Pennsylvania”, “Virginia”, “New York”].
A breadth-first from New Jersey would be [“New Jersey”, “New York”, “Pennsylvania”, “Virginia”].
Since a graph is a set of nodes connected, linear & binary data structures can, in a sense, be viewed as simple graphs. Because graphs can take many different forms & shapes, the complexity of traversal through a graph depends on the algorithm(s) used for the traveling, a discussion best saved for another time.
References:
https://www.udemy.com/js-algorithms-and-data-structures-masterclass/