*** 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()