Topics:
- Linked Lists
- Queues
- Binary Search Trees
- Heaps
-
Set up your repository by running
npm install
in your root directory to install all necessary dependencies. -
Implement each data structure, starting with the linked list data structure. Run
npm test <filename>.test.js
to run the tests for that data structure and check your progress. Get all the tests passing for each data structure. -
Open up the
Data_Structures_Questions.md
file, which asks you to evaluate the runtime complexity of each of the methods you implemented for each data structure. Add your answers to each of the questions in the file.
- Should have the methods:
addToTail
,removeHead
,contains
, andgetMax
.addToTail
replaces the tail with a new value that is passed in.removeHead
removes and returns the head node.contains
should search through the linked list and return true if a matching value is found.getMax
returns the maximum value in the linked list.
- The
head
property is a reference to the first node and thetail
property is a reference to the last node. Build your nodes with objects.
- Should have the methods:
enqueue
,dequeue
,isEmpty
and alength
getter.enqueue
should add an item to the back of the queue.dequeue
should remove and return an item from the front of the queue.isEmpty
should returntrue
if the queue contains no elements,false
otherwise.- A
length
getter that returns the number of items in the queue.
- Should have the methods
insert
,contains
,getMax
.insert
adds the input value to the binary search tree, adhering to the rules of the ordering of elements in a binary search tree.contains
searches the binary search tree for the input value, returning a boolean indicating whether the value exists in the tree or not.getMax
returns the maximum value in the binary search tree.
- Should have the methods
insert
,delete
,getMax
,bubbleUp
, andsiftDown
.insert
adds the input value into the heap; this method should ensure that the inserted value is in the correct spot in the heapdelete
removes and returns the 'topmost' value from the heap; this method needs to ensure that the heap property is maintained after the topmost element has been removed.getMax
returns the maximum value in the heap in constant time.bubbleUp
moves the element at the specified index "up" the heap by swapping it with its parent if the parent's value is less than the value at the specified index.siftDown
grabs the indices of this element's children and determines which child has a larger value. If the larger child's value is larger than the parent's value, the child element is swapped with the parent.
-
Implement a doubly-linked list class that adheres to the following specification. Uncomment the tests in the
tests/doubly-linked-list.test.js
file in order to test your solution.-
Consists of a
DoublyLinkedList
class and aListNode
class. -
The
ListNode
class has the methodsinsertAfter
,insertBefore
, anddelete
.insertAfter
inserts a new node with the input value after the calling node.insertBefore
inserts a new node with the input value before the calling node.delete
should remove the calling node from the list (think about what that means).
-
The
DoublyLinkedList
class, like theLinkedList
class, holds references to thehead
of the list as well as thetail
; it has the methodsaddToHead
,removeFromHead
,addToTail
,removeFromTail
,moveToFront
,moveToBack
, anddelete
addToHead
creates a new node with the input value and adds the new node as the new head of the list.addToTail
creates a new node with the input value and adds the new node as the new tail of the list.removeFromHead
removes the current head of the list; the current head's next node should be designated as the new head.removeFromTail
removes the current tail of the list; the current tail's previous node should be designated as the new tail.moveToFront
receives a node and moves that node (if it exists in the list) to the front of the list as the new head.moveToBack
receives a node and moves that node (if it exists in the list) to the back of the list as the new tail.delete
receives a node as input and deletes that node from the list.
-