UnOrdered Linked list – Prepend, Append, Insert At, Reverse, Remove, Search

In order to implement an unordered linked list we need to construct linked list which contains Node class, a building block for constructing linked list

Linked List

class Node(object):
    def __init__(self, item):
        self.data = item
        self.next = None
    
    def setNext(self, newnext):
        self.next = newnext
    
    def getNext(self):
        return self.next
    
    def setData(self, item):
        self.data = item
    
    def getData(self):
        return self.data


class UnOrderedLinkedList(object):
    
    def __init__(self):
        self.head = None
        self.tail = None
    
    def prepend(self, data):
        n = Node(data)
        n.setNext(self.head)
        self.head = n
        if n.getNext() == None:
            self.tail = n
    
    def append(self, data):
        n = Node(data)
        self.tail.setNext(n)
        self.tail = n
    
    def insertAfter(self, item, data):
        n = Node(data)
        found = False
        current = self.head
        while not found:
            if current.getData() == item:
                n.setNext(current.getNext())
                current.setNext(n)
                found = True
            else:
                current = current.getNext()
                
    def search(self, item):
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

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

    def remove(self, item):
        current = self.head
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

    def printList(self):
        current = self.head
        while current != None:
            print current.getData() , 'n|'
            current = current.getNext()

    def reverse(self):
        current = self.head
        previous = None
        while current:
            next = current.getNext()
            current.setNext(previous)
            previous = current
            current = next
        self.head = previous
        return self.printList()