CODEWITHSUNDEEP
pythondata-structureslinked-list
S s
S s

Reputation: 877

Inserting Into Linked List Python

I've create a pretty standard linked list in python with a Node class and LinkedList class. I've also added in methods for LinkedList as follows:

  1. add(newNode): Adds an element to the linked list
  2. addBefore(valueToFind, newNode): Adds a new node before an element with the value specified.
  3. printClean: Prints the linked list

I'm trying to use the addBefore method to perform an insertion, however it will not work if the insertion isn't on the head. I'm not sure why.

class Node:
    def __init__(self, dataval =None):
        self.dataval = dataval
        self.nextval = None

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

    def add(self, newNode):
        # The linked list is empty
        if(self.headval is None):
            self.headval = newNode
        else:
            # Add to the end of the linked list
            currentNode = self.headval
            while currentNode is not None:
                # Found the last element
                if(currentNode.nextval is None):
                    currentNode.nextval = newNode
                    break
                else:
                    currentNode = currentNode.nextval


    def addBefore(self, valueToFind, newNode):
        currentNode = self.headval
        previousNode = None
        while currentNode is not None:
            # We found the element we will insert before
            if (currentNode.dataval == valueToFind):
                # Set our new node's next value to the current element
                newNode.nextval = currentNode

                # If we are inserting at the head position
                if (previousNode is None):
                    self.headval = newNode
                else:
                    # Change previous node's next to our new node
                    previousNode.nexval = newNode
                    return 0

            # Update loop variables
            previousNode = currentNode
            currentNode = currentNode.nextval
        return -1

    def printClean(self):
        currentNode = self.headval
        while currentNode is not None:
            print(currentNode.dataval, end='')
            if(currentNode.nextval != None):
                print("->", end='')
                currentNode = currentNode.nextval
            else:
                return

testLinkedList = LinkedList()
testLinkedList.add(Node("Monday"))
testLinkedList.add(Node("Wednesday"))
testLinkedList.addBefore("Wednesday", Node("Tuesday"))
testLinkedList.printClean()

Monday->Wednesday

Upvotes: 2

Views: 877

Answers (4)

neutrino_logic
neutrino_logic

Reputation: 1299

Here's a fix that changes how you look for the next Node to insert before, and treats any head insertion separately. I also changed the names of variables and class attributes to make things a little clearer:

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nodepointer = None

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

Since each Node contains a reference to the next Node, called it nodepointer. This helps here (I think):

    def addBefore(self, valueToFind, newNode):

        currentNode = self.headnode

        if currentNode.dataval == valueToFind:    #treat the front-end insertion as a 
            newNode.nodepointer = self.headnode   #special case outside the while loop
            self.headnode = newNode
            return -1

        while currentNode.nodepointer:            #notice lose all the 'is None' syntax
            # We found the element we will insert before *by looking ahead*
            if currentNode.nodepointer.dataval == valueToFind:
                # Set our new node's next *reference* to the current element's *next ref*
                newNode.nodepointer = currentNode.nodepointer
                currentNode.nodepointer = newNode  #now link 'previous' to new Node
                return -1                
            # Update loop variables
            currentNode = currentNode.nodepointer  #if this is None, while loop ends
        return 0

This is more like a traditional C-style linked list, I think.

Upvotes: 0

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

To elaborate on Satvir Kira's comment, use this test harness

monday = Node("Monday")
tuesday = Node("Tuesday")
wednesday = Node("Wednesday")

testLinkedList = LinkedList()
testLinkedList.add(monday)
testLinkedList.add(wednesday)
testLinkedList.addBefore(wednesday.dataval, tuesday)

print (monday.__dict__)
print (tuesday.__dict__)
print (wednesday.__dict__)

Output:

{'dataval': 'Monday', 'nextval': Wednesday, 'nexval': Tuesday->Wednesday}
{'dataval': 'Tuesday', 'nextval': Wednesday}
{'dataval': 'Wednesday', 'nextval': None}

Monday is still pointing at Wednesday even though we definitely set nexval to Tuesday. Wait, Monday also has 'nexval' to Tuesday, and 'nextval' to Wednesday ... TYPO!!! nexval and nextval are completely different!

Oh yeah, my prints have that output because I added this to class node:

def __repr__(self):
    if self.nextval:
        return self.dataval + '->' + self.nextval.dataval
    return self.dataval

Upvotes: 0

foo-bar
foo-bar

Reputation: 231

You have a typo, see the #TODO below in the method addBefore:

    def addBefore(self, valueToFind, newNode):
    currentNode = self.headval
    previousNode = None
    while currentNode is not None:
        # We found the element we will insert before
        if (currentNode.dataval == valueToFind):
            # Set our new node's next value to the current element
            newNode.nextval = currentNode

            # If we are inserting at the head position
            if (previousNode is None):
                self.headval = newNode
            else:
                # Change previous node's next to our new node
                previousNode.nexval = newNode #TODO: Fix Typo: nexval
                return 0

        # Update loop variables
        previousNode = currentNode
        currentNode = currentNode.nextval
    return -1

Upvotes: 0

cool
cool

Reputation: 375

Hope this helps

def addBefore(self, valueToFind, newNode):
        currentNode = self.headval # point to headval
        previousNode = None 
        while currentNode.data != valueToFind: # while currentNode.data is not equal to valueToFind, move currentNode to next node and keep track of previous node i.e. previousNode
            previousNode = currentNode # keep tack of previous node
            currentNode = currentNode.nextval # move to next node

        previousNode.nextval = newNode # previous node will point to new node
        previousNode = previousNode.nextval # move previous node to newly inserted node
        previousNode.nextval = currentNode # previous node ka next will to currentNode

Upvotes: 0

Related Questions