*** 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()
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!
LikeLike
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.
LikeLike
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.
LikeLike
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
LikeLike
Thanks đŸ™‚ I am merely using wordpress’ default host
LikeLike