dtst
A collection of data structures to use, with comments and examples. Still a work in progress!
What's included
Usage
Tree
Trees are commonly used data structures for storing hierarchical information, such as a file system on a computer (think about navigating through directories and their sub-directories).
; // create an instance of Treevar tree = ; // create the first node in the tree and store the node instance in variable "root"var root = tree; // add three child nodes, which are attached to the root node by defaultvar child_1 = tree;var child_2 = tree;var child_3 = tree; // attach children to different nodes by specifying a parent node as a second argumentvar grandChild_1 = tree;var grandChild_2 = tree;var grandChild_3 = tree;var greatGrandChild_1 = tree; /*** Tree structure: root + child_1 + grandChild_1 + grandChild_2 + child_2 + grandChild_3 + greatGrandChild_1 + child_3 ***/ // check if the tree contains a valuetree; // -> returns child_2tree; // -> returns false // delete a node and its descendantstree;tree; // -> returns falsetree; // -> returns falsetree; // -> returns falsevar size = treesize; // -> 5
Trie
Tries (also known as radix trees or prefix trees) have an ordered data structure that is efficient for information retrieval. There are several ways to construct a Trie, but they all share a tree structure. Each node can represent a single character string, and traversing down a tree can build words or prefixes. A few useful application for Tries: dictionary suggestions, autocomplete dictionaries, searching through a contact list, or searching through phone directories.
; // create an instance of Trievar trie = ; // populate the Trie with a collection of 100 wordsconst collection = "abrupt" "acid" "adventurous" "ahead" "amused" "appliance" "attach" "bee" "better" "borrow" "bouncy" "branch" "brave" "bushes" "business" "cagey" "carpenter" "cattle" "chin" "cloth" "confuse" "consist" "cool" "count" "craven" "deep" "digestion" "ear" "escape" "evasive" "even" "examine" "fit" "flood" "frequent" "furtive" "gather" "graceful" "grumpy" "guiltless" "half" "hand" "handy" "hate" "hose" "ill-fated" "jail" "kaput" "likeable" "limit" "look" "malicious" "meaty" "mere" "mine" "moaning" "monkey" "nail" "neck" "nippy" "noise" "obedient" "obeisant" "observant" "order" "park" "penitent" "perform" "press" "queue" "quickest" "quince" "racial" "remember" "remind" "replace" "ripe" "roll" "safe" "satisfy" "school" "serious" "shop" "slip" "slope" "small" "spark" "squeamish" "stiff" "store" "supply" "swim" "taste" "tiny" "trees" "use" "useful" "volcano" "vulgar" "whispering";collection; // check if certain words or prefixes existtrie; // -> truetrie; // -> truetrie; // -> truetrie; // -> false // autocomplete or predict words based off a given prefixtrie; // -> ["abrupt", "acid", "adventurous", "ahead", "amused", "appliance", "attach"]trie; // -> ["confuse", "consist"]trie; // -> [] // remove prefixes and their descendant wordstrie;trie; // -> falsetrie; // -> falsetrie; // -> truetrie; // -> ["racial", "replace", "ripe", "roll"]
Binary Search Tree
Binary Search Trees efficiently store data in a sorted form that allow fast lookup, addition, and removal of items. BST operations uses the principle of binary search when traversing the tree, so lookup/insertion/deletion operations work approximately at logarithmic time complexity.
; // create an instance of BinarySearchTreevar bst = ; // insert key/value pairs, where the key is a unique number (used to determine how data is sorted)bst; // the root nodebst;bst;bst;bst;bst;bst;bst;bst;bst; // search for a value given a keybst; // -> 'ten'bst; // -> 'three'bstsize; // -> 10 // update a value given its keybst;bst;bst; // -> 'I am the root node!'bst; // -> 'I ate eight' // remove nodes corresponding to a key// note: this may cause nodes to be rearranged to maintain the sort patternbst;bst; // removes the root node bstsize; // -> 8bst; // -> nullbst; // -> nullbst; // -> 'I ate eight'bsthead; // -> Node instance { key: 7, value: 'seven' }
Graph
Graphs are vertices (nodes) connected by edges. In fact, a tree data structure can be considered a type of graph. Graphs are useful for anything network related, routing, finding relationships, etc. Connections with friends on social media, Google Maps finding a route based on shortest routes, internet pages linked by hyperlinks, are all real life applications of graphs.
; // create an instance of Graphvar graph = ; // add verticeslet sanFrancisco = graph;let sanJose = graph;let sacramento = graph;let losAngeles = graph; // connect vertices with edges// edges can be given an optional numeric weight, which defaults to 0// note: edges are directional, meaning an edge from A to B does not mean an edge from B to Agraph;graph;graph;graph;graph;graph; // get neighbors (direct connections) of a vertexsanFrancisco; // -> { 'Sacramento', 'San Jose', 'Los Angeles' }losAngeles; // -> { 'San Francisco' }sanJose; // -> { 'Sacramento', 'San Francisco' }sacramento; // -> { } // remove an edge between two verticesgraph;sanFrancisco; // -> { 'Sacramento', 'San Jose' }losAngeles; // -> { 'San Francisco' } // remove a vertex, which will also remove connections to and from that vertexgraph; // graph.removeVertex('San Francisco') will also worklosAngeles; // -> { }sanJose; // -> { 'Sacramento' }
Heap
Heaps are tree-based data structures where the parent-child ordering is consistent across the whole heap. In a min heap, every parent node's key is smaller than its children; therefore the root node will always contain the smallest node. In a max heap, every parent node's key is larger. They are useful for keeping track of the smallest (or largest) value in a stream of data. Heaps are often implemented in priority queues.
; // create an instance of MinHeapvar heap = ; // insert some data into the heapconst numbers = 42 9 5 12 11 99 1 23 28 33 20;numbers; // peek at the minimum element (the root element)heap; // -> 1 // extract or remove the minimum element// the heap will be re-arranged with the next smallest element as the rootheap; // -> 1heep; // -> 5 // keys correspond to a particular index location of an arrayheap; // -> 1 (5 is the smallest element, thus it's at the first index) // delete an element based on its index locationheap; // deleting the first element is essentially the same as heap.extract()heap; // -> 9
Linked List
Linked lists are linear collections of nodes where each node has a reference to the next node in line. In a doubly linked list, each node has a reference to the next and previous node. Linked Lists are advantageous over arrays because insertion/deletion operations involve a simple rearrangement of pointers. The same operations on an array require reorganizing the structure because the data is stored contiguously in memory. Linked lists can be used in creating stacks and queues to avoid pre-allocating memory for all elements.
; // create an instance of LinkedListvar list = ; // insert values into the linked list// use .search(value) to get a node from the list with the given value to be used as a reference'A' 'B' 'C' 'D' 'E';list;/*** (HEAD) --> ZERO --- A --- B --- C --- D --- E <-- (TAIL) ***/list;list;list;/*** (HEAD) --> ZERO --- A --- B --- C --- foo --- D --- E --- F --- bar <-- (TAIL) ***/list; // -> 9 // delete nodes from the linked listlist;list;/*** (HEAD) --> A --- B --- C --- foo --- D --- E --- F <-- (TAIL) ***/list;list;/*** (HEAD) --> A --- B --- C --- D --- E <-- (TAIL) ***/ // reverse the linked listlist;/*** (HEAD) --> E --- D --- C --- B --- A <-- (TAIL) ***/