Practice: A List Interface
You've used list (or sequence) data structures before, right? Think about Python lists or Java
ArrayLists
.To start things off, let's think about the interface for this data structure.
Let's imagine a STRING-LIST structure, a list that stores strings.
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.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!
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
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.)