CS 1

Data structures

Data structures:

• store data
• provide methods for accessing data
• form the basis for algorithms that manipulate data
• are used for bookkeeping for apprently unrelated algorithms

Google maps

How does this work? Soon, we'll see graph search.

Linked lists

Python lists and linked lists provide the same operations: insert, delete, append, find, replace.

Lists are our first example of an abstract data type: a set of operations, but no specified implementation. Python lists and linked lists are implementations of the 'list' abstract data type.

Different implementations of lists:

• same operations may have different run-times
• Linked lists are special cases of graphs and trees

Python list run-time

Worst cases:

• $\Theta(1)$ access by index, using address computation.
• $\Theta(n)$ insertion, by shifting items to the right.
• $\Theta(n)$ append. (What? Why?)

Python list: append

Naive $\Theta(n)$ approach to appending:

• Make a new area in memory that is one element larger.
• Copy old list into new area.
• Add the new item.
• Automagically update address of all list variables.

Python list: append

Summary: shed full, build new shed one log larger.

Python list: append

Smarter approach to append: plan for the future.

Python list: append

If out of space:

• Make a new area in memory that is one twice as big.
• Copy old list into new area.
• Add the new item.
• Automagically update address of all list variables.

Each list has two sizes:

• length: the number of items in the list (public)
• capacity: the amount of room for the list (internal)

Python list: append

Cost of appending many items, with capacity-doubling?

(Amortized run-time analysis.)

Add 32 items to a (full) list of size 32:

The cost was 64, if we charge 1 for a copy or write.

Cost per item was 2.

Python list: append

Add 64 items to a (full) list of size 64:

The cost was 128, if we charge 1 for a copy or write. Cost per item was 2.

In general, the cost of appending $n$ items is $\Theta(n)$. Amortized, the cost of appending $1$ item is $\Theta(1)$.

Linked lists

Every farmer and every farmer's boy ought to be able to splice a rope, make a rope halter, and tie all the useful knots known to the sailor. To splice a rope is a simple matter, but to teach the art on paper is quite another thing. (J.M.Drew, St. Paul Publishing Company 1918.)

Linked lists

Main idea: objects can contain references to other objects.

A node is a simple object that contains data and a reference to the next node. (Node volunteers?)

A linked list is referred to using the address of the first node, the head node. (node_example.py)

Linked lists

Doubly-linked circular list with sentinel:

• Doubly-linked. Why? (splicing, finding previous)
• Circular. Why? (first and last more uniform)
• sentinel: an extra node with no data. Why? (searching)

Empty list:

(look at init method)

OMG WHAT IS self.sentinel.next = self.sentinel OMG?

Linked lists: insert

Insertion near beginning of Python list is $\Theta(n)$. How about for linked lists? (Volunteers, again.)

Linked lists: deletion

Deletion near beginning of Python list is $\Theta(n)$. How about for linked lists?

Linked list: searching

"find()" method in: sentinel_DLL.py

(Note clever use of sentinel.)