Chapter 07
In [1]:
import copy
Exercises
R-7.2
Describe a good algorithm for concatenating two singly linked lists L and M, given only reference to the
first node of each list, into a single list L′ that contains all the nodes of L followed by all nodes of M.
Answer
In [2]:
class Empty(Exception):
pass
In [3]:
class LinkedStack:
"""LIFO Stack implementatino using a singly linked list for storage"""
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, nxt):
self._element = element
self._next = nxt
def __init__(self):
self._head = None
self._size = 0
def __len__(self):
return self._size
def __iter__(self):
cur = self._head
while cur is not None:
yield cur._element
cur = cur._next
def is_empty(self):
return self._size == 0
def push(self, e):
self._head = self._Node(e, self._head)
self._size += 1
def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self._head._element
def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
answer = self._head._element
self._head = self._head._next
self._size -= 1
return answer
In [4]:
L = LinkedStack()
In [5]:
[Link](5)
[Link](4)
[Link](3)
In [6]:
[i for i in L]
Out[6]:
[3, 4, 5]
In [7]:
M = LinkedStack()
[Link](3)
[Link](2)
[Link](1)
In [8]:
[i for i in M]
Out[8]:
[1, 2, 3]
Making a new LinkedStack is less efficient (n pop & n push for each list) than just making the base list's
last node to designate the head of the list to be appended (n references for traversing).
In [9]:
def concat_singly_linked_stack(base, append):
base = [Link](base)
append = [Link](append)
base_last = None
cur = base._head
while True: # Need to traverse whole list since LinkedStack does not
keep its last node.
if cur._next is None:
base_last = cur
break
cur = cur._next
base_last._next = append._head
base._size += append._size
return base
In [10]:
concat_list = concat_singly_linked_stack(L, M)
In [11]:
[i for i in concat_list]
Out[11]:
[3, 4, 5, 1, 2, 3]
R-7.3
Describe a recursive algorithm that counts the number of nodes in a singly linked list.
Answer
In [12]:
def recursive_count(list_head):
"""
list_head: head reference to a list
"""
if list_head._next is None:
return 1
else:
return 1 + recursive_count(list_head._next)
In [13]:
recursive_count(concat_list._head)
Out[13]:
6
R-7.7
Our CircularQueue class provides a rotate() method that has semantics equivalent
to [Link]([Link]()), for a nonempty queue. Implement such a method for the LinkedQueue class
without the creation of any new nodes.
Answer
In [14]:
class LinkedQueue:
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, nxt):
self._element = element
self._next = nxt
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def __len__(self):
return self._size
def __iter__(self):
cur = self._head
while cur is not None:
yield cur._element
cur = cur._next
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Empty("Queue is empty")
return self._head._element
def dequeue(self):
if self.is_empty():
raise Empty("Queue is empty")
answer = self._head._element
self._head = self._head._next
self._size -= 1
if self.is_empty():
self._tail = None
return answer
def enqueue(self, e):
newest = self._Node(e, None)
if self.is_empty():
self._head = newest
else:
self._tail._next = newest
self._tail = newest
self._size += 1
rotate method in LinkedQueue should dequeue the first element and insert it back into its tail by enqueue
In [15]:
def rotate(self):
if self._size > 0:
old_head = self._head
self._head = old_head._next
self._tail._next = old_head
old_head._next = None
[Link] = rotate # monkey patching
In [16]:
q = LinkedQueue()
[Link](5)
[Link](4)
[Link](3)
[Link](2)
[Link](1)
In [17]:
[Link]()
In [18]:
[i for i in q]
Out[18]:
[4, 3, 2, 1, 5]
R-7.13
Update the PositionalList class to support an additional method find(e), which returns the position of the
(first occurrence of )element e in the list (or None if not found).
In [19]:
class _DoublyLinkedBase:
"""A base calss providing a doubly linked list representation."""
class _Node:
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, nxt):
self._element = element
self._prev = prev
self._next = nxt
def __init__(self):
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer
self._trailer._prev = self._header
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def _insert_between(self, e, predecessor, successor):
newest = self._Node(e, predecessor, successor)
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node(self, node):
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element
node._prev = node._next = node._element = None
return element
In [20]:
class PositionalList(_DoublyLinkedBase):
class Position:
"""An abstraction representing the location of a single element."""
def __init__(self, container, node):
self._container = container
self._node = node
def element(self):
return self._node._element
def __eq__(self, other):
return type(other) is type(self) and other._Node is self._node
def __ne__(self, other):
return not (self == other)
def _validate(self, p):
if not isinstance(p, [Link]):
raise TypeError('p must be proper Position type')
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._next is None:
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
if node is self._header or node is self._trailer:
return None
else:
return [Link](self, node)
def first(self):
return self._make_position(self._header._next)
def last(self):
return self._make_position(self._trailer._prev)
def before(self, p):
node = self._validate(p)
return self._make_position(node._prev)
def after(self, p):
node = self._validate(p)
return self._make_position(node._next)
def __iter__(self):
cursor = [Link]()
while cursor is not None:
yield [Link]()
cursor = [Link](cursor)
def _insert_between(self, e, predecessor, successor):
node = super()._insert_between(e, predecessor, successor)
return self._make_position(node)
def add_first(self, e):
return self._insert_between(e, self._header, self._header._next)
def add_last(self, e):
return self._insert_between(e, self._trailer._prev, self._trailer)
def add_before(self, p, e):
original = self._validate(p)
return self._insert_between(e, original._prev, original)
def add_after(self, p, e):
original = self._validate(p)
return self._insert_between(e, original, original._next)
def delete(self, p):
original = self._validate(p)
return self._delete_node(original)
def replace(self, p, e):
original = self._validate(p)
old_value = original._element
original._element = e
return old_value
In [21]:
def find(self, e):
cur = [Link]()
while True:
if cur is None:
return None
if [Link]() == e:
return cur
cur = [Link](cur)
[Link] = find # Monkey patching
In [22]:
p = PositionalList()
In [23]:
for i in [2, 8 ,1, 10, 9, 8, 4, 3]:
p.add_first(i)
In [24]:
[Link]().element()
Out[24]:
3
In [25]:
[i for i in p]
Out[25]:
[3, 4, 8, 9, 10, 1, 8, 2]
In [26]:
[Link](10)
Out[26]:
<__main__.[Link] at 0x7fc2a05e9be0>
In [27]:
[Link]([Link](10)).element()
Out[27]:
9
In [28]:
[Link](8)
Out[28]:
<__main__.[Link] at 0x7fc2a063aba8>
In [29]:
[Link]([Link](8)).element()
Out[29]:
9
In [30]:
[Link](99) # Not found: None
R-7.14
Repeat the previous process using recursion. Your method should not contain any loops. How much space
does your method use in addition to the space used for L?
In [31]:
def find_recursive(self, cur_pos, e):
if cur_pos is None:
return None
elif cur_pos.element() == e:
return cur_pos
else:
cur_pos = [Link](cur_pos)
return find_recursive(self, cur_pos, e)
PositionalList.find_recursive = find_recursive # Monkey patching
In [32]:
[i for i in p]
Out[32]:
[3, 4, 8, 9, 10, 1, 8, 2]
In [33]:
p.find_recursive([Link](), 1)
Out[33]:
<__main__.[Link] at 0x7fc2a05e9a20>
In [34]:
[Link](p.find_recursive([Link](), 1)).element()
Out[34]:
10
In [35]:
p.find_recursive([Link](), 8)
Out[35]:
<__main__.[Link] at 0x7fc2a0650588>
In [36]:
[Link](p.find_recursive([Link](), 8)).element()
Out[36]:
9
In [37]:
p.find_recursive([Link](), 99) # Not found: None
C-7.24
Give a complete implementation of the stack ADT using a singly linked list that includes a header sentinel.
In [38]:
class LinkedStackwithSentinel:
"""LIFO Stack implementatino using a singly linked list for storage"""
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, nxt):
self._element = element
self._next = nxt
def __init__(self):
self._header = self._Node(None, None)
self._header._next = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def push(self, e):
new = self._Node(e, self._header._next)
self._header._next = new
self._size += 1
def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self._header._next._element
def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
pop_node = self._header._next
self._header._next = pop_node._next
answer = pop_node._element
pop_node = None
self._size -= 1
return answer
In [39]:
x = LinkedStackwithSentinel()
In [40]:
[Link](5)
[Link](3)
[Link](1)
In [41]:
[Link]()
Out[41]:
1
In [42]:
print([Link]())
print([Link]())
print([Link]())
1
3
5
In [43]:
try:
[Link]()
except Empty:
print("proper error")
proper error
C-7.25
Give a complete implementation of the queue ADT using a singly linked list that includes a header
sentinel.
In [44]:
class LinkedQueuewithSentinel:
class _Node:
__slots__ = '_element', '_next'
def __init__(self, element, nxt):
self._element = element
self._next = nxt
def __init__(self):
self._header = self._Node(None, None)
self._header._next = None
self._tail = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Empty("Queue is empty")
return self._header._next._element
def dequeue(self):
if self.is_empty():
raise Empty("Queue is empty")
dequeue_node = self._header._next
self._header._next = dequeue_node._next
answer = dequeue_node._element
dequeue_node = None
self._size -= 1
if self.is_empty():
self._tail = None
return answer
def enqueue(self, e):
newest = self._Node(e, None)
if self.is_empty():
self._header._next = newest
else:
self._tail._next = newest
self._tail = newest
self._size += 1
In [45]:
x = LinkedQueuewithSentinel()
In [46]:
[Link](5)
[Link](4)
[Link](3)
In [47]:
[Link]()
Out[47]:
5
In [48]:
[Link]()
Out[48]:
5
In [49]:
[Link]()
Out[49]:
4
In [50]:
[Link](10)
In [51]:
[Link]()
Out[51]:
3
In [52]:
[Link]()
Out[52]:
10
In [53]:
[Link]()
Out[53]:
10
In [54]:
try:
[Link]()
except Empty:
print("proper error")
proper error