Linked Lists

Linked lists are a fundamental data structure in computer science. Unlike arrays, linked lists are a flexible way to store and manage collections of data. Linked lists are especially useful when dealing with collections of data that are dynamic and unpredictable. Understanding linked lists is crucial for programmers as they form the basis for more complex data structures like stacks, queues, and graphs. This guide will explore the linked list data structure, including its importance and how to implement and work with linked lists in Python.

What Is A Linked List

A linked list is a linear data structure where elements are stored in nodes. Each node contains two parts: the data, and a link to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, which makes them ideal in situations where dynamic memory allocation is needed.

Type Of Linked Lists

There are several types of linked lists with each having their own unique purpose:

• Singly linked list:
  • Each node points to the next node and the last node points to None.
• Doubly linked list:
  • Each node points to the next node and to the previous node.
• Circular linked list:
  • The last node points back to the first node, forming a circle.

This guide will focus on singly linked lists, but you can learn more about doubly and circular linked lists by continuing through this section.

Why Linked Lists Are Important

Linked lists are crucial in programming for several reasons:

• Dynamic memory allocation:
  • Linked lists can grow or shrink as needed, making them more flexible than arrays.
• Efficient insertion/deletion:
  • Since linked lists don’t require contiguous memory locations, insertion and deletion is much more efficient compared to arrays where shifting elements is necessary.
• Foundation for advanced data structures:
  • Linked lists are the building blocks for more advanced data structures like stacks, queues, and graphs.

Implementing A Singly Linked List In Python

In this example, we will be implementing a basic singly linked list in Python. We’ll start by defining a Node class to represent each element, and a LinkedList class to manage the nodes.

Step 1: Define The Node Class

pythonCopy code
class Node:
	def __init__(self, data):
		self.data = data  # Store the data
		self.next = None  # Initialize the next pointer as None

Each Node object contains the data and a reference to the next node in the list.

Step 2: Define The LinkedList Class

pythonCopy code
class LinkedList:
	def __init__(self):
		self.head = None  # Initialize the head of the list
	
	def append(self, data): 
		new_node = Node(data)
		if self.head is None:
			self.head = new_node  # If the list is empty, make the new node the head
			return
		last = self.head
		while last.next:
			last = last.next    # Traverse to the end of the list
		last.next = new_node   # Link the last node to the new node
		
	def print_list(self):
		current = self.head
		while current:
			print(current.data, end" -> ")
			current = current.next
		print("None")

In the LinkedList class:

• append(data) adds a new node to the end of the list.
• print_list() prints the linked list in a readable format.

Here is a detailed explanation to the LinkedList class in the example above:

• The __init__ method:
  • This method is the constructor for the LinkedList class, initializing the linked list by setting the head attribute to None.
  • The head is a reference to the first node in the list.
• The append method:
  • This method adds a new node to the end of the linked list.
  • new_node = Node(data) creates a new Node object with the provided data.
  • if self.head is None: checks if the list is empty and the new node becomes the head of the list if it is empty.
  • while last.next: traverses the list by following the next pointers until it reaches the last node.
  • last.next = new_node: updates the next pointer of the last node to point to the new node once the end of the list is reached, adding it to the end of the list.
• The print_list method:
  • This method prints the data in each node of the linked list in a readable format.
  • current = self.head starts the method at the head of the list.
  • while current: traverses the list, printing the data of each node followed by an arrow (→) until it reaches the end of the list.
  • print("None") prints None after printing all the nodes to indicate the end of the list.

Step 3: Using The LinkedList Class

pythonCopy code
# Create a LinkedList object
link_list = LinkedList()

# Append data to the linked list
link_list.append(1)
link_list.append(2)
link_list.append(3)

# Print the linked list
link_list.print_list()

# Output:
# 1 -> 2 -> 3 -> None

This code creates a linked list with three nodes and prints the list.

Common Linked List Operations

Linked lists support various operations, including:

• Insertion:
  • Adding a node to the beginning, end, or specific position in the list.
• Deletion:
  • Removing a node from the beginning, end, or specific position in the list.
• Traversal:
  • Visiting each node in the list to perform operations like searching or printing.

Deleting A Node In A Linked List

The following code is an example of deleting a node in a linked list with Python:

pythonCopy code
def delete_node(self, key):
	current = self.head
	
	if current is not None:
		if current.data == key:
			self.head = current.next  # Change head if the node being deleted is the head
			current = None
			return
	
	while current is not None:
		if current.data == key:
			break
		prev = current
		current = current.next
	
	if current is None:
		return
	
	prev.next = current.next
	current = None

This method deletes the first occurrence of a node with the given data (key) from the linked list.

Here are the steps to the delete_node(self, key) method explained:

• Initialize the current node:

  pythonCopy code
  current = self.head

  • Assigns self.head to the variable current. self.head refers to the first node in the linked list, and the current variable will be used to traverse the linked list.

• Check if the head node contains the key:

  pythonCopy code
  	if current is not None:
  		if current.data == key:
  			self.head = current.next  
  			current = None
  			return

  • Checks if the linked list is empty (current is not None). If the list is not empty and the head node contains the key, the method updates the self.head to current.next , removing the head from the list.
  • It then sets current to None to delete the node and exit the method.

• Traverse the list to find the key:

  pythonCopy code
  	while current is not None:
  		if current.data == key:
  			break
  		prev = current
  		current = current.next

  • If the head does not contain the key, the method enters a while loop to traverse the linked list until it finds the node with the matching key or reaches the end of the list.
  • prev keeps track of the node before current , allowing the method to re-link the previous node to the node after current when deleting the node.

• Check if the key was found:

  pythonCopy code
  if current is None:
  	return

  • If the loop finishes without finding the key, the method returns without doing anything.

• Delete the node:

  pythonCopy code
  prev.next = current.next
  current = None

  • If the key was found, the method updates the next pointer of the prev node to skip over the current node, removing it from the list.
  • The current node is then set to None to delete it.

Advantages And Disadvantages Of Linked Lists

Advantages:

• Dynamic Size:
  • The size of a linked list can grow and shrink as needed.
• Efficient insertion/deletion:
  • Inserting and deleting nodes doesn’t require shifting of elements.

Disadvantages:

• No random access:
  • Accessing elements in a linked list requires traversing the list from the beginning, resulting in O(n) time complexity.
• Memory overhead:
  • Each node requires extra memory for storing the reference to the next node.

Linked List Use Cases

Linked lists are used in various applications, including:

• Implementation of stacks and queues:
  • Linked lists can efficiently implement stacks and queues where elements are frequently added or removed.
• Dynamic memory allocation:
  • Linked lists manage dynamic memory allocation, making them ideal for implementing custom memory management systems.
• Graph adjacency lists:
  • Linked lists represent adjacency lists in graph data structures, making them suitable for graph algorithms.

Conclusion

Linked lists are a fundamental data structure that provides flexibility in memory management and efficient data operations. Understanding linked lists is crucial for mastering more advanced data structures and algorithms. By learning how to implement and linked lists in Python, you’ll be better equipped for solving a wide range of programming challenges and LeetCode problems.

This guide has provided to introduction to linked lists, including their implementation in Python, common operations, and use cases. Continue through this section to learn more advanced topics with Linked Lists and other data structures in detail.