Linked List in Python- Append, Index, Insert, and Pop functions. Not sure with code/errors

Question

This assignment asks us to implement the append, insert, index and pop methods for an unordered linked-list. (What I have so far)

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def AppendNode(self, data):
        new_node = Node(data)

        if self.head == None:
            self.head = new_node

        if self.tail != None:
            self.tail.next = new_node

        self.tail = new_node
    def PrintList( self ):
        node = self.head

        while node != None:
            print (node.data)
            node = node.next

    def PopNode( self, index ):
        prev = None
        node = self.head
        i = 0

        while ( node != None ) and ( i < index ):
            prev = node
            node = node.next
            i += 1

        if prev == None:
            self.head = node.next
        else:
            prev.next = node.next

list = LinkedList()
list.AppendNode(1)
list.AppendNode(2)
list.AppendNode(3)
list.AppendNode(4)
list.PopNode(0)
list.PrintList( )

The output so far:

    2
    3
    4
    Traceback (most recent call last):
      File "<pyshell#32>", line 1, in <module>
        main()
      File "<pyshell#31>", line 50, in main
        list.PrintList( )
      File "<pyshell#31>", line 27, in PrintList
        node = node.next
    AttributeError: 'Node' object has no attribute 'next'

I'm not sure why i'm getting the errors, since the code is technically working. Also any input on the insert, and index functions would be greatly appreciated.

Answer 1

For insert and index methods you will need another Node attribute, because you'll need to keep track of which item is on what position. Let we call it position. Your Node class will now look like this:

class Node:
    def __init__(self, data, position = 0):
        self.data = data
        self.next_node = None
        self.position = position

Retrieving index value now is easy as:

def index(self,item):
    current = self.head
    while current != None:
        if current.data == item:
            return current.position
        else:
            current = current.next
    print ("item not present in list")

As for the list-altering methods, I would start with a simple add method which adds items to the leftmost position in the list:

def add(self,item):
        temp = Node(item)           #create a new node with the `item` value
        temp.next = self.head     #putting this new node as the first (leftmost) item in a list is a two-step process. First step is to point the new node to the old first (lefmost) value
        self.head = temp            #and second is to set `LinkedList` `head` attribute to point at the new node. Done!
        current = self.head         #now we need to correct position values of all items. We start by assigning `current` to the head of the list
        self.index_correct(current) #and we'll write helper `index_correct` method to do the actual work.
        current = self.head
        previous = None
        while current.position != self.size() - 1:
             previous = current
             current = current.next
             current.back = previous
        self.tail = current

What shall the index_correct method do? Just one thing - to traverse the list in order to correct index position of items, when we add new items (for example: add, insert etc.), or remove them (remove, pop, etc.). So here's what it should look like:

def index_correct(self, value):
    position = 0
    while value != None:
        value.position = position
        position += 1
        value = value.next

It is plain simple. Now, let's implement insert method, as you requested:

def insert(self,item,position):
    if position == 0:
        self.add(item)
    elif position > self.size():
        print("position index out of range")
    elif position == self.size():
        self.AppendNode(item)
    else:
        temp = Node(item, position)
        current = self.head
        previous = None
        while current.position != position:
            previous = current
            current = current.next
        previous.next = temp
        temp.next = current
        temp.back = previous
        current.back = temp
        current = self.head
        self.index_correct(current)