Functioning Chained List

Question

I’m trying to implement a chained list scheme in Python and was debugging the code to better understand how it works. I’m curious about some things.

The code I’m implementing is as follows::

class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None

    def get_data(self):
        return self.data

    def set_data(self, data):
        self.data = data

    def get_next_node(self):
        return self.next_node

    def set_next_node(self, next_node):
        self.next_node = next_node

    def __str__(self):
        return str(self.data)


class List:
    def __init__(self):
        self.first_node = None
        self.last_node = None

    def insert_at_last_node(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.first_node = self.last_node = new_node
        else:
            self.last_node.set_next_node(new_node)
            self.last_node = new_node

    def insert_at_first_node(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.first_node = self.last_node = new_node
        else:
            new_node.set_next_node(self.first_node)
            self.first_node = new_node

    def remove_first_node(self):
        if self.is_empty():
            raise (IndexError, 'Lista vazia!')
        pop_value = self.first_node.get_data()
        if self.first_node == self.last_node:
            self.first_node = self.last_node = None
        else:
            self.first_node = self.first_node.get_next_node()
        return pop_value

    def is_empty(self):
        return self.first_node is None

    def __str__(self):
        string = ''
        value = self.first_node
        while value is not None:
            string = string + str(value.get_data()) + ' -> '
            value = value.get_next_node()
        return string

First order of business:

In function insert_at_last_node, when I activate the method set_next_node in the variable self.last_node, why the variable self.first_node is also updated?

Second order:

For the following function modification insert_at_last_node:

def insert_at_last_node(self, value):
    new_node = Node(value)
    if self.is_empty():
        self.first_node = new_node
    else:
        self.first_node.set_next_node(new_node)

Why is the variable self.first_node does not add all due values as was done in the previous code situation?

You can observe these behaviors by running the following script in a parallel file:

from nodes import List

new_list = List()
new_list.insert_at_last_node(5)
new_list.insert_at_last_node(4)
new_list.insert_at_last_node(3)
print(new_list)

Answer 1

Tip: puts a print(self) inside the list insertion function, so you can better track its behavior:

def insert_at_last_node(self, value):
    new_node = Node(value)
    print(self)
    if self.is_empty():
        self.first_node = self.last_node = new_node
    else:
        self.last_node.set_next_node(new_node)
        self.last_node = new_node

Making the insertion as the one you indicated, of the values 5, 4 and 3, the output of the program will be:

5 ->
5 -> 4 ->
5 -> 4 -> 3 ->

Which is correct, it only updates first_node and last_node at the same time, as you said, when the list was empty and you want to insert the first element, and in this case really, it will be the first and the last, for being the only one inside.

In your second question, this change in function insert_at_last_node you are making only two changes in the list:

1. Pointing out which is the first node if the list is empty (if)
2. Changing the value of the next of the first, if the list has some value()

In other words, this list of yours will not be more than two elements, and every time you try to insert more than that it will only change the value of the latter. This would be the exit from this list (inserting 5, 4, 3, 2, 1):

5 ->
5 -> 4 ->
5 -> 3 ->
5 -> 2 ->
5 -> 1 ->

When it should be:

5 ->
5 -> 4 ->
5 -> 4 -> 3 ->
5 -> 4 -> 3 -> 2 ->
5 -> 4 -> 3 -> 2 -> 1 ->

When you want to insert a node at the end of a chained list the steps are to update the next of what is currently the last one to what you want to insert (before it pointed to None) and update that the last one is now this new node, what already occurs in this code snippet you provided:

self.last_node.set_next_node(new_node)
self.last_node = new_node