Question

How do you write an append function for a linked list that is a that has a O(1) Big O notation in Python? The one given in class is O(n). He recommended using a variable to track the end the list. This is the code I have written so far. I don't think I'm properly defining the tail in the add possibly

class Node:

    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next

class UnorderedList:

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


    def is_empty(self):
        return self.head == None

    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        if self.size()>1:
            self.tail = self.head
            self.head = temp
        else:
            self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.get_next()
        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.get_data() == item:
                found = True
            else:
                current = current.get_next()
        return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while current != None and not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()
        if found and previous != None:
            previous.set_next(current.get_next())
        elif found and previous is None:
            self.head = None
        else:
            print("The item is not in list")
        return found



    def append(self, data):
        last = self.tail
        print(last2)
        temp = Node(data)
        last.set_next(temp)
        tail = temp

myList = UnorderedList()
myList.add(31)
myList.add(99)
print(myList.size())
myList.add(45)
myList.add(80)
print(myList.size())
myList.append((100))
print(myList.size())

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

#code

class Node:

    def __init__(self, init_data):
        self.data = init_data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next

class UnorderedList:

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


    def is_empty(self):
        return self.head == None

    #adds an element at the beginning
    def add(self, item):
        temp = Node(item)
        #if list is empty, adding temp as both head and tail
        if self.head==None:
            self.head = temp
            self.tail= temp
        else:
            #or adding before head node, and updating head node
            temp.set_next(self.head)
            self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.get_next()
        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.get_data() == item:
                found = True
            else:
              current = current.get_next()
        return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while current != None and not found:
            if current.get_data() == item:
              found = True
            else:
                previous = current
                current = current.get_next()
        if found and previous != None:
            previous.set_next(current.get_next())
            #if current.get_next() is None, updating tail node to be previous
            if current.get_next()==None:
                self.tail=previous
        elif found and previous is None:
            self.head = self.head.get_next()
            #if head node became None, setting tail to None
            if self.head==None:
                self.tail=None
        else:
            print("The item is not in list")
        return found


    #adds an element at the end
    def append(self, data):
        #creating a Node
        node=Node(data)
        #if self.head is None (list is empty), adding node as both head and tail
        if self.head==None:
            self.head=node
            self.tail=node
        else:
            #appending after tail
            self.tail.set_next(node)
            #updating tail
            self.tail=self.tail.get_next()

    #a helper method to print the list elements for testing
    def print_list(self):
        node=self.head
        while node!=None:
            print(node.get_data(),end=' ')
            node=node.get_next()
        print()

myList = UnorderedList()
myList.add(31)
myList.add(99)
print(myList.size())
myList.add(45)
myList.add(80)
print(myList.size())
myList.print_list() #80 45 99 31
myList.append((100))
print(myList.size())
myList.print_list() #80 45 99 31 100

#output

2

4

80 45 99 31

5

80 45 99 31 100