Assign5: Linked Lists

Due Tuesday, August 04 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 Wednesday end of the day PDT, with no penalty.
• The grace period expires at the end of the day Wednesday, 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, 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 manipulating 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. 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 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.
• Students will understand the different paradigms that define various real-world sorting algorithms.

Assignment parts

This assignment consists of two debugging/warmup exercises (warmup.cpp and labryinth.cpp) and one programming task (sorting.cpp). To give you a sense of time allocation, completing the sorting portion of the assignment took the instructors about 3.5 times longer than the labyrinth exercise.

• Pointers/Linked Lists 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: implement two well-known recursive sorting algorithms 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

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

Additionally, you will answer questions in short_answer.txt.

Before getting started writing code, we highly recommend reading the CS106B Style Guide. All of your assignment submissions this quarter will be graded on their coding style, and this guide contains the coding standards that make up our style rubric.

Helpful Resources

Here are some resources that you might find helpful for this assignment:

• Trip's Assignment 5 YEAH Slides
• 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
• Lecture Slides: Thursday Intro to Linked Lists, Monday Linked List Operations, Tuesday Sorting, Wednesday Testing with Linked Lists
• Section: Dynamic Memory and Pointers, Linked Lists and Sorting
• Textbook 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 contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for code debugging questions – however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. 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 submission checklist to be sure all your ts are crossed and is dotted. Then 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
• sorting.cpp
• short_answer.txt

🏁 Submit to Paperless

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