ADT COMPILED REVISION
LINKED LIST AND NODE
Creating Nodes
class Node:
def __init__(self, data, next= None):
self.data = data
self.next = next
def __str__(self):
state = f"Node: {self.data}"
if self.next:
state += f", Next: {self.next.data}"
else:
state += ", Next: None"
return(state)How Nodes are related to Linked Lists
Nodes show the current data and next data.
When being used in a linked list, the newest node is on the left, oldest on the right.
When using the code:
x = Node(1)
x = Node(2, x)
x = Node(3, x)
This creates a linked list that is like:
3 -> 2 -> 1 -> None
Hence, when removing first, we are removing 3.
Removing last, we remove 1. Node 2 now points to None.
Linked List Code
class LinkedList():
def __init__(self):
self.head = None
def create(self):
for i in range(5):
self.head = Node(str(i), self.head)
# this creates a linked list of 4 -> 3 -> 2 -> 1 -> 0 -> None
def __str__(self):
probe = self.head
string = ""
while probe != None:
string += probe.__str__() + '\n'
probe = probe.next
return(string)
def insertStart(self, insert):
self.head = Node(insert, self.head)
def insertEnd(self, insertEnd):
probe = self.head
while probe.next != None:
probe = probe.next
probe.next = Node(insertEnd)
def insertAny(self, insertData, index):
probe = self.head
if index == 0:
self.head = Node(insertData, probe)
else:
for i in range(index-1):
probe = probe.next
probe.next = Node(insertData, probe.next)
def find(self, data):
probe = self.head
num = 0
while probe != None:
if probe.data == data:
return(f'Found, index {num}')
probe = probe.next
num += 1
return('Not found')
def removeStart(self):
self.head = self.head.next
def removeEnd(self):
probe = self.head
while probe.next.next != None:
probe = probe.next
probe.next = None
def removeAny(self, index):
if index == 0:
self.head = self.head.next
else:
probe = self.head
for i in range(index -1):
probe = probe.next
probe.next = probe.next.next
x = LinkedList()
x.create()
print('DEFAULT')
print(x)
print('INSERT START')
x.insertStart('hi')
print(x)
print('INSERT END')
x.insertEnd('bye')
print(x)
print('INSERT ANY')
x.insertAny('test',3)
print(x)
print('REMOVE START')
x.removeStart()
print(x)
print('REMOVE END')
x.removeEnd()
print(x)
print('REMOVE ANY')
x.removeAny(2)
print(x)
print(x.find('4'))
# take note: i am taking the first index in the linked list to be 0.Output:
DEFAULT
Node: 4, Next: 3
Node: 3, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: None
INSERT START
Node: hi, Next: 4
Node: 4, Next: 3
Node: 3, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: None
INSERT END
Node: hi, Next: 4
Node: 4, Next: 3
Node: 3, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: bye
Node: bye, Next: None
INSERT ANY
Node: hi, Next: 4
Node: 4, Next: 3
Node: 3, Next: test
Node: test, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: bye
Node: bye, Next: None
REMOVE START
Node: 4, Next: 3
Node: 3, Next: test
Node: test, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: bye
Node: bye, Next: None
REMOVE END
Node: 4, Next: 3
Node: 3, Next: test
Node: test, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: None
REMOVE ANY
Node: 4, Next: 3
Node: 3, Next: 2
Node: 2, Next: 1
Node: 1, Next: 0
Node: 0, Next: None
Found, index 0Stack ADT
Stack is a LAST IN FIRST OUT (LIFO) Data Structure. Imagine that they are layers.
--- top ---
A
B
C
--- bottom ---
HENCE - this means that items POPPED are popped from the top. Items PUSHED are also pushed onto the top.
If you need an analogy: think about the undo function of your keyboard. It undoes starting from the last thing you did. (LIFO)
class LinkedStack():
def __init__(self):
self.top = None
self.size = 0
def __len__(self):
return self.size
def isEmpty(self):
return(len(self) == 0)
def __str__(self):
probe = self.top
string = ''
while probe != None:
string = f"{probe.data} {string}"
# i am defining that the left of the string is bottom
probe = probe.next
return(string)
def push(self, item):
self.top = Node(item, self.top)
self.size += 1
def pop(self):
if self.isEmpty():
return 'Is Empty'
else:
removed = self.top.data
self.top = self.top.next
self.size -= 1
return(f"Removed {removed}")
def peek(self):
if self.isEmpty():
return 'Is Empty'
else:
return self.top.datax = LinkedStack()
x.push('1')
x.push('2')
x.push('3')
print("DEFAULT: (left is bottom, right is top)")
print(x)
print('\nPOP:')
print(x.pop())
print('\nPEEK:')
print(x.peek())
print('\nFULL:')
print(x)Output:
DEFAULT: (left is bottom, right is top)
1 2 3
POP:
Removed 3
PEEK:
2
FULL:
1 2QUEUE ADT
Queue is a FIRST IN FIRST OUT (FIFO) Data Structure. Literally it is like real world queueing. The first data (person) inserted into queue is the first data (person) out.
class LinkedQueue():
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def __str__(self):
probe = self.front
string = ''
while probe != None:
string += f"{probe.data} "
probe = probe.next
return(string)
def __len__(self):
return self.size
def isEmpty(self):
return len(self) == 0
def enqueue(self, data):
newNode = Node(data)
if self.isEmpty():
self.front = newNode
else:
self.rear.next = newNode
self.rear = newNode
self.size += 1
def dequeue(self):
if self.isEmpty():
return 'Queue is emepty'
else:
old = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
self.size -= 1
return oldx = LinkedQueue()
x.enqueue('front')
x.enqueue('2')
x.enqueue('3')
x.enqueue('rear')
print('FULL')
print(x)
print('\nDEQUEUE 1')
print(x.dequeue())
print('\nUPDATED')
print(x)Output:
FULL
front 2 3 rear
DEQUEUE 1
front
UPDATED
2 3 rear