Linked List – Code Snippet

We can see linked list implementation in python in the following code. And with some important operations of the linked list. The time complexity of every operation is O(n) except insert_front and empty. And the complexity of insert_front and empty is O(1).

Singly Linked List

class Node():

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

class LinkedList():
	
	def __init__(self):
		self.head = None

	
	# insert_front
	def insert_front(self, data):
		new_node = Node(data)
		new_node.next = self.head
		self.head = new_node
	
	# insert_last
	def insert_last(self, data):
		new_node = Node(data)
		
		if self.head:
			current = self.head
			while current.next:
				current = current.next
			
			current.next = new_node
		else:
			self.head = new_node
	
	# insert_after
	def insert_after(self, target, data):
		if self.head == None:
			print('List is empty')
			return
			
		new_node = Node(data)
		current = self.head
		
		while current:
			if current.data == target:
				new_node.next = current.next
				current.next = new_node
				return
				
			current = current.next
		
		print(f'Node with data {data} not found')
		
	# insert_before
	def insert_before(self, target, data):
		if self.head == None:
			print('List is empty')
			return;
		
		if self.head.data == target:
			return self.insert_front(data)
		
		new_node = Node(data)
		current = self.head
		prev = self.head
		
		while current:
			if current.data == target:
				prev.next = new_node
				new_node.next = current
				return
			
			prev = current
			current = current.next
			
	
		print(f'Node with data {data} not found')
	
	# traverse
	def traverse(self):
		current = self.head
		nodes = []
		while current:
			nodes.append(str(current.data))
			current = current.next
		nodes.append('None')
		
		return '->'.join(nodes)
	
	# Size 
	def size(self):
		current = self.head
		count = 0
		
		while current:
			count += 1
			current = current.next
			
		print(f'Total Node = {count}')
		
	# Search 
	def search(self, data):
		current = self.head
		while current:
			if current.data == data:
				return True
			
			current = current.next
		return False
		
	# Remove 
	def remove(self, target):
		if self.head == None:
			print('List is empty')
			return
		
		if self.head.data == target:
			self.head = self.head.next
			return
		
		prev = self.head
		current = self.head
		
		while current:
			if current.data == target:
				prev.next = current.next
				return
				
			prev = current
			current = current.next
		
		print(f'Node with data {target} not found')
		
	# empty
	def empty(self):
		return self.head == None

lists = LinkedList()
lists.insert_last(1)
lists.insert_last(2)
lists.insert_last(3)
lists.insert_last(4)
lists.insert_last(5)
lists.insert_front(0)
lists.insert_after(4, 11)
lists.insert_before(0, 10)
lists.insert_before(5, 15)
lists.remove(15)
print(lists.traverse())
lists.size()
print(lists.empty())

print(lists.search(5))
print(lists.search(7))

Doubly Linked List

class Node():

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

Tags: Code