Python data structure problem next_node type problem?

Question

I want to set data into my linked list. but what is the problem in my code? How can i add a new linked list?

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


class LinkedList:
    def __init__(self, head_node=None):
        self.head_node = Node(head_node)

    def add_new_head(self, new_head_node):
        # --------> what line of code goes here?
        
        self.head_node = new_head_node
        new_head_node.next_node = self.head_node
li= LinkedList(4)
li.add_new_head(5)
li.add_new_head(6)
print(li)

Answer 1

There are some issues:

• The names of the parameters head_node and new_head_node are misleading: these are not instances of Node as their names suggest, but are values (integers) to be used for creating nodes. So maybe call them head_value and new_head_value

  Probably because of this misnaming, you do self.head_node = new_head_node, but that will assign an integer to an attribute that is supposed to be a node reference. In the __init__ method you did it correctly, and first created a Node and then assigned that to self.head_node. The same should happen in add_new_head.

• The assignment new_head_node.next_node = self.head_node comes to late: by that time self.head_node is already equal to new_head_node, and so (if the previous error were corrected), this would create a circular reference.

• Not a problem, but as your Node constructor allows for an optional argument for the next node, you could make use of this in add_new_head, making the code rather elegant.

• Your LinkedList constructor always creates a node. This is not right, as this way you cannot make an empty linked list. It is not really clear to me why you would pass a value to this constructor. Either don't have this parameter, or allow multiple values to be passed as argument. There is no reason why you need this constructor to allow for one value.

• print(li) will not display something that is useful. To get some readable output, implement the __repr__ method so it returns the list as a string (that can be printed with print)

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


class LinkedList:
    def __init__(self):  # No extra parameter: just create an empty linked list
        self.head_node = None

    def add_new_head(self, new_head_value):  # argument is a value
        # Create node with Node constructor, and use second argument to link it
        self.head_node = Node(new_head_value, self.head_node)  

    def __iter__(self):  
        node = self.head_node
        while node:
            yield node.value
            node = node.next_node
            
    def __repr__(self):
        return " ".join(map(repr, self))  # This uses __iter__

li = LinkedList()  # No arguments here. Use `add_new_head` for adding values
li.add_new_head(4)
li.add_new_head(5)
li.add_new_head(6)
print(li)

Explanation of self.head_node = Node(new_head_value, self.head_node)

This code calls the Node constructor, providing it also with the optional argument. For instance, in the above main program, the situation after having inserted two nodes is as follows:

┌─li────────────┐
│ head_node: ─────┐  
└───────────────┘ │
                  │
                ┌─┴─────────┐   ┌───────────┐
                │ val: 5    │   │ val: 4    │
                │ next: ────────┤ next: None│
                └───────────┘   └───────────┘

When we call li.add_new_head(6), and execute Node(new_head_value, self.head_node), then the constructor will run and will get the value 6 as argument, and a reference of the current head node, i.e. the node with value 5. The constructor will initialise the new node as illustrated below:

┌─li────────────┐
│ head_node: ─────┐  
└───────────────┘ │
                  │
┌───────────┐   ┌─┴─────────┐   ┌───────────┐
│ val: 6    │   │ val: 5    │   │ val: 4    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

Note that it has its next referencing the current head node. The constructor returns a reference to the new node, and so the add_new_head function will assign it to self.head_node, which results in:

┌─li────────────┐
│ head_node: ─────┐  
└───────────────┘ │
      ┌───────────┘
┌─────┴─────┐   ┌───────────┐   ┌───────────┐
│ val: 6    │   │ val: 5    │   │ val: 4    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

...and that completes the action.