jcuffe/data-structures

Data Structures

Topics:

• Linked Lists
• Queues
• Binary Search Trees
• Heaps

Tasks

1. Set up your repository by running npm install in your root directory to install all necessary dependencies.

2. 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.

3. 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.

Linked Lists

• Should have the methods: addToTail, removeHead, contains, and getMax.
  • 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 the tail property is a reference to the last node. Build your nodes with objects.

Queues

• Should have the methods: enqueue, dequeue, isEmpty and a length 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 return true if the queue contains no elements, false otherwise.
  • A length getter that returns the number of items in the queue.

Binary Search Trees

• 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.

Heaps

• Should have the methods insert, delete, getMax, bubbleUp, and siftDown.
  • insert adds the input value into the heap; this method should ensure that the inserted value is in the correct spot in the heap
  • delete 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.

Stretch Goals

1. 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 a ListNode class.

   • The ListNode class has the methods insertAfter, insertBefore, and delete.

     • 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 the LinkedList class, holds references to the head of the list as well as the tail; it has the methods addToHead, removeFromHead, addToTail, removeFromTail, moveToFront, moveToBack, and delete

     • 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.
     • moveToBackreceives 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.