Reed CSCI 221 Fall 2020

Homework 05: linked lists

Due October 8th at 4pm.

• from Git classroom link
• as ZIP file

This assignment has two parts. Each ask you to mimic our llist library code from lecture. You’ll invent a linked list implementation of an ordered dictionary data structure and also a linked list implementation of a queue data structure.

This folder contains the linked list library as the source files llist.hh and llist.cc, along with the sample client test_llist.cc. There is also a Makefile and the starting code for the second part of the assignment. Once you’ve completed the assignment you will have edited or created 6 files that you’ll need to submit, namely

order.cc order.hh test_order.cc (Part 1)
queue.cc queue.hh test_queue.cc (Part 2)

Please work to mimic the coding style guidelines and formatting I’ve suggested so far. Include comments that describe the code, when appropriate. Include some comments at the top of your source code, including your name and other brief info describing the program. There should also be a brief comment that precedes each struct, function, and procedure definition you write. Mimic the work I’ve done in the llist files.

You should work to complete each of these exercises so that they compile and run correctly. Should you face problems in solving an exercise, you can still submit broken code. In your top comment in that file PLEASE let us know in what way the code is broken (why it doesn’t compile, or what tests failed, etc.). In many cases, we are willing to give partial credit if you identify problems in the code.

Part 1: write ordered

For this exercise, you’re going to invent a different linked list data structure that holds a sequence of key-value pairs, sorted by the key. This is called an ordered dictionary data structure. We’ll make the keys of type std::string and we’ll have each key’s associated value be of type int. The resulting code will mimic many aspects of Python’s dict type, except entries won’t be removed, and missing entries will have a default associated value of 0.

The best way to develop this code is to make a copy of the llist source files with the commands:

cp llist.cc ordered.cc
cp llist.hh ordered.hh
cp test_llist.cc test_ordered.cc

In these you’ll create a new namespace called ordered and invent a new struct type called dict, rather than node and llist. The test client program for ordered should have a main that uses of a value of type ordered::dict*. We’ll use entry as the type name for its linked list nodes, rather than the type name node. The code in ordered.cc will use pointers of type entry* rather than node*.

In ordered.hh define a struct entry that contains three components:

• key: a std::string value stored for a dictionary entry,
• value: an int stored for each entry, associated with its key string, and
• next: a struct entry* pointer to the next entry in the dictionary.

Also in ordered.hh define a dict struct that contains two components:

• first: an entry* that points to the first entry in the dictionary, or is nullptr, and
• defaultValue: an int that represents the associated values of keys that don’t yet have an entry.

You are to define these functions in ordered.cc:

• dict* build(int v): returns a pointer to an empty dictionary. Missing entries have a default associated value of v. • int get(dict* D, std::string k): returns the value associated with the entry with key k, or the default value if that key has no entry yet in D.
• void set(dict* D, std::string k, int v): updates D so that value v is associated with key k. This could either add an entry into the linked list if k doesn’t yet have one, or update an existing entry if k has one. • std::string toString(dict* D): give back a Python representation of the dictionary’s existing entries, and in increasing alphabetical order by their keys.

For all of these functions, the linked list that you maintain should be in alphabetical order of the entry’s keys. This means that your set operation will have to find the place where it needs to place an entry, when it discovers that the entry k doesn’t yet exist. This also means that your code for get can exit the traversal loop early. It won’t need to traverse all the nodes to discover that a key has no entry.

You’ll want to modify the testing code’s main so that it tests the set and get operations. It should start by building an empty order::dict*, accept a series of those commands to modify that ordered dictionary, and it should output the order::toString of the dictionary that results from each change. Include help and quit commands, too.

Note that you can get rid of the main code that processes argc and argv, instead having it declared as type int main(void). You’ll want to keep the parseCommand code to figure out the user’s inputs for the commands get <key> and set <key> <value>.

Here is a transcription of the test_ordered code working:

