Single Linked List

single_linked_list.py

class Node:
	def __init__(self, data=None, next=None):
		self.data = data
		self.next = next

	def __repr__(self):
		return repr(self.data)


def append(lst, value):
	if not lst:
		return Node(value)

	# Assign be ref
	curr = lst

	while curr.next:
		curr = curr.next

	curr.next = Node(value)

	return lst


def prepend(lst, value):
	lst = Node(value, lst)
	return lst

def reprs(lst):
	values = []
	curr = lst
	while curr:
		values.append(str(curr.data))
		curr = curr.next

	return "[{}]".format(", ".join(values))


def find(lst, value):
	if not lst:
		return None

	curr = lst

	while curr:
		if curr.data == value:
			return curr
		curr = curr.next

	return None

def remove(lst, value):
	if not lst:
		return None

	curr = lst

	if curr.data == value:
		return curr.next

	while curr.next:
		if curr.next.data == value:
			# Remove this element
			curr.next = curr.next.next

		if curr.next:
			curr = curr.next

	return lst


def reverse(lst):
	curr = lst
	next_node = None
	prev_node = None

	while curr:
		next_node = curr.next
		curr.next = prev_node
		prev_node = curr
		curr = next_node

	lst = prev_node

	return lst

def remove_dup(lst):
	if not lst:
		return None

	curr = lst

	while curr.next:
		if curr.data == curr.next.data:
			curr.next = curr.next.next
		else:
			if curr.next:
				curr = curr.next
	return lst

def main():
	x = Node(1)
	x.next = Node(2)
	x.next.next = Node(3)
	x.next.next.next = Node(4)

	x = prepend(x, 0)
	x = prepend(x, 8)
	x = prepend(x, 5)
	x = prepend(x, 4)

	x = append(x, 100)
	x = append(x, 1000)

	y = find(x, 100)

	print(reprs(y)) # [100, 1000]

	print(reprs(x)) # [4, 5, 8, 0, 1, 2, 3, 4, 100, 1000]

	print(reprs(remove(x, 4))) # [5, 8, 0, 1, 2, 3, 4, 100, 1000]
	print(reprs(reverse(x))) # [1000, 100, 4, 3, 2, 1, 0, 8, 5, 4]

	y = Node(1)
	y.next = Node(2)
	y.next.next = Node(3)
	y.next.next.next = Node(4)

	y = prepend(y, 0)
	y = prepend(y, 0)
	y = prepend(y, 8)
	y = prepend(y, 8)
	y = prepend(y, 8)
	y = prepend(y, 4)

	print(reprs(y)) # [4, 8, 8, 8, 0, 0, 1, 2, 3, 4]
	print(reprs(remove_dup(y))) # [4, 8, 0, 1, 2, 3, 4]

if __name__ == '__main__':
	main()