I have a basic understanding of usage of nodes, like node = node.next, and self.head, and things like
node.next = self.head
self.head = new_node
to add whatever is in new_node to the beginning of the list.
However, I am confused about how the key logic in the three update methods of the linked list class works (the code where these lines are from is at the bottom):
In add_update():
new_node.next = node.next
node.next = new_node
In add_before():
prev_node.next = new_node
new_node.next = node
In remove_node():
previous_node.next = node.next
For the "add" methods, I am confused about how everything gets linked, and for the "remove" method, I don't understand how the code above has the desired effect of removal.
The code is the following:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def add_after(self, target_node_data, new_node):
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
def add_before(self, target_node_data, new_node):
if self.head.data == target_node_data:
return self.add_first(new_node)
for node in self:
if node.data == target_node_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node
def remove_node(self, target_node_data):
if self.head.data == target_node_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node
llist = LinkedList(['a', 'b', 'c', 'd', 'e'])
print(repr(llist))
llist.add_after('c', Node('1'))
print(repr(llist))
llist.add_before('d', Node('2'))
print(repr(llist))
llist.remove_node('c')
print(repr(llist))
Here is a detailed annotation of the code you have supplied. Hopefully this will provide some insight into the things your question is asking about.
The nodes in a linked list look like this, for example:
object: node1 node2 node3 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' 'd' 'e'
name: next
contents: node2 node3 node4 node5 None
The linked list object itself looks (in this example) like this:
object: llist
data type: LinkedList
attributes:
name: head
contents: node1
By convention, the first node of a linked list is known as the head of the linked list, and the last node (namely, the node with a next attribute equal to null, or None in python) is known as the tail of the linked list. In our example, node1 is the head and node5 is the tail.
Let's look at the key methods in your LinkedList class (__iter__, add_after, add_before and remove_node).
The __iter__ method:
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
This method allows us to use language constructs like for node in self to iterate through the nodes in the linked list. In our example:
node = self.head # assigns `node1` object to variable node
while node is not None: # tests `True`
yield node # makes `node1` available to the caller on call #1
node = node.next # assigns `node2` to variable node
while node is not None: # tests `True`
yield node # makes `node2` available to the caller on call #2
node = node.next # assigns `node3` to variable node
while node is not None: # tests `True`
yield node # makes `node3` available to the caller on call #3
node = node.next # assigns `node4` to variable node
while node is not None: # tests `True`
yield node # makes `node4` available to the caller on call #4
node = node.next # assigns `node5` to variable node
while node is not None: # tests `True`
yield node # makes `node5` available to the caller on call #5
node = node.next # assigns `None` to variable node
while node is not None: # tests `False`
The add_after method:
def add_after(self, target_node_data, new_node):
for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return
This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately after (or "downstream" of) the matching node.
Suppose we use it like this for our example:
llist.add_after('c', Node('1'))
Then add_after would do this:
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True
# we now want to "splice" new_node in place between node and node.next
new_node.next = node.next # assigns `node4` object (which is referenced by node.next) to new_node.next
node.next = new_node # update node.next to now reference new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_1
return # the method has finished its work, so it returns without examining any further downstream nodes
The nodes in our linked list example now look like this:
object: node1 node2 node3 node3_1 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' 'd' 'e'
name: next
contents: node2 node3 node3_1 node4 node5 None
The add_before method:
def add_before(self, target_node_data, new_node):
if self.head.data == target_node_data:
return self.add_first(new_node)
for node in self:
if node.data == target_node_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node
This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.
Suppose we use it like this for our example:
llist.add_before('d', Node('2'))
Then add_before would do this:
if self.head.data == target_node_data: # handles an edge case: if head is the node we want to add our node before, we need to update our head attribute
return self.add_first(new_node) # this method is not shown in your question, but would simply do this: new_node.next = self.head; self.head = new_node
# NOTE: does not apply in our example
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node1' object in variable prev_node
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'b', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node2' object in variable prev_node
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'c', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3' object in variable prev_node
for node in self: # assigns `node3_1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3_1.data is '1', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3_1' object in variable prev_node
for node in self: # assigns `node4` object to variable node by calling `__iter__`
if node.data == target_node_data: # node4.data is 'd', target_node_data is 'd', so comparison tests True
# we now want to "splice" new_node in place
prev_node.next = new_node # assigns the object referenced by the new_node argument to the next attribute of 'node3_1'
new_node.next = node # assigns 'node4' to the next attribute of new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_2
return # the method has finished its work, so it returns without examining any further downstream nodes
The nodes in our linked list example now look like this:
object: node1 node2 node3 node3_1 node3_2 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' '2' 'd' 'e'
name: next
contents: node2 node3 node3_1 node3_2 node4 node5 None
The remove_node method:
def remove_node(self, target_node_data):
if self.head.data == target_node_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node
This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.
Suppose we use it like this for our example:
llist.remove_node('c')
Then remove_node would do this:
if self.head.data == target_node_data: # handles an edge case: if head is the node we want to remove, we need to update our head attribute
self.head = self.head.next # simply assign self.head.next to the attribute self.head
# NOTE: does not apply in our example
previous_node = self.head # save a reference to the 'node1' object in variable previous_node
for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node1' object in variable previous_node
for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node2' object in variable previous_node
for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True
previous_node.next = node.next # update the next attribute of 'node2' to refer to the next attribute of 'node3', which is 'node3_1'
# NOTE: the object 'node3' is no longer referenced by the next attribute of any nodes in our linked list, which means it has now been removed
return # the method has finished its work, so it returns without examining any further downstream nodes
The nodes in our linked list example now look like this:
object: node1 node2 node3_1 node3_2 node4 node5
data type: Node
attributes:
name: data
contents: 'a' 'b' '1' '2' 'd' 'e'
name: next
contents: node2 node3_1 node3_2 node4 node5 None