Implementing an insert method on a linked list on python

Question

Attempting to create a method for a singly linked list and struggling to understand why this test case is failing. In my second class SLinkedList, I have a method called insert, it takes the argument pos which is an integer. Now in my test case when I add middle to position 4 it stops referencing any further nodes the linked list meaning that the node containing the data middle does not have a reference to the node containing 77. I'm confused why this is happening? I've programmed it such that when current_pos==pos we set the next of our current (new_node) to be current.getNext() (77). Haven't I assigned the next of 2 to middle and the next of middle to 77?

class SLinkedListNode:
    # an instance of this class is a node in a Single Linked List
    # a node has a reference to data and reference to next
    def __init__(self,initData,initNext):
        self.data = initData
        self.next = initNext

    def getNext(self):
        return self.next

    def getData(self):
        return self.data

    def setData(self,newData):
        self.data = newData

    def setNext(self,newNext):
        self.next = newNext


class SLinkedList:
    # an instance of this class is a Singly-Linked List object
    # it has reference to the first node in the list
    def __init__(self):
        self.head = None
        self.size = 0

    def add(self,item):
        # adds an item at the start of the list
        new_node = SLinkedListNode(item,None)
        new_node.setNext(self.head)
        self.head = new_node
        self.size = self.size + 1

    def append(self,item):
        # adds an item at the end of the list
        new_node = SLinkedListNode(item,None)
        current = self.head # Start the traversal
        if self.size == 0: # check if list is empty
            self.add(item)
        else:
            while (current.getNext()!=None):
                current= current.getNext() # traversing the list
            current.setNext(new_node)
            self.size = self.size +1


    def insert(self,pos,item):
        # inserts the item at pos
        # pos should be a positive number (or zero) of type int
        assert type(pos)==int,'Error:pos is not an integer'
        assert pos>=0,'Error:pos must be positive'
        current=self.head
        new_node= SLinkedListNode(item,None)    
        if pos==0:
            self.add(item)
        elif pos==self.size:
            self.append(item)
        else:
            current_pos=0
            while(current.getNext()!=None):


                if (pos-1)==current_pos:
                    print(current.getData())
                    current.setNext(new_node)

                if pos==current_pos:
                    print(current.getData())

                    new_node.setNext(current.getNext())    
                current=current.getNext()


                current_pos+=1
            self.size+=1



   # 1--> 2--->inserteditem---> 3-->4---> 5---> 6             





        # TO DO: write assert statement that tests if pos is int
        # TO DO: write assert statement that tests that pos is not negative
        # TO DO: COMPLETE THE METHOD 



    def remove(self,item):
        # remove the node containing the item from the list
        if self.size == 0:
            raise Exception('List is Empty')
        current = self.head
        previous = None
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if not found:
            raise Exception('Item not in list')
        else:
            if previous == None: # the item is in the first node of the list
                self.head = current.getNext()
            else: # item is not in the first node
                previous.setNext(current.getNext())
            self.size = self.size -1

    def index(self,item):
        # finds the location of the item in the list
        if self.size == 0:
            raise Exception('List is empty')
        position = 0
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                position = position + 1
        if found:
            return position
        else:
            return 'Item not found'

    def pop(self):
        # removes the node from the end of the list and returns the item 
        if self.size == 0:
            raise Exception('List is empty')
        current = self.head
        previous = None
        while current.getNext() != None:
            previous = current
            current = current.getNext()
        if previous == None:
            self.head = None
        else:
            previous.setNext(None)
        self.size = self.size -1
        return current.getData()

    def __str__(self):
        # returns a string representation of the list
        current = self.head
        string = ''
        while current != None:
            string = string + str(current.getData())+'->'
            current = current.getNext()
        return string

    def getSize(self):
        return self.size


def main():
    # Testing Singly-Linked List
    slist = SLinkedList()
    slist.add(2)
    slist.add(4)
    slist.add('A')
    slist.append(77)
    slist.append(6)
    slist.append('Z')
    print('Original List:', slist.getSize(), 'elements')
    print(slist)
    print()
    slist.insert(0,'start')
    print('After inserting the word start at position 0:', slist.getSize(), 'elements')
    print(slist)
    print()
    slist.insert(7,'end')
    print('After inserting the word end at position 7:', slist.getSize(), 'elements')
    print(slist)
    print()
    slist.insert(4,'middle')
    print('After inserting middle at position 4:', slist.getSize(), 'elements')
    print(slist)

if __name__=="__main__":
    main()

Answer 1

Take a look at this code snippet from your insert-method:

else:
    current_pos=0
    while(current.getNext()!=None):
        if (pos-1)==current_pos:
            print(current.getData())
            current.setNext(new_node)

        if pos==current_pos:
            new_node.setNext(current.getNext())    

        current=current.getNext()
        current_pos+=1

Once the first if-condition is met, you're setting your new node as the current node's next node. Bear in mind, this new node has no reference to the rest of the list. The second if statement will not execute during this iteration, so the next line to be executed is current=current.getNext(), which sets current to be your new node, still without reference to the rest of the list. Therefore, in the next iteration of the while loop current.getNext() evaluates to None and your iteration terminates right then and there, effectively removing all nodes after your new node from the list.

To fix this, remove the second if and set the new node's next node in the previous if statement. This way, you'll maintain the reference to the rest of the list.

---

On a side note, get- and set-methods are very unpythonic, you can access and modify these attributes directly, e.g. by using current.next = whatever. Also, a while-loop iterating over your entire list seems fairly inefficient for the insert task since you exactly know the index to insert the new node into. Also also, your insert-method will break for positions greater than the list's length, you might want to add another check for that