Data Structures in JavaScript

Overview:

Data structures provide a method of both storing and processing data. Each one has a "Best Case Use" and should be understood before using them. This Repository provides an implementation of these data structures that are best suited for primitive data types. This is due to the nature of JavaScript, dynamically typed, and probably should not be used in production.

List

The List is the most basic data structure. It is essentially an array, but this array is controlled by the add, remove, etc. functions. The list can be accessed by index, like the array, and can be treated very similarly to an array.

List Details:

1. List Size listSize - determines the length of the list. (Coincides with the number of elements in the list.)
2. Position pos - represents the current position in the list.
3. List Data listData - Private property that is the actual list, but the overarching class structure controls interactions with the array to enforce specific operations and access.
4. λ Clear : clear() - removes all elements from the list.
5. λ Find: find(element) - finds an element in the list based on the element passed.
6. λ ToString: toString() - Returns the array in whole for the purposes of printing the list.
7. λ Insert: insert(element, after) - Inserts an element passed to the function after the index passed to the function. returns true if successful, false if not.
8. λ Append: append(element) - Adds the provided element at the end of the list.
9. λ Remove: remove(element): removes the element passed to the function from the list.
10. λ Front: front(): sets the current position of the list as the first element. (index will be zero)
11. λ End: end(): sets the current position of the list as the last element. (index will be listData.length -1)
12. λ Prev: prev() - sets the current position of the list as the next lowest index.
13. λ Next: next() - sets the current position of the list as the next highest index.
14. λ Length: length() - returns the length of the list.
15. λ Current Position: currentPosition() - returns the index of the currently selected element of the list.
16. λ MoveTo: moveTo(position) - sets the current position of the list to the passed in index.
17. λ GetElement: getElement() - returns the currently selected element of the list.
18. λ Contains: contains(element) - returns true if the element is contained in the list, otherwise returns false.

Stack

The Stack is a Last In First Out (LIFO) data structure. To get an idea of an analog representation of a Stack, think of a physical stack of paper. For the purposes of consistency, we limit ourselves to only being able to add or remove items to the top of the stack. This means that the data structure is intended only to be accessed at one end of the structure.

Stack Details:

1. Data Store: dataStore - private property that is essentially an array of data, that is the underlying storage of the data.
2. Top: top - Represents the index of the underlying array, and the only point of entry into the stack. The top is the boundary that we access the stack.
3. λ Push: push(element) - Adds an element to the stack. Since we can only modify from the "top" of the stack, this new element becomes the top of the stack and will be the first returned by pop().
4. λ Pop: pop() - returns the element at the "top" of the stack. This also "removes" the item from the stack. (this item is not actually removed from the underlying array, it is simply "no longer the top", when a new element is added by push() it will be overwritten.)
5. λ Peek: peek() - Returns the element immediately below top. (top - 1)
6. λ Length: length() - returns the value of Top, which is essentially the number of elements remaining in the stack.
7. λ Clear: clear() - Sets top to 0. This essentially clears the entire stack of items. (Mainly because push() will overwrite any existing element that is above top)

Queue

The Queue data structure is similar to the Stack, because we can only access the data from one "end" of the structure, but instead of adding and removing from the same end, as in LIFO, we add and remove from opposite "ends" to create a First In First Out (FIFO) flow for this data structure.

Queue Key Terms

1. Enqueue - Means that we are adding to the queue.
2. Dequeue - Means that we are taking away from the queue.

Queue Details

1. Data Store: dataStore - Implemented as a private array, this serves as the basis of the queue.
2. λ Enqueue: enqueue(element) - Adds an element to the queue. (on the newest "end" of the queue.)
3. λ Dequeue: dequeue() - removes an element from the queue. (on the oldest "end" of the queue.)
4. λ Front: front() - returns the first element of the queue. (True 0 index of the underlying array.)
5. λ Back: back() - returns the last element of the queue. (True dataStore.length -1 index of the underlying array.)
6. λ To String: toString() - provides a string representation of the entire queue as currently instantiated.

Linked List

The Linked List is a data structure similar to the original list, except that instead the list isn't simply an array behind the scenes, and each element of the list is a "Node" object. The node is simply the value, and a pointer to the next node in the list. The pointer is the "Link" part of the linked list. The Linked List described can be called a "Singly Linked List" as each node in the list is linked to the next node in the list only. There are no "back" links to previous nodes.

Linked List Details

Linked Lists include Nodes and nodes are simply the value of the node, and a link to the next node denoted by the next property.

Node

1. Element: element - Value of the Node.
2. Next: next - Link to the next Node.

Linked List

1. Head: head - Represents the start of the Linked List.
2. λ Find: find(element) - finds the Node with the value passed to the function.
3. λ Insert: insert(newElement, item) - Creates a new Node to add to the list based on the newElement parameter. Then it finds the location in the list to add the new node, and inserts the new node in the appropriate spot in the Linked List.
4. λ Remove: remove(item) - Locates the item to be removed, and removes the item from the Linked List.
5. λ Display: display() - logs to the console each item in the Linked List.
6. λ Find Previous: findPrevious(item) - determines the node prior to the one passed as a parameter.

Doubly Linked Lists

The main difference between the previous Linked List, and the Doubly Linked List is that instead of each node having only a link to the next Node in the list each node has a next and prev properties that are links to the next and previous nodes respectively. This allows us to traverse the List in both directions.

Doubly Linked List Node Details

1. Element: element - Value of the Node
2. Next: next - Link to the next Node.
3. Prev: prev - Link to the previous Node.

Doubly Linked List Details

1. Head: head - Represents the start of the Doubly Linked List.
2. λ Find: find(element) - finds the element in the list and returns it.
3. λ Insert: insert(newElement, item) - inserts the newElement parameter as a new node just after the Node item in the list.
4. λ Display: display() - prints to the console the entire list in forward order, via each node's next property.
5. λ Remove: remove(item) - Removes the node with the specified element value from the list.
6. λ Find Last: findLast() - finds and returns the last node in the list.
7. λ Display Reverse: displayReverse() - Prints to the console the entire list in reverse order, using each node's prev property.

Dictionary

A dictionary is very similar to that of the Python Dictionary, and also similar to the standard JavaScript Object. It is a set of key/value pairs. Data is accessed by the keys only, and there is no traversal. Each value is returned when called by the key.

Dictionary Details

1. Data Store: dataStore - This is the basic underlying data structure of the Dictionary. It is literally a JavaScript Object, and could have been an array. I prefer the Object as we don't have to worry about additional indexes inside the data structure.
2. λ Add: add(key, value) - Adds the parameter value to the dictionary via the key parameter.
3. λ Find: find(key) - Returns the value represented by the key parameter.
4. λ Remove: remove(key) - Removes the value represented by the key parameter from the Dictionary.
5. λ Show All: showAll() - Prints to the console all key/value pairs in the dictionary. This is unsorted.
6. λ Show Sorted: showSorted() - Prints to the console all key/value pairs in the dictionary and is sorted.
7. λ Count: count() - Returns the number of key/value pairs in the dictionary.
8. λ Clear: clear() - Removes all key/value pairs from the Dictionary.