Class4.md

Class 4: Arrays & Linked Lists

Topics

• Compare abstract data types and concrete data structures
• Abstract data types: list
• Concrete data structures: array, dynamic array (resizable array, vector), linked list

Resources

• Review Make School's array and linked list slides
• Watch Make School's array and linked list video lecture
• Read Vaidehi Joshi's articles on linked lists, part 1: how they work and part 2: complexity analysis and comparison to arrays with excellent, beautiful drawings
• Watch HackerRank's linked list video
• Watch Harvard's array video, singly linked list video, and doubly linked list video
• Play with VisuAlgo's interactive linked list visualization

Challenges

• Add new features to LinkedList class using linked list starter code:
  • Add size property that tracks list length in constant running time
  • Implement get_at_index(index) - returns the item at index in the list
  • Implement insert_at_index(index, item) - inserts item at index (all items after index are moved down)
  • Implement replace(old_item, new_item) - replaces old_item in the list with new_item using the same node
  • Run python linkedlist.py to test LinkedList class instance methods on a small example
  • Run pytest linkedlist_test.py to run the linked list unit tests and fix any failures
• Annotate methods with complexity analysis of running time and space (memory)

Stretch Challenges

• Implement DoublyLinkedList class with BinaryNode objects, which have both next and previous properties
• Write unit tests for to ensure the DoublyLinkedList class is robust
  • Include test cases for each class instance method and property
• Annotate methods with complexity analysis of running time and space (memory)