Transcript 20 Introduction to Lists

Computer Science 112
Fundamentals of Programming II
Lists
Lists: Formal Properties
• A list is a linear collection that supports
access, replacement, insertion, and removal
at any position
• Lists are more general-purpose than stacks
and queues
• No standard set of operations, but most lists
support many typical ones
Categories of List Operations
• Supporting, such as len, isEmpty, iter,
+, ==
• Index-based (use an index position)
• Content-based (use an object)
• Position-based (move a cursor)
Supporting Operations
L.isEmpty()
Returns true if empty, false otherwise
len(L)
Returns the number of items in the list
str(L)
Returns the string representation of the list
iter(L)
Items are served up from the first position through the last one
L1 == L2
Compares items at consecutive positions
L1 + L2
Items from L2 follow the items from L1
Index-Based Operations
L.insert(i, item)
Opens up a slot in the list at index i and inserts item in this slot
L[i]
Returns the item at index i
L.pop(i)
Removes and returns the item at index i (or item at last position if i is
omitted)
L[i] = item
Replaces the item at index i with the item
Preconditions on [] and pop:
0 <= i < length of the list
Content-Based Operations
L.append(item)
adds item at the list’s tail (method add has same effect)
item in L
returns true if the list contains an object equal to item
L.index(item)
returns the index of the first instance of item in the list
L.remove(item)
removes the first instance of item from the list
Preconditions on index and remove:
item must be in the list
Position-Based Operations
for Navigation
LI = L.listIterator() returns a new list iterator object on a list
LI.first()
moves the cursor to the first item
LI.hasNext()
returns true if there are any items following the current position
LI.next()
returns the next item and advances the position
LI.last()
moves the cursor to the last item
LI.hasPrevious()
returns true if there are any items preceding the current position
LI.previous()
returns the previous item and moves the position backward
Similar to an extended iterator
Position-Based Operations
for Mutation
LI.insert(newItem)
LI.remove()
LI.replace(newItem)
inserts newItem at the current position
removes the last item returned by next or previous
replaces the last item returned by next or previous
List Applications
•
•
•
•
object heap storage management
documents
files
implementations of other collections
List Implementations
– list
– ArrayList
– LinkedList
– ListIterator
standard Python (array-based)
array-based
two-way nodes
(allows insertions,
removals, movement to
previous items)
Performance Tradeoffs
lyst = ArrayList()
# Add some objects to lyst
# Traverse the list to print ‘em all
for item in lyst:
print(item)
The simple iterator has the same performance in all list
implementations
Constant-time access to each item, so loop is no worse than
linear
Performance Tradeoffs
lyst = LinkedList()
# Add some objects to lyst
# Traverse the list to print ‘em all
for item in lyst:
print(item)
The simple iterator has the same performance in all list
implementations
Constant-time access to each item, so loop is no worse than
linear
Performance Tradeoffs
lyst = ArrayList()
# Add some numbers to lyst
# Traverse the list to increment ‘em all
for i in range(len(lyst)):
lyst[i] += 1
Index-based traversal of a list using [] is needed to replace all
items
Each [] operation on an array-based list is constant-time, so the
loop is no worse than linear
Performance Tradeoffs
lyst = LinkedList()
# Add some numbers to lyst
# Traverse the list
for i in range(len(lyst)):
lyst[i] += 1
Index-based traversal of a LinkedList using [] looks like it
would be linear, but it’s actually quadratic!
Almost all LinkedList operations are linear, including []
Performance Tradeoffs
lyst = LinkedList()
# Add some objects to lyst
# Traverse the list
rator = lyst.listIterator()
while rator.hasNext():
print(rator.next())
Can use a list iterator for traversals
of a list, in either direction
Performance Tradeoffs
lyst = LinkedList()
# Add some numbers to lyst
# Traverse the list to increment ‘em all
rator = lyst.listIterator()
while rator.hasNext():
number = rator.next()
rator.replace(number + 1)
Can use a list iterator to traverse a
list and replace its items
One-Way Linked Structures
head
5
4
3
2
A one-way linked structure supports movement in one
direction only; cannot move backward
Access at the head is O(1), but access anywhere else is
O(N)
Insertion or removal at the head is a special case
Tweak with a Tail Pointer
head
tail
5
4
3
2
Access to either end is O(1), but generally is still O(N)
Still cannot move backward; insertion or removal at the
head or tail is still a special case
Removal at the tail is still linear
Two-Way Linked Structures
D1
D2
D3
A circular, doubly linked structure with a dummy header
node
• permits movement in both directions
• allows constant-time access to the head or tail
• eliminates special cases in code when access is at the
beginning or the end of the structure
An Empty Structure
When there are no data, there is a single dummy header
node
Its two links point ahead and back to itself
Its data field is None
The Node Class
class TwoWayNode(object):
def __init__(self, data, previous = None, next = None):
self.data = data
self.previous = previous
self.next = next
Strictly a utility class
No need for accessor or mutator methods
Declaring an External Pointer
class TwoWayNode(object):
def __init__(self, data, previous = None, next = None):
self.data = data
self.previous = previous
self.next = next
head = TwoWayNode(None)
head.previous = head.next = head
head
Appending a Node
head.previous always points to the last node
The last node’s next pointer always points back to head
temp = TwoWayNode("A", head.previous, head)
temp
head
“A”
Appending a Node
head.previous always points to the last node
The last node’s next pointer always points back to head
temp = TwoWayNode("A", head.previous, head)
head.previous.next = temp
temp
head
“A”
Appending a Node
head.previous always points to the last node
The last node’s next pointer always points back to head
temp = TwoWayNode("A", head.previous, head)
head.previous.next = temp
head.previous = temp
temp
head
“A”
Analysis
No loop is needed to locate the last node
Append is a constant time operation!
No if statements needed to check for special cases
temp = TwoWayNode("A", head.previous, head)
head.previous.next = temp
head.previous = temp
temp
head
“A”
For Monday
List Iterators