Assignment 5. Linked Lists

Due Wednesday, August 9 at 11:59 pm Pacific

  • Submissions received by due date receive a small on-time bonus.
  • All students are granted a pre-approved extension or "grace period" of 24 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Thu, Aug 10 at 11:59 pm Pacific, after which we will deduct 15% per late day.
  • You must submit the assignment by Tue, Aug 15 at 11:59 pm Pacific to receive any credit. We will not accept any submissions past this date.
  • In this course, we express all date/times in Pacific time GMT -7. Our Paperless submission system also displays/records due dates and submission times in Pacific time.

Last week, you gained experience working with pointers in the context of arrays and dynamic memory allocation. This week, you will further strengthen your pointer skills by manipulating linked lists. The pointer-based linked structures are a fundamentally different way of representing sequences than the array-based approaches you worked with in the previous assignment, and this assignment aims to build your familiarity with the joys, trials, and tribulations of working with linked lists. Along the way, you'll also deepen your understanding of some different real-world sorting algorithms.

This assignment is to be completed individually. Working in pairs/groups is not permitted.

Learning goals

  • Students will continue to build and improve their skills of working with pointers.
  • Students will be able to use their knowledge of pointers to traverse and investigate linked data structures in the debugger.
  • Students will understand the fundamental differences between storing data in contiguous memory locations as compared to organizing data pointer links.
  • Students will gain practice with different "idioms" of linked list usage.
  • Students will understand the difference in approach of several real-world sorting algorithms and resulting performance tradeoffs.

Assignment parts

This assignment consists of a warmup debugging exercise and two programming tasks.

  • Memory Debugging Warmup

    A collection of tools and strategies to prep you for working with linked lists.

  • The Labyrinth

    Make your way out of a maze using only pointers and linked lists.

  • Sorting Linked Lists

    A classic programming task: reordering the nodes of a linked list into sorted order.

Getting started

We provide a ZIP of the starter project. Download the zip, extract the files, and double-click the .pro file to open the project in Qt Creator.

📦 Starter code

Resources

Here are resources that will be helpful for this assignment:

Submission instructions

Before you call it done, run through our submit checklist to be sure all your ts are crossed and is are dotted. Make sure your code follows our style guide. Then upload your completed files to Paperless for grading.

Please submit only the files you edited; for this assignment, these files will be:

  • labyrinth.cpp
  • escape.cpp
  • sorting.cpp
  • short_answer.txt

You don't need to submit any of the other files in the project folder.

🏁 Submit to Paperless

If you modified any other files that you modified in the course of coding up your solutions, submit those as well. And that’s it! You’re done!

Good luck, and have fun!