Due Wednesday, November 17 at 11:59 pm
- Submissions received by the due date receive a small on-time bonus.
- All students are granted a pre-approved extension or "grace period" of 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
- The grace period expires Fri, Nov 19 at 11:59 pm, after which we cannot accept further late submissions.
- All due dates and submission times are expressed in Pacific time.
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 we've seen so far, 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 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.
- 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 build an understanding of real-world sorting algorithms and the performance tradeoffs of sorting data represented in different underlying formats.
This assignment consists of two short debugging/warmup exercises (
labryinth.cpp) and a substantive programming task on linked lists (
A collection of tools and strategies to prep you for working with linked lists.
A hybrid coding/debugging exercise where you’ll trace through pointers in the debugger to escape from a labyrinth.
A classic programming task: reordering the nodes of a linked list into sorted order.
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.
The source files you will edit are
Additionally, you will answer questions in
Here are resources that will be helpful for this assignment:
- 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.
- Lectures: Sorting algorithms, Memory, pointers, LinkNode, Linked Lists, Linked List operations
- Section exercises: Section 6 and Section 7
- Textbook Chapter 10 Sorting, Chapter 11 Pointers and Arrays, Chapter 12 Dynamic Memory Management
Working very closely with raw memory, pointers, and linked data structures will be challenging. We recommend drawing lots of diagrams and making good use of the debugger.
Look for an announcement on the Ed forum for the YEAH session for this assignment. As always, we're here to help you if you get stuck. The Ed forum is open 24/7 for general discussion. Always start by searching first to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the LaIR helper hours or office hours.
Before you call it done, run through our submit checklist to be sure all your
ts are crossed and
is dotted. Then upload your completed files to Paperless for grading.
Please submit only the files you edited; for this assignment, these files will be