Assign5: Linked Lists

Due Tuesday, August 03 at 11:59 pm

• The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
• Submit by the end of the day Tuesday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Thursday end of the day PDT, with no penalty.
• The grace period expires at the end of the day Thursday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in the PDT frame of reference.

Last week, you gained experience working with pointers in the context of arrays and dynamic memory allocation. This week, you further strengthen your pointer skills by manipulating linked lists. The pointed-based 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 lists. Along the way, you'll also deepen your understanding of some different real-world sorting algorithms. 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!

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 location as compared to organizing data pointer links.
• Students will gain practice with different "idioms" of linked list usage, including pointer rewiring and insertion/removal of nodes from linked lists.
• Students will understand the difference in approach of different real-world sorting algorithms and resulting performance tradeoffs.

Assignment parts

This assignment consists of two short debugging/warmup exercises (warmup.cpp and labryinth.cpp) and a substantive programming task on linked lists (sorting.cpp).

• Memory Debugging Warmup

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

• Labyrinth

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

• 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

The source files you will edit are labyrinth.cpp and sorting.cpp.

Additionally, you will answer questions in short_answer.txt.

Resources

Here are resources that will be helpful for this assignment:

• The Assignment 5 YEAH Session is scheduled for Friday, 7/30 at 11:30am PDT. Zoom information can be found on the Zoom Information page.
• Jin-Hee, Grant, and Lauren's Assignment 5 YEAH Slides
• The CS106B Style Guide
• A Guide to Testing Code in CS106B
• Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
• Stanford Libraries Documentation
• Section: Dynamic Memory and Pointers, Linked Lists and Sorting
• Textbook Chapter 10 Sorting, Chapter 11 Pointers and Arrays, Chapter 12 Dynamic Memory Management

Getting help

Working very closely with raw memory, pointers, and linked data structures is a challenging task! We always recommend drawing lots of diagrams and making use of the debugger whenever possible. As always, we're here to help you if you get stuck. You can reach out with a post on Ed, email your section leader, join in at office hours, or sign up for one-one-one help at the LaIR. For questions specific to your code, coming to Lair is your best bet. If you cannot attend LaIR due to timezone issues, you may post your question on Ed. However, you must use a private post if you are including code so that you are not posting your solutions for the whole class to see.

Submit

Before you call it done, run through our [submit checklist][submit_checklist] to be sure all your t's are crossed and i's dotted. 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
• sorting.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in [Pacific time][PT].