Lists

We spent the first half of the course building our toolbox with the knowledge, skills, and programming constructs needed to create and use data structures, including:

The memory model of Python
Big-O notation
Recursion
Arrays and linked lists

With this knowledge, we are finally ready to describe some new ADTs! We will start with a "list."

The list ADT

A list is a data structure in which items can be inserted, accessed, and removed from any position. In other words, a list has the following properties:

Order matters: you can ask to insert, get, or remove an element at a specific position i
Duplicates are allowed: there is no restriction regarding duplicates

It might be helpful to contrast the idea of a list with the set ADT, in which order did not matter (we could only grab a random element) and duplicates were not allowed.

To go along with our ADT, we can specify some operations that we want lists to support:

get_item(i): get the item at position i
add_item(item, i): add the specified item at position i
remove_item(i): remove the item at position i
length(): get the number of items in the list
is_full(): test if the list already has the maximum number of items
to_string(): return a string representation of the list

The methods for the list ADT above are just defined for our purposes in this class -- there is no specific set of methods that a "list" is required to support in general. For example, Python's built-in list data structure is similar to this definition of the list ADT. However, it doesn't have any concept of being "full" (and so doesn't have a is_full() method) and also has other functionality, such as slicing.

Linked lists vs. lists vs. Python lists

At this point we have learned about a few entities that are all called lists, so let's take a moment to remember the differences between them.

A linked list is a building block data structure in which data is connected using nodes and references. It can used to implement various ADTs.

A list is an ADT that represents a sequential collection of data where order matters and duplicates are allowed. It could be implemented in various ways, including using an array or a linked list.

A Python list is a Python-specific implementation of the list ADT, which uses an array under the hood along with some additional functionality (e.g., slicing).

Implementing a list using an array

After creating the list ADT, the next question to ask is how should we implement it? Since a list is a sequential data structure, it's natural to consider an array.

Of course, since arrays don't exist as a built-in feature of Python, we will use Python lists. But recall that Python lists are implemented using arrays, so we need to keep that in mind as we use Python lists to implement the list ADT.

Watch the video below to see how the list ADT could be implemented using a Python list (i.e., an array):

Check your understanding

In the add_item() method, to insert an item at position i we used a loop that started at the end of the list of items (self.length - 1), and moved over each item one-by-one until we reached item i:

for j in range(self.length - 1, i - 1, -1):
    self.items[j + 1] = self.items[j]

The loop proceeded from right to left. If you tried to implement the loop by iterating from element i up to element self.length - 1 (left to right), it would look like this:

for j in range(i, self.length):
    self.items[j + 1] = self.items[j]

However, this won't work. Why not?

Click to reveal the answer.

Answer. If you move the elements over from left-to-right, you will just end up copying the element at index i throughout the list -- into every position that the loop touches.

Implementing a list using a linked list

The other natural choice for implementing the list ADT would be to use a linked list. Watch the video below to see how this would work:

Note: The class name LLList was chosen because it is the linked list (LL) implementation of a list.

Summary

Let's summarize the tradeoffs between the array and linked list implementations of the list ADT:

	`ArrayList`	`LLList`
`get_item()`	`O(1)` in all cases	Best: `O(1)` (`get_item(0)`) Average/Worst: `O(n)` (getting item at middle/end)
`add_item()`	Best: `O(1)` (adding to end) Average/Worst: `O(n)` (adding to beginning/middle)	Best: `O(1)` (`add_item(0)`) Average/Worst: `O(n)` (adding to middle/end)