Alex A
Alex A

Reputation: 3

Issue with iterating through Linked List in Python

I am trying to implement a Linked List from scratch in Python 3.7 and after many attempts, I can't seem to get the print_values() method to print all node values in the order that is expected (sequential). At this point I am not sure if the problem is with the append() method or the print_values() method.

    class Node:
        def __init__(self, node_value):
            self.node_value = node_value
            self.nextNode = None


    class SinglyLinkedList:
        # methods that should be available: get_size, insert_at, append, remove, 
        # update_node_value
        def __init__(self):
            self.head_node = None
            self.tail_node = None
            self.size = 0

        def get_list_size(self):
            """This returns the value for the size variable which get incremented 
               every time a new node is added.
               This implementation is better because it has a running time of O(1) 
               as opposed to iterating through the
               whole list which has a running time of O(n)"""
            return self.size

        def append(self, value):
            new_node = Node(value)
            if self.head_node is None:
                self.head_node = new_node
                self.size += 1
            else:
                while self.head_node.nextNode is not None:
                    self.head_node = self.head_node.nextNode
                self.head_node.nextNode = new_node
                self.size += 1

        def print_values(self):
            current_node = self.head_node
            list_values = []
            while current_node.nextNode is not None:
                list_values.append(current_node.node_value)
                if current_node.nextNode.nextNode is None:
                    list_values.append(current_node.nextNode.node_value)
                current_node = current_node.nextNode
            if list_values is not None:
                print("Linked list: " + str(list_values))
            else:
                print("Linked List is currently empty.")


# Helper code below.
new_ll = SinglyLinkedList()
new_ll.append("alpha")
print(new_ll.get_list_size())
new_ll.append("beta")
print(new_ll.get_list_size())
new_ll.append("gamma")
print(new_ll.get_list_size())
new_ll.append("delta")
print(new_ll.get_list_size())
new_ll.append("epsilon")
print(new_ll.get_list_size())
new_ll.append("zeta")
print(new_ll.get_list_size())
new_ll.print_values()

And all I am getting in the output is this:

1
2
3
4
5
6
Linked list: ['epsilon', 'zeta']

Upvotes: 0

Views: 4577

Answers (2)

Typically a singly linked list only keeps track of the head. (Not the tail as well). So self.tail_node = None is not normally used.

When working with a linkedlist or a tree it will make your life a lot easier to work with recursion instead of using loops. Loops work fine if you just want to go over the list but if you want to change it then I would recommend a recursive solution.

That being said the issue isn't with your print it is with your append.

You can NEVER move the head node. You must always make a pointer so this caused the issue:
self.head_node = self.head_node.nextNode

Fix:

def append(self, value):
    new_node = Node(value)
    if self.head_node is None:
        self.head_node = new_node
        self.size += 1
    else:
        temp_head = self.head_node
        while temp_head.nextNode is not None:
            temp_head = temp_head.nextNode
        temp_head.nextNode = new_node
        self.size += 1

Recursive Solution:

def append(self, value):
    new_node = Node(value)
    self.size += 1
    self.head_node = self.__recursive_append(self.head_node, new_node)
def __recursive_append(self, node, new_node):
    if not node:
        node = new_node
    elif not node.nextNode:
        node.nextNode = new_node
    else:
        node.nextNode = self.__recursive_append(node.nextNode, new_node)
    return node

That being said I didn't realize this till after I redid your print so here is a cleaner print method using a python generator that may help you.

Generators is something you can use with python that you can't normally use with other programming languages and it makes something like turning a linked list into a list of values really easy to do:

def print_values(self, reverse=False):
    values = [val for val in self.__list_generator()]
    if values:
        print("Linked list: " + str(values))
    else:
        print("Linked List is currently empty.")

def __list_generator(self):
    '''
    A Generator remembers its state.
    When `yield` is hit it will return like a `return` statement would
    however the next time the method is called it will
    start at the yield statment instead of starting at the beginning
    of the method.
    '''
    cur_node = self.head_node
    while cur_node != None:
        yield cur_node.node_value # return the current node value

        # Next time this method is called
        # Go to the next node
        cur_node = cur_node.nextNode

Disclaimer: The generator is good but I only did it that way to match how you did it (i.e. getting a list from the linkedlist). If a list is not important but you just want to output each element in the linkedlist then I would just do it this way:

def print_values(self, reverse=False):
    cur_node = self.head_node
    if cur_node:
        print('Linked list: ', end='')
        while cur_node:
            print("'{}' ".format(cur_node.node_value), end='')
            cur_node = cur_node.nextNode
    else:
        print("Linked List is currently empty.")

Upvotes: 2

bitbangs
bitbangs

Reputation: 514

I agree with Error - Syntactical Remorse's answer in that the problem is in append and the body of the while loop...here is the example in pseudo code:

append 0:
  head = alpha

append 1:
  //skip the while loop
  head = alpha
  next = beta

append 2:
  //one time through the while loop because next = beta
  head = beta
  //beta beta just got assigned to head, and beta doesn't have next yet...
  next = gamma

append 3:
  //head is beta, next is gamma...the linked list can only store 2 nodes
  head = gamma //head gets next from itself
  //then has no next
  next = delta

...etc.

Upvotes: 0

Related Questions