Comp 11

Linked Structures

Review

Linked Structures

Allow us to represent relationships. Think LinkedIn, Facebook friends, family trees, etc.

Solving an immediate problem

Linked lists

Start from the client's view (as if they were built in). After we know how to use them, we'll see how to implement them.

A linked list of some data type is an ordered collection of data elements. A list is either
Abstractly, we can have a list of 0 integers, 1 integer value, 200,000 integer values. Similarly, we could have a list of strings or snakes or fish or any other data type.

Above definition is recursive, i.e., it refers to itself!

Metaphors:

Exercise:
You and a group of friends pretend you're tow trucks, get a balloon. One friend is just a hook (they hold on to the beginning of a list). Build:

Devise an algorithm for searching the list. First search for 2. Then search for 42.

Be careful: Tow trucks have minds of their own, and if they aren't hooked up to something, they just drive away in search of adventure.

Box and pointer diagrams

Because we don't always have friends around.

We can represent the empty list as ∅

A variable that holds a non-empty list would be drawn like this:

A C++ StringList Interface

A new game:
We're going to approach this new data structure a little differently. For dynamic arrays, we showed you how to make one, and then how to use it. For linked lists, we're going to work the other way.

This time, we'll say “What if we had something that behaves in such-and-such a way? What could we do with it? How would we use it?”

Below is a simple string list API (application programming interface) consisting of a new type, called StringList (whose precise definition is left abstract), and a set of six functions client code can use to make an manipulate lists. There is also some documentation in this file.

StringList.h:

When programming a real project (and your own programming projects would certainly qualify), it is common to break the problem up into pieces (Big Idea #3) that represent reusable functionality (Big Idea #2). For example, an application that needed to represent lists of strings (maybe it's a math game) could benefit from a general string list package that could be used throughout the application and in other applications, too. To accomplish this, we design an abstraction (Big Idea #1) that has an interface all client code can use.

We want the interface to be reasonably general to foster reuse, so it doesn't contain anything specific to a particular application, for example, the game probably has a GUI, but the list code doesn't know anything about that.

An abstraction that represents a data structure and its operations is called a data abstraction. That is, a data abstraction consists of one or more abstract types and a set of operations (functions) on values of the abstract type(s).

An StringList Client

In the real world, picking up existing code and figuring out how to use it based on its API is a common activity: it's much more common than programming everything yourself — in fact, you almost never write a whole application from scratch. Also, when designing an abstraction, it's usually a good idea to think through and sketch some simple use cases.

What kinds of things can we do with a list? What have you done with sequences of values before?

Let's start with reading in a list, printing a list, and summing up the members of a list. To build a list, you start with an empty list, and then you prepend things onto it: 

StringListNode *family = empty();

numbers = prepend("ma", numbers);
numbers = prepend("pa", numbers);
Results in: 
+------+--+     +------+--+
| "pa" | .+---->| "ma" | .+---->@
+------+- +     +------+- +

Notice that you build a list up back to front, because whenever you add a new element, it goes on the front.

Reading a list of arbitrary length is extremely easy! Suppose we want to read a list of strings from the keyboard: 

string          name;
StringListNode *nameList = empty();

for (cin >> name; !cin.eof(); cin >> name)
        ageList = prepend(name, nameList);

How would you write a readFile function that takes a string giving the file name and returns a list of the string values in the file (assume the file only contains strings)?

Print the list. Sum the elements of the list. Copy a list. Produce a list of strings from a to b.

Here is a client of string lists that one might make to test your list functions. The idea would be that for each list function you add, you could add a command to your interactive test loop to run that function.

StringListExample1.cpp:

Exercises:
For these tasks, you are writing client code. You will not manipulate any pointers or structs directly. Notice the interface deals only with strings and string lists.

For each problem, begin by writing a stub, that is, write a function definition whose body is the most trivial thing possible. If you were writing code, you could compile and even begin some testing just using the stub. It's also good practice for exams (on an exam, you wouldn't write the stub, but you should be very fast at getting the function header right).

  1. Using the above interface, write a function that takes an StringList and prints its elements.

    Write it with a loop. But then try to see if you can think of a way to to do it without a loop.

    List reducers:

  2. Write a function called concatList() that takes an string list as a parameter and returns the concatenation of the elements in the list. Use recursion.
  3. [For IntLists] Write a function called sumList() that takes an integer list as a parameter and returns the sum of the elements in the list. Use recursion.
  4. Write a function called length() that takes an string list and returns the number of (non-empty) elements in the list. Use recursion.

    List transducers:

  5. Write a function called copy() that takes an string list and returns a new string list that is a copy of the input list.
  6. Write a function called mapPluralize() that takes an input list and returns a new string list each of whose elements is the correpsonding element of the input list with the letter 's' attached to the end. Use recursion.
  7. [For IntLists] Write a function called mapIncrement() -- that takes input list and returns a new string list -- each of whose elements is the corresponding element of the -- input list plus one. Use recursion. --
  8. Write a function called mapSuffix() that takes an input list and a string suffix and returns a new string list each of whose elements is the corresponding element of the input list with the given suffix attached. Use recursion.
  9. [For IntLists] Write a function called mapIncrementBy() -- that takes input list and an integer increment vale -- returns a new integer list each of whose elements is the -- corresponding element of the input list plus the given -- increment value. Use recursion. --
  10. Write a function called pairwiseConcat() that takes two string lists and returns a new string list each of whose elements is the concatenation of the corresponding elements of the list parameters. If the two input lists are not the same length, treat the shorter list as if it were padded out with empty strings to be the same length as the longer list. (You do not need to modify the list to do this.) Use recursion.

    List filter:

  11. Write a function called filterInitial() that takes a string list and a character and returns a new string list containing only the strings that start with the give letter. Use recursion.
  12. [For IntLists] Write a function called filterPositive() that takes an integer list and returns a new integer list whose elements are the positive elements of the input list. That is, the output list is a copy of the input list with negative and zero elements removed. Use recursion.

    List generator:

  13. [For IntLists] Write a function called range() that takes two integers, low and high and returns a list of the integers in the interval [low … high) (the list includes low but not high). If low ≥ high, the resulting list should be empty. Use recursion.
Here are some solutions for your reference: StringListUtils.cpp.

Act these out. Some people represent list nodes, others represent activation records. Activation records track their variables and where they are in the function at any given time. List nodes track their data value(s) and next pointers.

A StringList Implementation

StringList.cpp:

Another List Implementation

An enormous benefit of good data abstractions is that the implementer is free to change the impelmentation as long as they continue to support the published interface. It is therefore possible to have multiple implementations of a data abstraction, each optimized for different situations (such as making certain operations faster at the expense of others for certain applications). Client code can use any faithful implementation without any change whatsoever.

Here is an implementation of integer lists that does not use NULL to represent the empty list.

IntList2.cpp:

A StringList Implementation

There is a saying in computing that every interesting program contains at least one list structure. Lists are very common, and we've seen one way of implementing them — there are others, and Comp 15 uses a more traditionally imperative/object-oriented approach.

Because they are so common, C++ has a list implementation as part of its Standard Template Library. This implementation works for any type of data. To get a sense of how this might be possible, consider the StringList module shown below. Can you see how similar it is to the StringList module? Could you write a program that takes the name of a type, say T and outputs a correct TList.h and TList.cpp?

StringList.h:

StringList.cpp:

Mark A. Sheldon (msheldon@cs.tufts.edu)
Last Modified 2021-Jan-08