Python: Linked List

In arrays the size is fixed. This is why we need to know the upper limit of elements we can add.

If we have to add more than that, we’ll need to copy the elements from first array into a bigger array. This resizing of array is expensive.

As an alternative, we can use a Linked List. Here each node can stay anywhere in memory. The items/nodes need not be consecutive because each item/node holds a pointer to the next one. The image below illustrates my point:

To implement such a structure, we’ll make use of something called Node which can be a data structure in its own separate class. Then we’ll use LinkedList class which will set the head and have insert and remove functions.

Here’s how you can visualize a Linked List:

And here’s the full Python implementation:

class Node:
	def __init__(self, data):
		self.value = data
		self.next = None
 
class LinkedList:
	def __init__(self, data=None):
		self.head = data
 
	def printlist(self):
		p = self.head
 
		while p:
			print(p.value)
			p = p.next
 
	def insert(self, data):
		newnode = Node(data)
		newnode.next = self.head
		self.head = newnode
 
	def remove(self, data):
 
		p = self.head
		found = False
 
		if not p:
			return 'Empty List'
 
		if p.value == data:
			self.head = p.next
 
		while p.next:
 
			if p.next.value == data:
				p.next = p.next.next
				found = True
				break
			else: 
				p = p.next
 
		return found
 
# testing
l = LinkedList()
l.insert(1)
l.insert(2)
l.insert(3)
 
l.printlist()
 
for i in range(4):
	item = i+1
	print(l.remove(item))
 
# output:
# 3
# 2
# 1
# True
# True
# False
# Empty List

The code is again self explanatory. But to give you something to visualize, here’s the insertion of item 4 on paper:

And here’s the removal of 2 on paper:

That’s all in this post!