Data Structures: Linked List with Python

If you’re just starting out in the Computer Science world, you may have started learning about data structures. Or maybe you’re trying to brush up on the basics so you be prepared to take on the l33t coding interview for your dream job. Whatever your reason may be, I’ve taken the liberty to write up one of the most basic data structures for you in python: a linked list

What is a linked list?

Simply put, a linked list is a sequence of nodes that contain data and a reference point to the next node in memory. There are many different variations of linked lists with different capabilities that may better fit different use cases, but in this blog post I’ve created a doubly linked list. My doubly linked list has the following functions/feats:

• Size: Contains a property that tracks the number of elements in the list
• AddNode(data: int): Add a new node at the end of the list with the provided data
• SetValueAt(index: int, data: int): Change the value of an existing node with the provided data
• RemoveNodeAtIndex(index: int): Remove a node at the provided index from the linked list
• GetValueAtIndex(index: int): Returns the value of the node that exists at the provided index.
• Clear(): Clears the linked list of all nodes

Code

	class Node:
	def __init__(self, data: int):
	'''
	Initialize a new Node with the provided data
	Parameters
	———-
	data: int
	Value for new Node
	———-
	'''
	self.data: int = data
	self.prev: Node = None
	self.next: Node = None
	def __str__(self):
	return str(self.data)
	class LinkedList:
	def __init__(self):
	'''
	Initialize an empty LinkedList
	'''
	self.__head: Node = None
	self.__size: int = 0
	def __str__(self):
	result: str = ""
	currentNode: Node = self.__head
	while (currentNode != None):
	result += f"{currentNode} "
	currentNode = currentNode.next
	return f"Size {self.__size}: {result}"
	@property
	def size(self):
	'''
	Number of nodes that exist within linked list.
	'''
	return self.__size
	def AddNode(self, data: int):
	'''
	Add node to end of linked list with specified data
	Parameters
	———-
	data: int
	Value for node to be added at end of linked list
	———-
	'''
	if self.__head is None:
	self.__head = Node(data)
	self.__head.prev = self.__head.next = None
	else:
	currentNode: Node = self.__head
	prevNode: Node = None
	while (currentNode.next is not None):
	prevNode = currentNode
	currentNode = currentNode.next
	newNode = Node(data)
	currentNode.next = newNode
	currentNode.prev = prevNode
	self.__size += 1
	def SetValueAt(self, index: int, data: int):
	if (index >= self.__size):
	raise ValueError("Index is greater than size of linked list!")
	currentNode: Node = self.__head
	while (index != 0):
	currentNode = currentNode.next
	index -= 1
	currentNode.data = data
	def RemoveNodeAtIndex(self, index: int):
	'''
	Remove node at specified index. Raises ValueError exception if index is
	greater than size of linked list.
	Parameters
	———-
	index: int
	Index value (starting from 0) of node to remove from linked list
	———-
	'''
	if (index >= self.__size):
	raise ValueError("Index is greater than size of linked list!")
	currentNode: Node = self.__head
	while (index != 0):
	currentNode = currentNode.next
	index -= 1
	if (currentNode.prev is not None and currentNode.next is not None):
	currentNode.prev.next = currentNode.next
	currentNode.next.prev = currentNode.prev
	currentNode = None
	elif (currentNode.prev is not None and currentNode.next is None):
	currentNode.prev.next = currentNode = None
	elif (currentNode.prev is None and currentNode.next is not None):
	self.__head = self.__head.next
	self.__head.prev = None
	else:
	self.__head = None
	self.__size -= 1
	def GetValueAtIndex(self, index: int):
	'''
	Get value of node at specified index. Raises ValueError exception if index is
	greater than size of linked list.
	Parameters
	———-
	index: int
	Index value (starting from 0) of node.
	———-
	'''
	if (index >= self.__size):
	raise ValueError("Index is greater than size of linked list!")
	currentNode: Node = self.__head
	while (index != 0):
	currentNode = currentNode.next
	index -= 1
	return currentNode
	def Clear(self):
	while (self.__head != None):
	self.__head.prev = None
	self.__head = self.__head.next
	self.__head = None
	self.__size = 0
	def main():
	# Initialize Linked List
	linkedList = LinkedList()
	print(linkedList)
	# Add 5 nodes
	linkedList.AddNode(1)
	linkedList.AddNode(2)
	linkedList.AddNode(3)
	linkedList.AddNode(4)
	linkedList.AddNode(5)
	print(linkedList)
	# Remove some nodes
	linkedList.RemoveNodeAtIndex(3)
	print(linkedList)
	linkedList.RemoveNodeAtIndex(0)
	print(linkedList)
	linkedList.RemoveNodeAtIndex(2)
	print(linkedList)
	# Add more nodes
	linkedList.AddNode(6)
	linkedList.AddNode(7)
	linkedList.AddNode(8)
	print(linkedList)
	# Change some node values
	linkedList.SetValueAt(0, 9)
	linkedList.SetValueAt(2, 8)
	linkedList.SetValueAt(linkedList.size – 1, 7)
	print(linkedList)
	# Clear linked list
	linkedList.Clear()
	print(linkedList)
	if __name__ == "__main__":
	main()

view raw LinkedList.py hosted with ❤ by GitHub

Running Code

Python3 LinkedList.py

Conclusion

As I previously mentioned, there are many different ways to create a linked list. My provided example is just one of many that you can find on the internet. I just hope that somebody out there can find my example useful in some way.

If you found this post interesting, please consider following my blog here on WordPress where I have many other posts like:

• VulnHub: Jangow 1.0.1 Writeup
• Hosting a Website with Github Pages
• Creating a Python Bot with Selenium
• Asynchronous Server/Client with Python
• Hack The Box: Impossible Password

Feel free to also follow me via my other social media accounts: Instagram, Twitter, Facebook, and Medium!

As always, if you liked what you read and you’d like to support me, please consider buying me some coffee! Every cup of coffee sent my way helps me stay awake after my full-time job so that I can produce more high quality blog posts! Any and all support would be greatly appreciated!