Linked and Doubly Linked Lists

Investigate List-Based Abstract Data Types
Published

March 11, 2024

Exploration

  • Read chapters 7 and 8 in A First Course on Data Structures in Python
  • Try out the implementations of OrderedList in the ds2 package of donsheehy/datastructures. Can you write your own tests cases for these abstract data types? Can you use these abstract data types in your own program?
  • Note that chapter 7 was also the focus of last week
  • Design, implement, and test your own efficient implementation of the Deque using the DoubleLinkedList!

Activities

  • Monday and Wednesday: Linked Lists and Doubly Linked Lists
    • Deepen understanding of an abstract data type (ADT)
    • Understand implementation trade-offs for list-based structures
    • Use asymptotic analysis to characterize performance of an ADT
    • Examine Python source code segments to illustrate key points
  • Thursday: Mid-term executable examination
  • Friday: Algorithm analysis from mid-term examination

Project

Goal

Complete an executable examination for the mid-term assessment that covers the content in Chapters one through five of A First Course on Data Structures in Python. In the algorithm all-hands session following the examination, you will receive an additional assignment that invites you to write a retrospective in which you assess the design, implementation, and performance of one of the Python functions that you implemented as part of the examination.

Slides

Full Screen: Week Nine: Implementing List-Based Structures

Back to top