Assign6: Linked Lists

Due Friday, May 29 at 11:59 pm

• The assignment deadline is by the end of the day, Anywhere on Earth.
• Submit by end of day Friday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Wednesday end of day AoE, with no penalty.
• The grace period expires end of day Wednesday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in PDT frame of reference.

The grace period for Assignment 6 has been extended to end of day Wednesday.

Last week, we gained a lot of practice working with pointers in the context of arrays and dynamic memory allocation. This week, we are going to continue bolstering our pointer skills by working on some tasks centered around manipulation linked structures. Linked structures are a fundamentally different way of representing sequences than the array-based approaches you worked with in the last assignment, and this assignment aims to build your familiarity with the joys, trials, and tribulations of working with linked structures. By completing the following tasks you will become a master of pointers and linked structures, to the point where you'll finally be able to proclaim with confidence, Thank U->Next!

Learning goals

• Students will continue to build and improve their skills of working with pointers.
• Students will understand the fundamental difference between storing information in a contiguous array as compared to storing data in a linked data structure.
• Students will gain practice with different "idioms" of linked list usage, including pointer rewiring and insertion/removal of nodes from linked lists.

Assignment parts

This assignment consists of two debugging/warmup exercises and one programming task.

• Labyrinth

  A hybrid coding/debugging exercise where you’ll trace through pointers in the debugger to escape from a labyrinth.

• List warmups

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

• Linked list sort

  A classic programming task: implement a well-known recursive sorting algorithm on a linked list.

Getting started

We provide a ZIP of the starter project. Download the zip, extract the files, and open the project in Qt creator.

📦 Starter code

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

Getting help

Here are some resources that you might find helpful while working on the assignment:

• You can find the slides from the Assignment 6 YEAH session here and the recording of the session has been posted on Canvas. We highly recommend starting with these resources as you get started on the assignment.
• We will be hosting two collaborative group work sessions for Assignment 6. The sessions are open to anyone and will be focused on providing a collaborative group work environment where students can work together and collaborate on the assignment at a high level, while a section leader will be around to answer any conceptual questions regarding how to get started on the assignment. Zoom information for both sessions can be found on the Zoom details page.
  • The first session will be on Sunday, May 24 from 7:30-8:30pm PDT.
  • The second session will be on Tuesday, May 26 from 5:00-6:00pm PDT.
• Lecture Slides: Friday Sorting, Monday Linked Lists, Wednesday More Lists
• Section: Linked Lists
• Textbook Chapter 12 Dynamic memory, linked lists
• We’re here to help you get there! Contact us on Ed discussion, email your section leader, or come join non-stop coding party that is the LaiR.

Submit

Review our submission checklist before calling it done. Upload your completed files for grading to the Paperless website.

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

• labyrinth.cpp
• lists.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: When submitting to Paperless, due dates are expressed in PDT.