Linked and Doubly Linked Lists

Investigate List-Based Abstract Data Types
Published

March 10, 2025

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! How would you measure this structure’s performance?

Activities

  • Tuesday and Thursday: 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
  • Friday: Submit algorithm engineering project four and start algorithm engineering project five and review for the algorithm engineering skill-check next week

Project

Goal

To build and use a Python program, called listmutator, that runs benchmarks to study the performance of combining data into different types of lists

Steps

  • Click the link provided in Discord to get started on this project
  • Use List Mutation as your template repository
  • Install the project’s dependencies using devenv and/or poetry
  • Follow the instructions to complete the project:
    • Week 1: Implement all of the modules in listmutator
    • Week 2: Design and conduct experiments and document experimental results
  • Schedule office hours if you have questions
Student Insights

Students who completed this project shared these insights:

  • “Python allows for an easy way to create complex data structures through a user-friendly syntax. Because of Python’s subtle overhead when calling multiple functions in a sequence, this overhead is greatly magnified when scaled on the order of 10e6 items or more. That said, using Python to perform doubling experiments is a quick way to quickly evaluate the effectiveness of data structures and algorithms.” Simon Jones

  • “Implementing a robust benchmarking methodology can be challenging. You have to define the experimental setup, conduct multiple runs to account for variability, and analyze the results statistically to draw meaningful conclusions.” Vital Joseph

Slides

Full Screen: Week Nine: Implementing List-Based Structures

Back to top