4

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.

2
  • There is no next in node. There is next_node and you don't need a main function in python like in C. Commented Mar 9, 2014 at 16:18
  • which book are you working off of? this feels like straight out of Problem Solving with Algorithms and Data Structures with Python by David Ranum and Brad Miller. I'm working on that too and the example looks way too similar Commented Oct 24, 2020 at 4:50

4 Answers 4

5

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)
Sign up to request clarification or add additional context in comments.

1 Comment

Your implementation of index requires that the index is specified when creating the node, right? If that's the case, wouldn't that defeat the purpose of an index method? If you are providing the index when creating the node, why would you want to ask for the index?
2

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()

2 Comments

for index do we need to assing the pos value as we go, or is there a way that we can add it to the Node itself and then just retrieve that value when we look for it? Would there be any advantage to that? I feel like there wouldn't since we are already doing the work of traversing the list and we will get O(n) complexity, but it'd be nice if we could just add an index to the Node beforehand.
My append method for constant time is def append(self, item): new_node = Node(item) if self.head == None: self.head = new_node self.tail = new_node else: self.tail.set_next(new_node) but it doesn't work. I think we have the same basic idea for it, but why is mine not working?
1
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

Comments

0

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.