linked list implementation and functions
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def print_list(self):
cur_node = self.head
while cur_node:
print(cur_node.data)
cur_node = cur_node.next
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_after_node(self, prev_node, data):
if not prev_node:
print("Previous node does not exist.")
return
new_node = Node(data)
new_node.next = prev_node.next
prev_node.next = new_node
def delete_node(self, key):
cur_node = self.head
if cur_node and cur_node.data == key:
self.head = cur_node.next
cur_node = None
return
prev = None
while cur_node and cur_node.data != key:
prev = cur_node
cur_node = cur_node.next
if cur_node is None:
return
prev.next = cur_node.next
cur_node = None
def delete_node_at_pos(self, pos):
if self.head:
cur_node = self.head
if pos == 0:
self.head = cur_node.next
cur_node = None
return
prev = None
count = 1
while cur_node and count != pos:
prev = cur_node
cur_node = cur_node.next
count += 1
if cur_node is None:
return
prev.next = cur_node.next
cur_node = None
def len_iterative(self):
count = 0
cur_node = self.head
while cur_node:
count += 1
cur_node = cur_node.next
return count
def len_recursive(self, node):
if node is None:
return 0
return 1 + self.len_recursive(node.next)
def print_helper(self, node, name):
if node is None:
print(name + ": None")
else:
print(name + ":" + node.data)
def reverse_iterative(self):
prev = None
cur = self.head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
self.head = prev
def reverse_recursive(self):
def _reverse_recursive(cur, prev):
if not cur:
return prev
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return _reverse_recursive(cur, prev)
self.head = _reverse_recursive(cur=self.head, prev=None)