$ ./test_ordered
Your dictionary is {}.
Enter a dictionary command: get bob
That key has value 0.
Your dictionary is {}.
Enter a dictionary command: set bob 42
Your dictionary is {'bob': 42}.
Enter a dictionary command: get bob
That key has value 42.
Your dictionary is {'bob': 42}.
Enter a dictionary command: set alice 101
Your dictionary is {'alice': 101, 'bob': 42}.
Enter a dictionary command: set carlos -6
Your dictionary is {'alice': 101, 'bob': 42, 'carlos': -6}.
Enter a dictionary command: set bob 1234
Your dictionary is {'alice': 101, 'bob': 1234, 'carlos': -6}.
Enter a dictionary command: get carlos
That key has value -6.
Your dictionary is {'alice': 101, 'bob': 1234, 'carlos': -6}.
Enter a dictionary command: quit
Bye!
$

Note that main creates a dictionary whose default value is 0.

You do not need to write the code for a destroy function. This function, like llist::destroy, would release all its nodes’ storage back to the heap. You are welcome to write this as a BONUS exercise.

RECOMMENDATION: I recommend getting this code working first without it putting the keys in sorted order. Once you’ve got it working in that way, change set so that it inserts the keys in the right order. There are several cases you’ll need to consider in that code to get it to work correctly. It’s tricky.

Part 2: write queue

A queue is a container data structure that holds a set of items, and keeps track of the order that they were added to the queue. The item at the front, called the head of the queue, was the item that was first added. The item at the end is the item that was last added. The items in between are ordered from the earliest added after the head, to the latest added, working from front to back. The operation for adding an item to the back of the queue is normally called enqueue.

An item can be removed from the queue using the operation called dequeue. With queues, however, you can’t just remove any of the items it stores. Rather, instead, the next item removed with a dequeue is the one at the front of the queue, the head item. It gets removed from the front, and so the next item in line becomes the new head, unless of course that dequeued item was the only item in the queue.

We’ll see how queues are used in search and graph algorithms later, but for now we simply want to practice writing more linked list code. This exercise asks you to complete the code in queue.cc for a linked list data structure queue::queue defined in queue.hh and tested in test_queue.cc. Once all your code is working, this is the kind of interaction I’d expect:

$ ./test_queue
Your queue contains []
Enter a command: head
Your queue is empty and has no head.
Your queue contains []
Enter a command: enqueue 1
Your queue contains [(1)]
Enter a command: enqueue 2
Your queue contains [(1) 2]
Enter a command: enqueue 3
Your queue contains [(1) 2 3]
Enter a command: head
1 is at the head of your queue.
Enter a command: dequeue
1 was removed from the head of your queue.
Your queue contains [(2) 3]
Bye!
$

The code currently compiles and runs, but several of the queue functions aren’t properly written. Finish the code in queue.cc. These two are already written:

• build: constructs, initializes, and returns an empty queue.
• isEmpty: returns whether or not the queue is empty.

The others, listed just below, need to be written by you.

To implement a queue as a linked list, we use two node pointers first and last, so each is of type node*. An empty queue has both of these attributes set to nullptr. A queue with only one item has first and last pointing to the same node struct. A queue with more items has first pointing to the head item’s node, that node points to the next item in line, and so on, and the queue has last pointing to the node whose next attribute is a nullptr.

Here are the other operations you need to complete:

• enqueue: taked an integer and places it, in a new linked list node, at the end of the queue. When the queue isn’t empty, you can use last to append to the end.

• dequeue: this should remove and return the value stored at the front node of the queue. NOTE: you should also deallocate its linked list node removed by calling delete on its pointer. ALSO NOTE: you should make sure that both first and last are made null should this removed head be the only item that was in the queue.

• head: this should return the value stored at the front node of the queue.

• toString: this should create and return a string that represents the contents of the queue. Mimic the sample output above.

• destroy: this should dequeue each item in the queue. Because you delete within dequeue, this gives back each node’s storage to the heap. It should then delete the pointer of the queue itself.