"""Linear Linked List
Included:
- put
- sort
- delete
- find
- display
"""
# Linear Linked List
class Node:
def __init__(self, val, next_=None):
self.val = val
self.next = next_
class LLL:
def __init__(self, start=None):
self.head = self.tail = start
def empty(self):
return self.head is None
def put(self, data):
# Create a new node
new_node = Node(data)
# Empty: assign head and tail to new node
if self.empty():
self.head = self.tail = new_node
else:
# Not Empty: new node added after tail, becomes new tail
self.tail.next = new_node
self.tail = new_node
def sort_it(self):
if self.empty():
return
# Bubblesort
curr = self.head
while curr:
temp = curr.next
while temp:
if curr.val > temp.val:
curr.val, temp.val = temp.val, curr.val
temp = temp.next
curr = curr.next
def delete(self, val):
if self.empty():
return f"Empty!"
curr, prev = self.head, None
# Update curr and prev until find item
while curr and val > curr.val:
prev, curr = curr, curr.next
# Found
if curr and val == curr.val:
if curr == self.head:
self.head = self.head.next
else:
prev.next = curr.next
return f"Del: {val}"
# Not found
return f"No: {val}"
def find(self, val):
curr = self.head
# Update curr until item found
while curr and val > curr.val:
curr = curr.next
# Found
if curr and val == curr.val:
return True
# Not found
return False
def size(self):
count = 0
curr = self.head
# Loop through all nodes and count
while curr:
count += 1
curr = curr.next
return count
def display(self):
nodes = []
curr = self.head
# Loop through all filled nodes
while curr:
nodes.append(curr.val)
curr = curr.next
return nodes
# Test
from random import randint
def LLL_Test(LLL):
# Create random lists
r = randint(15, 20)
test = [randint(10, 100) for _ in range(r)]
a, b = len(test) // 3, -3
notinlst, inlst, after_empty = test[:a], test[a:b], test[b:]
print(f"test: {test}",
f"notinlst: {notinlst}",
f"inlst: {inlst}",
f"after_empty: {after_empty}",
sep = "
", end = "
")
# Create empty LLL
LLL = LLL()
# Put items from inlst into LLL, and sort LLL
for num in inlst:
LLL.put(num)
LLL.sort_it()
print(f"Size: {LLL.size()}",
f"Data ( ): ",
f" ",
f"LLL: {LLL.display()}",
f"{LLL.display() == sorted(inlst)}",
sep = " | ", end = "
")
## Test notinlst
print("notinlst:")
for num in notinlst:
print(f"Size: {LLL.size()}",
f"Data ({num}): {LLL.find(num)}",
f"{LLL.delete(num)}",
f"LLL: {LLL.display()}",
sep = " | ")
print()
# Test inlst
print("inlst:")
for num in inlst:
print(f"Size: {LLL.size()}",
f"Data ({num}): {LLL.find(num)}",
f"{LLL.delete(num)}",
f"LLL: {LLL.display()}",
sep = " | ")
print()
# Test after_empty
print("after_empty:")
for num in after_empty:
print(f"Size: {LLL.size()}",
f"Data ({num}): {LLL.find(num)}",
f"{LLL.delete(num)}",
f"LLL: {LLL.display()}",
sep = " | ")
LLL_Test(LLL)