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[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
                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
            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
            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
        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)
print("Item found at position", MyLinkList.find(40))


5 thoughts on “CIE Computer Science Linked List Code

  1. You actually make it appear so easy along with your presentation however I in finding this topic to be actually something that I think I would by no means understand. It seems too complicated and very huge for me. I am having a look forward in your next submit, I will try to get the dangle of it!


  2. I’m no longer certain where you are getting your info, but great topic. I must spend some time finding out more or working out more. Thank you for magnificent information I used to be on the lookout for this information for my mission.


    1. Hi Alex! Are you an A-Level student or just a programming learner? I was studying Computer Science as an A-Level course and the section on Linked List provided a massively flawed code example. So I wrote out a corrected and working example, primarily for students of this curriculum.


  3. Excellent weblog here! Additionally your web site lots up fast! What host are you using? Can I get your affiliate hyperlink on your host? I wish my web site loaded up as fast as yours lol


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s