Chapter 14

These are the solutions to the exercises found in the section .

1. One way we can do this is with a simple while loop:

   ​	​def​ ​print_list​(self):
   ​	current_node = self.first_node
   ​
   ​	​while​ current_node:
   ​	​print​(current_node.data)
   ​	current_node = current_node.next_node

2. With a doubly linked list, we have immediate access to the last nodes and can follow their “previous node” links to access the previous nodes. This code is basically the inverse of the previous exercise:

   ​	​def​ ​reverse_print​(self):
   ​	current_node = self.last_node
   ​
   ​	​while​ current_node:
   ​	​print​(current_node.data)
   ​	current_node = current_node.previous_node

3. Here, we use a while loop to move through each node. However, before we move forward, we check ahead using the node’s link to ensure that there is a next node:

   ​	​def​ ​last​(self):
   ​	current_node = self.first_node
   ​
   ​	​while​ current_node.next_node:
   ​	current_node = current_node.next_node
   ​
   ​	​return​ current_node.data

   For fun, here’s an alternative implementation that uses recursion:

   ​	​def​ ​recursive_last​(self, current_node=None):
   ​	​if​ ​not​ current_node:
   ​	current_node = self.first_node
   ​
   ​	​if​ current_node.next_node:
   ​	​return​ self.recursive_last(current_node.next_node)
   ​	​else​:
   ​	​return​ current_node.data

4. One way to reverse a classic linked list is to iterate through the list while keeping track of three variables.

   The primary variable is the current_node, which is the primary node we’re iterating over. We also keep track of the next_node, which is the node immediately after the current_node. And we also keep track of the previous_node, which is the node immediately before the current_node. See the following diagram:

   

   Note that when we first begin and the current_node is the first node, the previous_node points to None; there are no nodes before the first node.

   Once we have our three variables set up, we proceed with our algorithm, which begins a loop.

   Inside the loop, we first change the current_node’s link to point to the previous_node:

   

   Then we shift all our variables to the right:

   

   We begin the loop again, repeating this process of changing the current_node’s link to point to the previous_node, until we reach the end of the list. Once we reach the end, the list will have been fully reversed.

   Here’s the implementation for this algorithm:

   ​	​def​ ​reverse​(self):
   ​	previous_node = None
   ​	current_node = self.first_node
   ​
   ​	​while​ current_node:
   ​	next_node = current_node.next_node
   ​	current_node.next_node = previous_node
   ​
   ​	previous_node = current_node
   ​	current_node = next_node
   ​
   ​	self.first_node = previous_node

5. Believe it or not, we can delete a middle node without having access to any of the nodes that precede it.

   Following is a diagram of an example situation. We have four nodes, but we only have access to node "b". This means we don’t have access to node "a", since links only point forward in a classic linked list. We’ve indicated this using a dashed line; that is, we don’t have access to any node to the left of the dashed line:

   

   Now, here’s how we can delete node "b" (even though we don’t have access to node "a"). For the sake of clarity, we’re going to call this node the “access node,” since it’s the first node we have access to.

   First, we take the next node beyond the access node and copy its data into the access node, overwriting the access node’s data. In our example, this means copying the string "c" into our access node:

   

   We then change the link of the access node and have it point to the node that is two nodes to the right of it. This effectively deletes the original "c" node:

   

   The code for this is short and sweet:

   ​	​def​ ​delete_node​(node):
   ​	node.data = node.next_node.data
   ​	node.next_node = node.next_node.next_node