Created
September 27, 2019 10:02
-
-
Save zeyu2001/012b730764db211138f60b0c1f351380 to your computer and use it in GitHub Desktop.
Linked List OOP Implementation in Python (with array)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class ListNode: | |
def __init__(self): | |
self._Name = None | |
self._Pointer = None | |
def SetName(self, Name): | |
self._Name = Name | |
def SetPointer(self, Pointer): | |
self._Pointer = Pointer | |
def GetName(self): | |
return self._Name | |
def GetPointer(self): | |
return self._Pointer | |
class LinkedList: | |
def __init__(self): | |
self._Node = None | |
self._Start = None | |
self._NextFree = None | |
def Create(self): | |
# index starts from 0 | |
# -1 means invalid index | |
self._Node = [ListNode() for i in range(10)] | |
for i in range(9): | |
self._Node[i].SetPointer(i + 1) | |
self._Node[9].SetPointer(-1) | |
self._Start = -1 | |
self._NextFree = 0 | |
def Insert(self, name, position): | |
# create new node | |
NewNodePtr = self._NextFree | |
self._NextFree = self._Node[self._NextFree].GetPointer() | |
self._Node[NewNodePtr].SetPointer(-1) | |
self._Node[NewNodePtr].SetName(name) | |
def helper(currPtr, currPos, pos): | |
# reached end of list, add to back of list | |
if currPtr == -1: | |
return NewNodePtr | |
# position found | |
elif currPos == pos: | |
self._Node[NewNodePtr].SetPointer(currPtr) | |
return NewNodePtr | |
# keep traversing until position found | |
else: | |
self._Node[currPtr].SetPointer(helper(self._Node[currPtr].GetPointer(),\ | |
currPos + 1, pos)) | |
return currPtr | |
self._Start = helper(self._Start, 1, position) | |
def Delete(self, position): | |
def helper(currPtr, currPos, pos): | |
if currPos == pos: | |
# return node to front of NextFree linked list | |
NextPtr = self._Node[currPtr].GetPointer() | |
self._Node[currPtr].SetPointer(self._NextFree) | |
self._Node[currPtr].SetName(None) | |
self._NextFree = currPtr | |
return NextPtr | |
else: | |
self._Node[currPtr].SetPointer(helper(self._Node[currPtr].GetPointer(),\ | |
currPos + 1, pos)) | |
return currPtr | |
self._Start = helper(self._Start, 1, position) | |
def Length(self): | |
count = 0 | |
currPtr = self._Start | |
while currPtr != -1: | |
count += 1 | |
currPtr = self._Node[currPtr].GetPointer() | |
return count | |
def IsEmpty(self): | |
return self._Start == -1 | |
def isFull(self): | |
return self._NextFree == -1 | |
def Display(self): | |
print('Start: {}'.format(self._Start)) | |
print('NextFree: {}'.format(self._NextFree)) | |
for i in range(len(self._Node)): | |
print('Index {}: {}, Pointer {}'.format(i, self._Node[i].GetName(),\ | |
self._Node[i].GetPointer())) | |
def main(): | |
ll = LinkedList() | |
ll.Create() | |
ll.Insert('Ali', 1) | |
ll.Insert('Jack', 1) | |
ll.Insert('Ben',2) | |
ll.Delete(1) | |
ll.Insert('Jane', 2) | |
ll.Insert('Ken', 3) | |
ll.Delete(2) | |
ll.Display() | |
# main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment