Listy Strings

In this part of the assignment, you will write a small suite of functions that use linked lists to store and manipulate strings. In doing so, you will master the craft of linked list manipulation!

You are welcome to use any code you find in the course lecture notes and section problems as you work on this assignment, as long as you leave a comment saying where that code came from. However, you will likely find the linked list functions you have to write more approachable if you have sat down to replicate the code from class yourself and developed a deep understanding of how it works.

While incorporating code from our class into your project is acceptable, you of course should not incorporate or refer to code from other sources.

Linked List Strings and the ListyNode Struct

In this part of the assignment, we will create and manipulate linked list representations of strings. Each node in one of these so-called "listy strings" will contain a single character, and a listy string will have exactly as many nodes as there are characters in the string it represents. We will know that we have reached the end of a listy string when we encounter a nullptr.

For example, the word "dwindle" can be represented using a linked list as follows:

Note that the next pointer for the final node (the node containing 'e') is set to nullptr.

We have created a ListyNode struct that you will use for your listy strings. It is defined in listynode.h and can be used in any code you write in listystrings.cpp:

struct ListyNode {
    char data;          /* Data stored in the node. */
    ListyNode *next;    /* Pointer to next node in the list. */
}

You also have access to a variety of constructors you can use when creating a new ListyNode (which you can read about in listynode.h), but the one we think is the easiest to use is the following:

// This version of the constructor initializes the data field to
// the specified value and the pointer field to nullptr.
//
// Example usage:  ListyNode *node = new ListyNode('q');

ListyNode(char data) {
    this->data = data;
    this->next = nullptr;
}

Advice

Here's some advice that we hope will help as you dig into this assignment:

• Be sure you have completed both warmup exercises before starting on these linked list functions. If you ran into any trouble on the warmups, get those confusions resolved first. You want to have top-notch skills for using the debugger to examine linked structures and be well-versed in what to expect from memory errors and how to diagnose them.

• Correct use of memory and pointers requires careful attention to detail. You'll likely benefit from drawing a lot of diagrams to help you keep track.

• If you have a test case that is crashing, remember that you can run your program in the debugger to find the exact line where that crash is happening. From there, use the debugging and sleuthing skills you've developed this quarter to figure out where things are going awry.

• To be sure your code is doing what you intend, you'll likely spend a lot of time stepping in the debugger and examining the state of your lists as you go. In fact, you might find it convenient to run in the debugger full time as you work on this project, as this gives you effective tools for analyzing what is going on in your program at any given moment. Alternatively, strategic use of cout statements can also be used to force your program to tell you exactly what it's doing in a complicated function and can serve as a powerful debugging tool that dumps a lot of useful data to the screen at once.

• If you draw out an intentional design for each function from the start and follow a systematic development process, you can absolutely triumph. On the other hand, attempting to pound out a solution on the keyboard before fully understanding your strategy and then hoping you can prod the code into working is likely to lead to headache and heartache.

• We have additional notes about testing and common questions at the bottom of this page that you might want to refer to before you start coding.

Required Functions (Part 1: Utilities)

Implement all of the following functions in listystrings.cpp. For additional examples of how these functions will be called and their expected behaviors, see the test cases in listystrings.cpp

• string listToString(ListyNode *head)

  • Description: This function takes the head of a linked list and returns the string represented by that list. If head is nullptr, simply return an empty string. For example, if the head of the linked list at the top of this page were passed to this function, it should return the string "dwindle". Be sure not to modify the linked list passed to this function in any way.

  • Runtime Requirement: This should be an O(n) function, where n is the length of the given linked list. For the purposes of this function, you may assume that concatenating a single character to a string is an O(1) operation.

