Need Help Fixing Linked List Implementation + append method

Question

For practice and to prepare for programming interviews I've by doing problem sets from cracking the interview by Gayle McDowell. That being said I've been answering all the problems in both Python and Java. I'm working with linked list in python at the moment, since i've completed it all in Java already. I'm having trouble adding cargo/node data to the end/tail of my linked list. This was not a problem in Java and I suppose my first mistake is that I'm trying to implement this method the same way I did in Java.

The is the method I need help with

  def append(self, data):.
        new_node = Node()
        new_node = data
        node = self.cur_node
        while node:
            node = node.next
        node.next = new_node

The problem i'm having is that node.next is set to None after the while loop. I thought that if I iterated over the linked list and added my data the to tail end this is how I would go about it. I assumptions are largely based on how I implemented it in Java which I added below just for reference.

 void appendToTail(int d){

        Node end = new Node(d); //Item to append to the end
        Node n = this; //To access Class object next

        while(n.next != null){
            n = n.next;
        }
        n.next = end;
    }

The rest of my python class looks like this, just incase you need to see how the rest of the link list is implemented.

class Node(object):
    def __init__(self):
        self.data = None
        self.next = None

class LinkedList(object):
    def __init__(self):
        self.cur_node = None

    def add(self, data):
        new_node = Node()
        new_node.data = data
        new_node.next = self.cur_node
        self.cur_node = new_node

    #write a method that appends to the tail instead of the head
    def append(self, data):.
        new_node = Node()
        new_node.data = data
        node = self.cur_node
        while node:
            node = node.next
        node.next = new_node #This is the problem line

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print node.data, 
            node = node.next

    # answer to question 2_1
    # Write code to remove duplicates from an unsorted linked list
    def remove_dup(self):
        lset = set()
        previous = Node()
        node = self.cur_node
        while node:
            if node.data in lset:
                previous.next = node.next
            else:
                lset.add(node.data)
                previous = node
            node = node.next

I would love some direction on how to go about fixing or changing my append method.

I'm pretty sure you need to change while node: to while node.next:, but I'm going to test this to be sure. — 1.618
– 1.618, Commented May 10, 2015 at 3:57
Why are you doing new_node = Node() and then immediately throwing that away with new_node = data? Is that supposed to be new_node.data = data or something like that? — abarnert
– abarnert, Commented May 10, 2015 at 4:03
Good luck with your interview practice. I am in the same situation right now... very stressful. — 1.618
– 1.618, Commented May 10, 2015 at 4:10

1.618 · Accepted Answer · 2015-05-10 04:06:59Z

1

Ok, this is what the function should look like:

def append(self, data):
    new_node = Node()
    new_node.data = data
    node = self.cur_node
    while node.next:
        node = node.next
    node.next = new_node #This is the problem line

You were iterating past the end of the list with your original while condition. Instead you want to stop on the last node, which is the one with next == None. and also you apparently had a typo where you were setting the node itself to the data, instead of its data attribute.

answered May 10, 2015 at 4:06

1.618

1,76517 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Need Help Fixing Linked List Implementation + append method

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related