Transcript 21 List Iterators

Computer Science 112
Fundamentals of Programming II
List Iterators
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
P
D N
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”
Opening a List Iterator on a List
lyst = LinkedList(range(11, 21))
# or ArrayList(range(11, 21))
rator = aList.listIterator()
rator.last()
while rator.hasPrevious():
print(rator.previous())
rator
# print in reverse order
lyst
Maintains a cursor to access 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
Mutations with a List Iterator
lyst = LinkedList(range(11, 21))
# or ArrayList(range(11, 21))
# Replace all ints with 0s
for i in range(len(lyst)):
lyst[i] = 0
Using an index-based loop with the subscript would
be O(n2) with a linked list
Mutations with a List Iterator
lyst = LinkedList(range(11, 21))
# or ArrayList(range(11, 21))
# Replace all ints with 0s
rator = lyst.listIterator()
while rator.hasNext():
rator.next()
rator.replace(0)
Using an index-based loop with the subscript would
be O(n2) with a linked list
Can Do Just One Insertion
on Each Pass
lyst = LinkedList(range(11, 21))
# Insert 1s before each integer
rator = lyst.listIterator()
while rator.hasNext():
rator.next()
rator.insert(1)
# or ArrayList(range(11, 21))
Consecutive Mutations Should
Raise an Error
lyst = LinkedList(range(11, 21))
# or ArrayList(range(11, 21))
# Error: must have a separate next() prior to each add
rator = lyst.listIterator()
while rator.hasNext():
rator.next()
rator.insert(1)
rator.insert(2)
Using a Mutator to Clear the List
lyst = LinkedList(range(11, 21))
# Clear the list (make it empty)
rator = lyst.listIterator()
while rator.hasNext():
rator.next()
rator.remove()
# or ArrayList(range(11, 21))
Can’t Use List Mutators
lyst = LinkedList(range(11, 21))
# or ArrayList(range(11, 21))
# Clear the list (make it empty)
rator = lyst.listIterator()
while rator.hasNext():
lyst.pop()
rator.next()
rator.remove()
Directly mutating the backing store in the context of
an iterator can cause the store and the iterator to
become inconsistent
The iterator will need to know when the store has
changed and raise an exception in that event
Tracking Mutations
• The list and its iterator each keep separate modCount
variables
• The list’s modCount is initially 0, and is incremented on
each mutation
• The iterator’s modCount is initialized to the list’s current
modCount
• Each call of next or previous compares the counts,
and if they’re different, raises an exception
The List’s modCount
• The modCount is tracked in
AbstractCollection
• Methods include
– getModCount
– incModCount
– resetSizeAndModCount
The List’s modCount
class ArrayList(AbstractList):
"""Represents an array-based list."""
DEFAULT_CAPACITY = 8
def __init__(self, sourceCollection = None):
self._items = Array(ArrayList.DEFAULT_CAPACITY)
AbstractList.__init__(self, sourceCollection)
def pop(self, i = None):
"""Precondition: 0 <= i < len(self)
Removes and returns the item at position i."""
if i is None: i = len(self) - 1
if i < 0 or i >= len(self):
raise IndexError("List index out of range")
item = self._items[i]
for j in range(i, len(self) - 1):
self._items[j] = self._items[j + 1]
self._size -= 1
self.incModCount()
# Track mutations!
return item
The ListIterator Class
class ArrayList(AbstractList):
"""Represents an array-based list."""
def listIterator(self):
"""Returns a list iterator."""
return ArrayList.ListIterator(self)
Because the ListIterator will be implemented
differently for each list implementation, we can nest it
in the list class
The ListIterator Class
class ArrayList(AbstractList):
"""Represents an array-based list."""
def listIterator(self):
"""Returns a list iterator."""
return ArrayList.ListIterator(self)
class ListIterator(object):
"""Represents the list iterator for an array list."""
def __init__(self, backingStore):
self._backingStore = backingStore
self._modCount = backingStore.getModCount()
self.first()
def first(self):
"""Returns the cursor to the beginning."""
self._cursor = 0
self._lastItemPos = -1
# Other ListIterator methods go here
The next Method
class ListIterator(object):
"""Represents the list iterator for an array list."""
def next(self):
"""Preconditions: hasNext returns True
The list has not been modified except by this iterator's mutators.
Returns the current item and advances the cursor to the next item.""”
if not self.hasNext():
raise ValueError("No next item in list iterator")
if self._modCount != self._backingStore.getModCount():
raise AttributeError("Illegal modification of backing store")
self._lastItemPos = self._cursor
self._cursor += 1
return self._backingStore[self._lastItemPos]
Moving from Right to Left
def last(self):
"""Moves the cursor to the end of the backing store."""
self._cursor = len(self._backingStore)
self._lastItemPos = -1
def hasPrevious(self):
"""Returns True if the iterator has a previous item or False otherwise."""
return self._cursor > 0
def previous(self):
"""Preconditions: hasPrevious returns True
The list has not been modified except by this iterator's mutators.
Returns the current item and moves the cursor to the previous item."""
if not self.hasPrevious():
raise ValueError("No previous item in list iterator")
self._lastItemPos = self._cursor - 1
self._cursor -= 1
return self._backingStore[self._lastItemPos]
For Wednesday
Sorted Lists