Linked Lists

Linked structures are a fundamentally different way of encoding sequences than the array-based approaches you worked with on Assignment 5. This assignment is all about manipulating, traversing, and exploring linked structures. It’s a three-parter. The first part is a hybrid coding/debugging exercise where you’ll work the debugger to escape from a maze. The second part is a warm-up exercise intended to get you playing around with doubly-linked lists. The third part is a coding exercise in which you’ll use linked lists to build a system that can be used to make nifty 2D graphics.

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

Assignment parts

This assignment consists of a warmup debugging exercises and three programming tasks.

• The Labyrinth

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

• Doubly Linked List Warmup

  Practice with doubly-linked lists (where each cell has a prev and next), which come into play in the Particle System.

• Particle System

  Create stunning animations by leveraging your class, pointer, and linked list knowledge!

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

Getting Help

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

• The CS106B Guide to Testing
• The CS106B Style Guide
• Resolving Common Build/Run Errors, compiled by section leader Jillian Tang.
• Prerecorded YEAH Hours
• Section: see Section 6 and Section 7 for some linked lists problems!

Submission instructions

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:

• Labyrinth.cpp.
• LabyrinthEscape.cpp.
• DoublyLinkedLists.cpp.
• ParticleSystem.h and ParticleSystem.cpp. (Don’t forget the header file!)

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

If you completed an extension, make sure to also submit the relevant files to Paperless as well!

🏁 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!