I don't understand how nodes work in a linked list [closed]

Question

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))

Answer 1

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