Computers are really good at dealing with large amounts of information. They can repeat a task over and over again without getting bored. When they repeat a task they are generally doing the same thing to similar data or objects. It is natural to want to organize those objects into some kind of structure so that our program can easily switch from one object to the next. How objects are added to a sequence or collection and how we move from one item to the next has some impact on how we might want to organize the collection of data in a program.

In this chapter we look at different ways of organizing data into a sequence. We'll also examine how to use Python to make working with sequences convenient. Operator overloading in Python lets us build sequences that we can manipulate with intuitive operations. Finally, we'll also examine how the organization of a sequence affects the computation complexity of operations on it.

An Abstract Data Type is a term that is used to describe a way of organizing data. Lists are one way of organizing a sequence of data, but in this chapter we'll discover other ways of organizing sequences as well. Ascending and descending sequences, linked lists, stacks, and queues are all abstract data types that we'll explore in this chapter.

4.1 Chapter Goals

In this chapter you will read about different ways of organizing data within a program. By the end of the chapter you should be able to answer these questions.

• When presented with an algorithm that requires you to maintain a sequence of data, which organizational scheme fits best?

• What are the trade-offs of selecting one type of sequence as opposed to another?

• What are some interesting algorithms that use lists, linked lists, stacks, or queues?

• What sorting algorithm is most commonly used when sorting a sequence of ordered values?

• What search algorithms are possible in a sequence?

• What is the complexity of many of the common operations on sequences and how is that complexity affected by the underlying organization of the data.

You will also be presented with a few interesting programming problems that will help you learn to select and use appropriate data structures to solve some interesting problems.

4.2 Lists

In the first and second chapter we developed a sequence called PyList. The PyList class is really just a repackaging of the Python list class. The example sequence demonstrates some of the operators that are supported by Python. In this section we want to look more deeply into how lists are implemented. There are many operations supported on lists. Chapter 16 contains the full list. The table in Fig. 4.1 is a subset of the operations supported by lists.

Each of the operations in the table has an associated complexity. The performance of an algorithm depends on the complexity of the operations used in implementing that algorithm. In the following sections we'll further develop our own list datatype, called PyList, using the built-in list only for setting and getting elements in a list. The indexed get and indexed set operations can be observed to have O(1) complexity. This complexity is achieved because the memory of a computer is randomly accessible, which is why it is called Random Access Memory. In Chap. 2 we spent some time demonstrating that each location within a list is accessible in the same amount of time regardless of list size and location being retrieved. In the following sections we'll enhance the PyList datatype to support the operations given in this table.

Operation

Complexity

Usage

Method

List creation

O(n) or O(1)

x = list(y)

calls init (y)

indexed get

O(1)

a= x[i]

x. getitem (i)

indexed set

O(1)

x[i] =a

x. setitem (i,a)

concatenate

O(n)

z=x+y

z= x. add (y)

append

O(1)

x.append(a)

x.append(a)

insert

O(n)

x.insert(i,e)

x.insert(i,e))

delete

O(n)

del x[i]

x. delitem (i)

equality

O(n)

x ==y

x. eq (y)

iterate

O(n)

for a in x:

x. iter__()

length

O(1)

len(x)

x. len__()

membership

O(n)

a inx

x. contains (a)

sort

O(n log n)

x.sort()

x.sort()

Fig. 4.1 Complexity of List Operations

Found a mistake? Please highlight the word and press Shift + Enter