Class4.md

Class 4: Arrays & Linked Lists

Minute-by-Minute [OPTIONAL]

NOTE: Fill in with the appropriate items

Elapsed	Time	Activity
0:00	0:05	Objectives
0:05	0:15	Overview
0:20	0:45	In Class Activity I
1:05	0:10	BREAK
1:15	0:45	In Class Activity II
TOTAL	2:00

Learning Objectives (5 min)

NOTE: Fill in with the appropriate items

By this end of this lesson, students should be able to...

1. Practice more advanced techniques with lists and arrays
2. Implement various list manipulation methods such as insert and replace

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)