• ListyNode *stringToList(string str)

  • Description: Create a linked list representation of the string passed to this function, and return the head of that linked list. The nodes in your linked list must be dynamically allocated. For example, if "dwindle" were passed to this function, it should return the head of the linked list depicted at the top of this page. If str is an empty string, simply return nullptr from this function without allocating any nodes.

  • Special Considerations: As you create your linked list, be sure to avoid creating orphaned nodes that are detached from the list. You do not need to delete the nodes that you create in this function (that's handled in the test cases, many of which will call your destroyList() function (described below) directly in order to delete all the nodes in your linked list), but you do need to ensure that all the nodes you create with this function are reachable from the head of the list that you return. Note that ListyNode allocations are being tracked, so our testing infrastructure will flag test cases with memory leaks.

  • Runtime Requirement: This should be an O(n) function, where n is the length of the given string (str). Note that as you loop through str to add characters to your linked list, if your strategy for each character is to always loop from the head of the list to the tail, over and over again, your runtime will devolve into O(n²).

  • Other Considerations: If you run into bugs while working on this function, remember your debugger training! You can use the debugger to step through your function, inspect any pointer variables, and draw diagrams of what's happening in memory. Alternatively, you might find it helpful to pepper your code with cout statements that print helpful messages telling you what your program is doing, step by step. Finally, consider writing a void printList(ListyNode *head) function that loops through any linked lists you create and prints them to the screen. While printList() is not a formal requirement for this assignment, having that function might come in handy for debugging.

• void destroyList(ListyNode*& head)

  • Description: Delete all the nodes in this linked list, and set the pass-by-reference head parameter to nullptr. Be sure to avoid segmentation faults and other memory errors. Remember, once you delete a node, you should not try to access any of the fields inside that node.

  • Special Considerations: Be sure to avoid segmentation faults in the case where head is nullptr. In that case, simply return from this function straight away.

  • Memory Leaks: Once you have this function implemented correctly, you should start passing all the destroyList() test cases we have provided. If you have already completed listToString() and stringToList(), implementing destroyList() correctly should cause our test infrastructure to stop flagging memory leaks for those functions, as well. If SimpleTest is still flagging memory leaks in the provided test cases for any of these three functions, that means at least one of them has not been implemented correctly.

Interlude: Recursion vs. Iteration

You might ask: should I use iteration or recursion to implement my linked list functions? For certain tasks, one approach may be tidier, but in many cases either can work well. However, recursively processing a linked list has a significant drawback: the cost of a stack frame for every node in the list adds a heavy performance cost and limits the total length of list that can be processed.

Because we want our functions to be able to scale up to very long lists, you must use iterative approaches throughout this assignment, not recursive.

Interlude: Runtime Analysis

Once you have listToString() and stringToList() implemented, examine the output of our two provided tests that are labeled [Timing Test] to determine whether the runtimes for your implementations are linear, quadratic, or something else. If the provided tests are taking too long to run, or if those tests run too quickly on your system to provide any meaningful runtime data, add your own STUDENT_TESTs that mirror our PROVIDED_TESTs, but with different string lengths.

Required Functions (Part 2: String Modifications)

Next, implement the following four functions in listystrings.cpp. These functions take existing listy strings like the ones you created in Part 1 and perform various modifications to them. For additional examples of how these functions will be called and their expected behaviors, see the test cases in listystrings.cpp.

• void appendString(ListyNode*& head, string str)

  • Description: Append the linked list representation of the given string (str) to the tail of the linked list passed to this function. If the string is empty, this function call should be a no-op. If the list is empty but the string is not, then the pass-by-reference head parameter should be set to the head of a linked list representation of the given string. If the list passed to this function is non-empty, you must not modify head. Do not delete any nodes from the linked list passed to this function, and do not edit the characters in any of those pre-existing nodes.

  • Runtime Requirement: This should be an O(m+n) function, where m is the length of the original list and n is the length of the given string. As with stringToList(), if you loop through the entire list for each new character you add to the end of this string, your runtime will become quadratic.

• void prependString(ListyNode*& head, string str)

  • Description: Prepend the linked list representation of the given string (str) to the front of the linked list passed to this function, updating the pass-by-reference head pointer as appropriate. If the string is empty, this function call should be a no-op. If the list is empty but the string is not, then the pass-by-reference head parameter should be set to the head of a linked list representation of the given string. Do not delete any nodes from the linked list passed to this function, and do not edit the characters in any of those pre-existing nodes.

  • Runtime Requirement: This should be an O(m+n) function, where m is the length of the original list and n is the length of the given string. As with stringToList(), if you loop through the entire list for each new character you add to the end of this string, your runtime will become quadratic.

• void removeChar(ListyNode*& head, char ch)

  • Description: This function takes the head of a linked list and removes any node that contains the given char (ch). If ch does not occur anywhere in the given listy string, the linked list should not be modified. The pass-by-reference head parameter should only be modified if this function needs to remove the head of the linked list (i.e., if the head of the linked list contains the character ch), in which case the function should update the head as appropriate. Do not delete any nodes unless they contain ch, and do not edit the characters in any existing nodes.

  • Special Considerations (Memory): Throughout this function, be sure to avoid memory leaks: if you are excising any nodes from this list, be sure to delete them before returning from this function. Our provided tests for this function attempt to delete all the remaining nodes in your list after calling removeChar() (either by deleting remaining nodes manually or by calling destroyList()), so if this function introduces memory leaks, they will be flagged by our test infrastructure. Furthermore, once removeChar() and destroyList() are implemented correctly, all our provided tests cases for this function should pass without any memory leaks. As always, be sure to avoid segmentation faults and other memory errors when writing this function. Be ever vigilant against dereferencing null pointers!

• void replaceChar(ListyNode*& head, char ch, string str)

  • Preliminary Note: This might be the most challenging function in the assignment. Don't be alarmed if this one takes you a while. If you feel like you're spinning your wheels on this one, you might want to move on to other parts of the assignment and come back to this one later.

  • Description: This function takes the head of a linked list (head) and replaces all occurrences of ch contained in that list with the linked list representation of the given string (str). For example, if we call this function with the linked list [s]->[p]->[i]->[n], the character 'i', and the string "oo", the single occurrence of 'i' in our list will be replaced with the nodes [o]->[o], and the resulting linked list will be [s]->[p]->[o]->[o]->[n]. If there were multiple 'i' nodes in the list, all of them would be replaced with [o]->[o]. If the linked list is empty (i.e., head is nullptr) a call to this function call should be a no-op. If ch is nowhere in the given list, the list should not be modified in any way. If str is the empty string (i.e., ""), then this function should delete all instances of ch from the given list. We strongly recommend looking over our provided tests for this function in listystrings.cpp to get a solid idea of its expected behaviors before you start coding.

  • Special Considerations (Removing and Modifying Nodes): You may only remove nodes from the given linked list if they contain ch (the character we're replacing with str). You may not delete any other nodes. Furthermore, you should never change the character inside a node unless it contains ch; all other nodes should have their characters unchanged when this function returns.

  • Special Considerations (Memory): The memory considerations for removeChar() apply to this function, as well. Avoid memory leaks, and guard against segmentation faults.

  • Helper Functions: For this function in particular, you might benefit from some carefully crafted helper functions. As you work on this function, keep an eye out for any sub-tasks you're faced with that can be cleanly described with a compact verb phrase. Those might be places where a helper function would come in handy – not only to make your replaceChar() function more readable, but also to help simplify the function conceptually, thereby making it a bit easier to implement. There are many valid ways to decompose this problem. Part of the fun here is deciding which helper functions would be useful to you and then coding them up. (Don't forget to add a few STUDENT_TESTs for any helper functions you create, too!)

Required Functions (Part 3: Explode)

For the next two functions, we need to introduce the concept of a compressed listy string and what it means to explode such a string.

In a compressed listy string, a node that has a numeric character '2' through '9' tells us that we should have that many occurrences of the character immediately before it (rather than just one) if we want to reconstruct the string being represented by our linked list.

For example, consider the following list:

The '2' after the 'f' tells us that the string this list represents should have two consecutive 'f' characters in place of that single 'f'. Similarly, the '2' after the 'e' tells us there should be two 'e' characters there, and the '3' after '!' tells us we should have three '!' characters at the end of the string. The resulting string represented by this linked list is "toffee!!!".

A compressed listy string must meet all of the following conditions. If it does, it is said to be well-formed:

• If the list is non-empty, the first node must contain a non-digit character. (That could be an alphabetic character, a space character, punctuation, or any other sort of character other than a digit.)

• None of the nodes in the list may contain the character '0' or '1'. We only use digit characters to indicate that the previous character in the list needs to occur more than one time. To avoid any ambiguity, '0' and '1' are banned from compressed listy strings.

• No two consecutive nodes in the list may contain digit characters. For example, the following listy string is not well-formed because there are two consecutive nodes (the '2' and '3' nodes) that both contain digits:

• If the list is empty (nullptr), it is considered well-formed.

Note that it's totally fine for two consecutive nodes to have the same non-digit characters. For example, the following listy string is well-formed, even though it contains two consecutive 'n' characters (so, what we glean here is that being well-formed just means that there's nothing invalid about the compression; it doesn't necessarily mean that we have achieved maximum compression):

It's also totally fine to have some character followed by a digit, followed by that same character again, followed by another digit. For example, both of the following are well-formed, and they are both valid ways to represent the string "yes!!!!" (with 4 exclamation points):

If we explode a compressed listy string, that means that we simply modify the linked list so that it no longer contains any digit characters and instead directly represents the intended string. For example, the exploded version of the "tof2e2!3" linked list above would represent the string "toffee!!!" directly, like so:

With those definitions in mind, implement the following functions in listystrings.cpp:

• bool isWellFormed(ListyNode *head)

  • Description: Return true if the list passed to this function is a well-formed compressed listy string according to the definition of "well-formed" given above. Otherwise, return false. Be sure not to modify the linked list passed to this function in any way. For examples of how this function will be called, see our test cases in listystrings.cpp.

  • Special Considerations: Keep in mind that the integer 2 and the character '2' are not the same thing; the ASCII representation for the character '2' is not equal to the integer 2. Keep in mind also that it is impossible to fit two digits into a single char. For example, '10' is not a valid char, and so we don't have to worry about encountering that in any of our nodes.

• int explode(ListyNode *head)

  • Description: If the list passed to this function is not a well-formed compressed listy string, simply return -1 (and be sure not to modify the list in any way). Otherwise, modify the linked list so that it contains the exploded version of the string, and return how many more nodes the resulting list has than the original list (0 if the number of nodes is unchanged). Note that if there are no digit characters in the linked list, it is considered well-formed, but no modifications occur when it is exploded, and so the function should return 0 in that case without having modified the list. The same is true of the empty list (nullptr).

  • Head Node Restriction: Notice that the head of the linked list is passed to this function by value, not by reference. That means that if we try to create a new head node for this list, we have no way of communicating that back to whoever called this function. Accordingly, you cannot deallocate or detach the head node from the list. It must remain intact and continue to serve as the head of the exploded version of this list.

  • Special Considerations (Memory): Other than the restriction above pertaining to the head node, you have considerable leeway in how you implement this function. It is possible to write this function in such a way that you only ever add nodes to the list and never remove, but you are also welcome to detach nodes (other than the head) as you see fit, if you find that easier. If you do so, you should be careful to avoid creating orphaned nodes. If you are excising any nodes from this list, be sure to delete them before returning from this function. Furthermore, if you create any new nodes, be sure they don't become detached from the list and get orphaned before returning from explode(). Any of our provided tests that call explode() will also call destroyList() on your exploded list, so if this function introduces memory leaks, that will be flagged by our test infrastructure. As always, be sure to avoid segmentation faults and other memory errors when writing this function. Be ever vigilant against dereferencing null pointers!

  • Special Considerations (Character Processing): As noted in the isWellFormed() function, keep in mind that the ASCII representation for the character '2' is not equal to the integer 2. To complete this function, you will have to convert digit characters ('2', '3', etc.) to their corresponding integer values (2, 3, and so on). You are welcome to use cctype and/or strlib.h functions to help process those digit characters. Our notes from Lecture 3 (Strings) have more information about those libraries (and character processing in general) that you might find helpful.

Testing

For each function you write, including any helper functions you create beyond the core functions that are required for this assignment, be sure to add targeted student tests that exercise those functions in isolation. Adding those tests allows you to confirm the correctness of your helper functions before moving on, so you can implement the rest of your functions with confidence that they're building on a strong foundation from your helpers.

As always, you should add additional tests for all the required functions, as well. Be on the lookout for edge cases described in this assignment that we haven't included in our provided tests. We want you to thoroughly test the nooks and crannies of your code's possible behaviors. Our test cases for replaceChar() are fairly comprehensive already, but there is certainly room to add more robust testing for the other functions.

The quality and breadth of your test cases will be an important component of the grading for this assignment. We're hoping you are ready to show us how much you have learned from the different testing exercises and provided tests that you've seen on the earlier assignments!

Answers to Common Questions

Answers to common questions about list memory allocation and deallocation:

• Are all of the functions in this assignment responsible for allocation and deallocation of nodes? Not all of them, no. Many of the functions in this assignment neither allocate nor deallocate nodes, but instead receive linked lists of allocated nodes and then process them without any sort of deallocation.

• Which code, then, does allocation and deallocation? Who will call destroyList()? Most deallocation happens in the test cases. Many test cases allocate nodes and create lists, pass the lists as input to your functions, confirm correctness of a return value, and then deallocate the lists. Some test cases call your destroyList() function directly. It's actually possible to complete this assignment correctly without ever calling destroyList() outside of PROVIDED_TESTs and STUDENT_TESTs.

• If SimpleTest is reporting a memory leak with a test case, do we need to fix it? Yes. A test case that allocates memory to be used in testing should properly deallocate that memory at the conclusion of the test case. If it's one of our PROVIDED_TESTs that's leaking, it's likely because one of your destroyer functions isn't fully correct, or because another function is leaking memory as it manipulates existing linked list structures. If one of your STUDENT_TESTs is leaking, you should ensure that it is deallocating any linked lists that are expected to be lingering in memory after it's finished calling all the functions that it's testing directly.