CSC161 2011S Imperative Problem Solving

Laboratory: Linked Structures


Prerequisites: Familiarity with pointers, linked lists, malloc, and more. The array structures lab.


a. Make sure that you have the diretory for the previous lab. I had suggested something like CSC161/Labs/Linear.

b. To that direcectory, add linked-stack.c and linked-queue.c.

c. To that directory, add the updated Makefile.

c. To that directory, add an updated copy of linear-expt.c.

d. Review linear-expt.c to ensure that you have a sense as to what the output should be for stacks and queues. (You might find it useful to write down a summary of the expected output.)


Exercise 1: Linked Stacks

a. Read through the code of linked-stack.c to ensure that you understand the parts. Make note of any potential problems or errors you observe.

b. Make and run linked-stack-expt.

c. As you may have noted, while linked-stack-expt gives the correct stack output, suggesting that linked-stack.c is correct, there does seem to be a memory leak in the program. Repair that leak. You will want to pay particular attention to destruct, get, and clear.

Exercise 2: Linked Queues

a. Read through the code of linked-queue.c to ensure that you understand the parts. Make note of any potential problems or errors you observe.

b. Make and run linked-queue-expt.

c. You are likely to observe the experiment segfault. Why? Because add is not defined. Define it.

d. You may also encounter another error because there is a small bug in get having to deal with deleting the last element of a list. Fix that bug.

e. Check for memory leaks.

For Those with Extra Time



Wednesday, 4 May 2011 [Samuel A. Rebelsky]

  • Created the template code, the header, and the experiments (for the previous lab).

Thursday, 5 May 2011 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Thu May 5 23:49:35 2011.
The source to the document was last modified on Thu May 5 23:49:34 2011.
This document may be found at
A PDF version of this document may be found at

Samuel A. Rebelsky,

Copyright © 2010 Samuel A. Rebelsky. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.