"""
Implementation of LinkedList Datastructure in Python
"""
class Node:
"""
init() : constructor
"""
def __init__(self, data = None, next = None):
self.data = data
self.next = next
"""
getData() : get the data of node;
"""
def getData(self):
return self.data
"""
setData() : set the data to the required node;
"""
def setData(self,data):
self.data = data
class LinkedList:
"""
init() : constructor;
"""
def __init__(self, head = None):
self.head = None
"""
len() : return the length of the nodes;
"""
def __len__(self):
if(self.head == None):
return 0
else:
count = 0
node = self.head
while(node != None):
node = node.next
count += 1
return count
"""
getItem() : return the specific index node from linked list;
"""
def __getitem__(self, index):
return self.head[index]
"""
print() : list all nodes of linked list
"""
def show(self):
node = self.head
while(node.next != None):
print(node.data, end=" -> ")
node = node.next
print(node.data)
"""
pushFront() : push elements from front;
eg, A <- B <- C <- D <- E
"""
def pushFront(self, data):
newNode = Node(data)
if(self.head == None):
self.head = newNode
else:
prevHead = self.head
self.head = newNode
newNode.next = prevHead
"""
pushBack() : push elements from the end;
eg, A -> B -> C -> D -> E
"""
def pushBack(self, data):
newNode = Node(data)
if self.head == None:
self.head = newNode
else:
temp = self.head
while(temp.next != None):
temp = temp.next
temp.next = newNode
"""
remove() : remove node for specific index;
eg,
Input : HEAD -> A -> B -> C -> None, index : 2
Output : HEAD -> A -> C -> None
"""
def remove(self, index):
if(self.head == None):
return None
else:
i, size = 1, len(self)
# Index > Size;
if(index > size):
index = index % size
# Base Case;
if(index == 1):
self.head = self.head.next
return
# Main Case;
# Step 1 : Go to one node before end;
while(i < index-1):
node = node.next
i += 1
# Step 2 : Removal of Specific node
if(node.next and node.next.next):
temp = node.next
node.next = node.next.next
del temp # Free-Up Memory
else:
node.next = None
"""
pop() : remove node from end;
eg,
Input : A -> B -> C
Output :A -> B -> None
"""
def pop(self):
if(self.head == None):
return
else:
node = self.head
prevNode = None
# Step 1 : Go to one node before end;
while(node.next != None):
prevNode = node
node = node.next
# Step 2 : Reset the last node;
prevNode.next = None
del node # Delete last node;
"""
reverse() : reverse the linked list;
eg,
Input : HEAD -> A -> B -> C -> None
Output : A <- B <- C <- HEAD
"""
def reverse(self):
if(self.head == None):
return
else:
node = self.head
prevNode = None
# Step 1 : Reverse Links;
while(node != None):
temp = node.next
node.next = prevNode
prevNode = node
node = temp
# Step 2 : Change Head;
if(temp == None):
self.head = prevNode
return self.head
"""
linked list
"""
#creating a class of node and creating contents
class Node:
def __init__(self, contents, next_node=None):
self.contents = contents
self.next = next_node
def __repr__(self):
return f"This node contains {str(self.contents)}."
# creating the linked list class
class LinkedList:
#creates data as an empty array
def __init__(self, data=[]):
self.head = None
if data:
self._init_from_data(data)
#creating data for the linked list
def _init_from_data(self, data):
previous_node = None
for datum in data:
new_node = Node(datum)
if not self.head:
self.head = new_node
else:
previous_node.next = new_node
previous_node = new_node
#
def _get_tail(self):
current_node = self.head
while current_node and current_node.next:
current_node = current_node.next
return current_node
def append_left(self, datum):
new_node = Node(datum, self.head)
self.head = new_node
def append_right(self, datum):
if self.head:
tail_node = self._get_tail()
tail_node.next = Node(datum)
else:
self.head = Node(datum)
def pop_left(self):
old_head = self.head
new_head = old_head.next
self.head = new_head
return old_head
def pop_right(self):
previous_node = None
current_node = self.head
while current_node and current_node.next:
previous_node = current_node
current_node = current_node.next
if previous_node:
previous_node.next = None
else:
self.head = None
return current_node
def __repr__(self):
current_node = self.head
nodes_contents = []
while current_node:
nodes_contents.append(current_node.contents)
current_node = current_node.next
nodes_contents.append("None")
return " >>> ".join(nodes_contents)
def reverse(self):
if(self.head == None):
return
else:
node = self.head
previous_node = None
# Step 1 : Reverse Links;
while(node != None):
temp = node.next
node.next = previous_node
previous_node = node
node = temp
# Step 2 : Change Head;
if(temp == None):
self.head = previous_node
return self.head
empty_list = LinkedList()
linked_list = LinkedList(["a","b","c"])
linked_list.append_left('aa')
linked_list.append_right('cc')
print(linked_list)
linked_list.pop_right()
print(linked_list)
linked_list.pop_left()
print(linked_list)
linked_list.reverse()
print(linked_list)
"""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)