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

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.

## Answers

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)

def insert(self,item,position): if position==0: self.add(item) elif position>self.size(): print("Position index is out of range") elif position==self.size(): self.append(item) else: temp=Node.Node(item,position) current=self.head previous=None current_position=0 while current_position!=position: previous=current current=current.next current_position+=1 previous.next=temp temp.next=current

Below is the implementation that I could come up with (tested and working). It seems to be an old post, but I couldn't find the complete solution for this anywhere, so posting it here.

# add -- O(1) # size -- O(1) & O(n) # append -- O(1) & O(n) # search -- O(n) # remove -- O(n) # index -- O(n) # insert -- O(n) # pop -- O(n) # can be O(1) if we use doubly linked list # pop(k) -- O(k) class Node: def __init__(self, initdata): self.data = initdata self.next = None def getData(self): return self.data def getNext(self): return self.next def setNext(self, newnext): self.next = newnext class UnorderedList: def __init__(self): self.head = None self.tail = None self.length = 0 def isEmpty(self): return self.head is None def add(self, item): temp = Node(item) temp.setNext(self.head) self.head = temp if self.tail is None: self.tail = temp self.length += 1 def ssize(self): # This is O(n) current = self.head count = 0 while current is not None: count += 1 current = current.getNext() return count def size(self): # This is O(1) return self.length def search(self, item): current = self.head found = False while current is not None and not found: if current.getData() == item: found = True else: current = current.getNext() return found def remove(self,item): current = self.head previous = None found = False while current is not None and not found: if current.getData() == item: found = True else: previous = current current = current.getNext() if previous == None: # The item is the 1st item self.head = current.getNext() else: if current.getNext() is None: self.tail = previous # in case the current tail is removed previous.setNext(current.getNext()) self.length -= 1 def __str__(self): current = self.head string = '[' while current is not None: string += str(current.getData()) if current.getNext() is not None: string += ', ' current = current.getNext() string += ']' return string def sappend(self, item): # This is O(n) time complexity current = self.head if current: while current.getNext() is not None: current = current.getNext() current.setNext(Node(item)) else: self.head = Node(item) def append(self, item): # This is O(1) time complexity temp = Node(item) last = self.tail if last: last.setNext(temp) else: self.head = temp self.tail = temp self.length += 1 def insert(self, index, item): temp = Node(item) current = self.head previous = None count = 0 found = False if index > self.length-1: raise IndexError('List Index Out Of Range') while current is not None and not found: if count == index: found = True else: previous = current current = current.getNext() count += 1 if previous is None: temp.setNext(self.head) self.head = temp else: temp.setNext(current) previous.setNext(temp) self.length += 1 def index(self, item): pos = 0 current = self.head found = False while current is not None and not found: if current.getData() == item: found = True else: current = current.getNext() pos += 1 if not found: raise ValueError('Value not present in the List') return pos def pop(self, index=None): if index is None: index = self.length-1 if index > self.length-1: raise IndexError('List Index Out Of Range') current = self.head previous = None found = False if current: count = 0 while current.getNext() is not None and not found: if count == index: found = True else: previous = current current = current.getNext() count += 1 if previous is None: self.head = current.getNext() if current.getNext() is None: self.tail = current.getNext() else: self.tail = previous previous.setNext(current.getNext()) self.length -= 1 return current.getData()

Notice that in the Node class you defined the "next" field as "next_node". Therefore the interpreter doesn't know "next". So, instead of node.next it should be node.next_node