Skip to content

Instantly share code, notes, and snippets.

@zeyu2001
Created September 27, 2019 10:02
Show Gist options
  • Save zeyu2001/012b730764db211138f60b0c1f351380 to your computer and use it in GitHub Desktop.
Save zeyu2001/012b730764db211138f60b0c1f351380 to your computer and use it in GitHub Desktop.
Linked List OOP Implementation in Python (with array)
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