CS 70

Practice: A List Interface

  • LHS Cow speaking

    You've used list (or sequence) data structures before, right? Think about Python lists or Java ArrayLists.

  • RHS Cow speaking

    To start things off, let's think about the interface for this data structure.

  • LHS Cow speaking

    Let's imagine a STRING-LIST structure, a list that stores strings.

  • RHS Cow speaking

    Incidentally, when we name things USING-FAKED-SMALL-CAPS rather than usingCamelCase, we're thinking about functionality conceptually, rather than at the level of C++ functions.

  • LHS Cow speaking

    And the names we choose may be more verbose to be clear about what's going on (and differ from how we'd say things in idiomatic C++ code).

The interface of a data structure is the set of operations that it supports.

The interface is not concerned with how the data structure actually performs those operations. There may be many different implementations that could support the same interface!

What operations should a STRING-LIST data structure support? Brainstorm as many as you can!

There are many possible operations we could want. Here is a pretty reasonable set of operations that we could require for our STRING-LIST structure.

STRING-LIST Interface

  • RHS Cow speaking

    Remember, this is the conceptual interface, not a specific C++ interface.

Creating New Lists

CREATE-LIST()
Create an empty list.
CLONE-LIST(list)
Create a copy of the list.

Operations on Existing Lists

Operations at the Front

GET-FRONT(list)
Return the first string in the list.
PUSH-FRONT(list, str)
Add the given string (_str_) to the front of the list.
POP-FRONT(list)
Remove first string from the list.

Operations at the Back

GET-BACK(list)
Return the last string in the list
PUSH-BACK(list, str)
Add the given string (_str_) to the back of the list.
POP-BACK(list)
Remove the last string from the list.

Operations at Specific (Numeric) Indexes

GET-ITEM-AT(list, idx)
Set the item at the given index (_idx_).
SET-ITEM-AT(list, idx, str)
Set the item at the given index (_idx_) to be the given string (_str_).
INSERT-ITEM-AT(list, idx, str)
Insert the given string (str) at the given index (_idx_); items at _idx_ and beyond move down one position.
ERASE-ITEM-AT(list, idx)
Remove the string at the given index (_idx_); items beyond _idx_ move up one position.

Other Operations

GET-SIZE(list)
Return the number of strings in the list.
DESTROY-LIST(list)
Destroy a list.

Interfaces in C++

In C++, this interface would be expressed in the class definition; specifically, in the public members of the class. Thus the creation of new lists would be the job of constructors, and the operations on existing lists would become member functions.

If we were to actually implement this class in C++, we wouldn't name our functions the same as the generic operations we've listed, as a specific list class might organize those operations in its interface differently.

(When logged in, completion status appears here.)