Lists

A list is an sequence of values. It may have properties such as being sorted/unsorted, having duplicate values or being unique. The most important part about list structures is that the data has an ordering (which is not the same as being sorted). Ordering simply means that there is an idea that there is a "first" item, a "second" item and so on. The position within the list where a piece of data is stored may be as important a piece of information as the data itself.

It should be noted at this point that the list we are speaking of here is not the same as a list in Python or a list from the C++ STL. A list here is much more general.

Lists typically have a subset of the following operations:

• initialize
• add an item to the list
• remove an item from the list
• search
• sort
• iterate through all items
• and more...

A list may implement only a subset of the above functionality. The description of a list is very general and it can be implemented in a number of different ways.

Two general implementation methods are the array method or the linked list method. We will look at each in turn.