CIE Computer Science Linked List Code

*** This is a slightly modified python code from the Cambridge coursebook as the pseudo code provided by the book does not work ***

class ListNode:
    def __init__(self): # object for each node
        self.Data = 0
        self.Pointer = 0
        
class LinkedList:
    def __init__(self,n): # initialisation
        self.__NULLPOINTER = -1
        self.__StartPointer = self.__NULLPOINTER
        self.__FreeListPointer = 0
        self.List = []
        for i in range(n):
            self.List.append(ListNode())
            self.List[i].Pointer = i+1
        self.List[n-1].Pointer = self.__NULLPOINTER

    def display(self): # print a display in order of index position
        print("Start Pointer:", self.__StartPointer)
        print("Free List Pointer:", self.__FreeListPointer)
        print("|{0:^5}|{1:^10}|{2:^10}|".format("Pos", "Data", "Pointer"))
        for i in range(len(self.List)):
            print("|{0:^5}|{1:^10}|{2:^10}|".format(i, self.List[i].Data, self.List[i].Pointer))

    def insert(self,item): # insert item, returns True when inserted and False when set is full
        if self.__FreeListPointer != self.__NULLPOINTER:
            NewNodePointer = self.__FreeListPointer
            self.List[self.__FreeListPointer].Data = item
            self.__FreeListPointer = self.List[self.__FreeListPointer].Pointer
            PreviousPointer = self.__StartPointer
            ThisPointer = self.__StartPointer
            if self.__StartPointer == self.__NULLPOINTER or item < self.List[ThisPointer].Data:
                ThisPointer = self.__StartPointer
                self.List[NewNodePointer].Pointer = ThisPointer
                self.__StartPointer = NewNodePointer
            else:
                HasRun = False
                while self.List[ThisPointer].Data < item and ThisPointer != self.__NULLPOINTER:
                    PreviousPointer = ThisPointer
                    ThisPointer = self.List[ThisPointer].Pointer
                    HasRun = True
                if HasRun:
                    self.List[NewNodePointer].Pointer = self.List[PreviousPointer].Pointer
                    self.List[PreviousPointer].Pointer = NewNodePointer
            return True
        else:
            return False

    def delete(self, item): # delete an item, returns True when deleted and False when not found or set empty
        if self.__StartPointer == self.__NULLPOINTER:
            return False
        if self.List[self.__StartPointer].Data == item:
            self.List[self.__StartPointer].Data = 0
            temp = self.List[self.__StartPointer].Pointer
            self.List[self.__StartPointer].Pointer = self.__FreeListPointer
            self.__FreeListPointer = self.__StartPointer
            self.__StartPointer = temp
        else:
            CurrentNodePtr = self.__StartPointer
            PreviousPtr = -1
            while CurrentNodePtr != self.__NULLPOINTER and self.List[CurrentNodePtr].Data != item:
                PreviousPtr = CurrentNodePtr
                CurrentNodePtr = self.List[CurrentNodePtr].Pointer
            if CurrentNodePtr == self.__NULLPOINTER and self.List[CurrentNodePtr].Data != item:
                return False
            self.List[PreviousPtr].Pointer = self.List[CurrentNodePtr].Pointer
            self.List[CurrentNodePtr].Data = 0
            self.List[CurrentNodePtr].Pointer = self.__FreeListPointer
            self.__FreeListPointer = CurrentNodePtr
            return True

    def find(self, item): # return position of an item, -1 if not found
        CurrentNodePtr = self.__StartPointer
        while CurrentNodePtr != self.__NULLPOINTER and self.List[CurrentNodePtr].Data != item:
            CurrentNodePtr = self.List[CurrentNodePtr].Pointer
        return CurrentNodePtr

    def access(self): # print a display in order of pointers
        CurrentNodePtr = self.__StartPointer
        print("|{0:^10}|{1:^5}|".format("Data","Pos"))
        while CurrentNodePtr != self.__NULLPOINTER:
            print("|{0:^10}|{1:^5}|".format(self.List[CurrentNodePtr].Data, self.List.index(self.List[CurrentNodePtr])))
            CurrentNodePtr = self.List[CurrentNodePtr].Pointer
                    
                
########################
### Example Commands ###
########################

MyLinkList = LinkedList(7)
MyLinkList.display()
MyLinkList.insert(40)
MyLinkList.insert(50)
MyLinkList.insert(10)
MyLinkList.insert(30)
MyLinkList.insert(60)
MyLinkList.insert(70)
MyLinkList.insert(80)
MyLinkList.display()
MyLinkList.access()
MyLinkList.delete(10)
MyLinkList.delete(10)
MyLinkList.delete(30)
MyLinkList.delete(80)
MyLinkList.display()
print("Item found at position", MyLinkList.find(40))
MyLinkList.access()

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s