Python Linked List: Simple Implementation Guide

Linked Lists in Python: An Introduction

Linked lists are an important data structure that can be used in various applications. In this article, we will explain what linked lists are, how they work, and how to use them in Python. We will also provide step-by-step sample code and explanations to help you understand the concept better.

Table of Contents

• Understanding Linked Lists
  • Main Concepts
  • Practical Applications
  • Performance Comparison: Lists vs Linked Lists
• Introducing collections.deque
  • How to Use collections.deque
  • How to Implement Queues and Stacks
• Implementing Your Own Linked List
  • How to Create a Linked List
  • How to Traverse a Linked List
  • How to Insert a New Node
  • How to Remove a Node
• Using Advanced Linked Lists
  • How to Use Doubly Linked Lists
  • How to Use Circular Linked Lists
• Conclusion

Understanding Linked Lists

Main Concepts

Linked lists are data structures used to store elements in an ordered way. Each element in a linked list is called a node and contains two fields:

1. Data: the value to be stored in the node.
2. Next: a reference to the next node in the list.

A linked list is a collection of nodes, with the first node called the head. The last node in the list has its next reference set to None, indicating the end of the list.

Practical Applications

Linked lists have various practical applications, such as:

• Implementing dynamic data structures like stacks and queues.
• Manipulating large amounts of data efficiently.
• Representing complex data structures like trees and graphs.
• Building hash tables and hash maps.

Performance Comparison: Lists vs Linked Lists

Linked lists offer some advantages over regular lists in certain scenarios. For example, inserting or deleting an element in a linked list is faster compared to regular lists, especially when dealing with large data sets. However, regular lists offer faster random access to elements. The choice between the two depends on the specific requirements of your application.

Introducing collections.deque

Python’s collections module provides a built-in class called deque (double-ended queue), which can be used as a linked list. The deque class supports operations like inserting and deleting elements from both ends, making it suitable for implementing stacks and queues.

How to Use collections.deque

To use collections.deque, you first need to import it from the collections module. Here’s an example:

from collections import deque

my_list = deque()
my_list.append(1)
my_list.append(2)
my_list.append(3)
print(my_list)  # Output: deque([1, 2, 3])

How to Implement Queues and Stacks

With collections.deque, you can easily implement a queue or stack. Here’s an example of implementing a stack:

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # Output: 3

And here’s an example of implementing a queue:

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft())  # Output: 1

Implementing Your Own Linked List

In some cases, you may need to implement your own linked list. Here’s a step-by-step guide on how to create, traverse, insert, and remove nodes in a linked list.

How to Create a Linked List

To create a linked list, you need to define a Node class with a data field and a next reference. Here’s an example:

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

# Create linked list
head = Node(1)
second = Node(2)
third = Node(3)

head.next = second
second.next = third

How to Traverse a Linked List

To traverse a linked list, you start from the head and keep moving to the next node until you reach the end (next reference is None). Here’s an example:

current = head
while current is not None:
    print(current.data)
    current = current.next

How to Insert a New Node

To insert a new node into a linked list, you need to update the next reference of the previous node and the new node. Here’s an example of inserting a node with data 4 after the head:

new_node = Node(4)
new_node.next = head.next
head.next = new_node

How to Remove a Node

To remove a node from a linked list, you need to update the next reference of the previous node to skip the node you want to remove. Here’s an example of removing the node with data 2:

previous = head
current = head.next

while current is not None:
    if current.data == 2:
        previous.next = current.next
        break

    previous = current
    current = current.next

Using Advanced Linked Lists

Besides the basic linked list, there are also advanced types of linked lists that you can use depending on your needs.

How to Use Doubly Linked Lists

A doubly linked list is similar to a regular linked list, but each node contains a reference to both the previous and next nodes. This allows for more efficient traversal in both directions. You can implement a doubly linked list in Python by modifying the Node class.

How to Use Circular Linked Lists

A circular linked list is a type of linked list where the next reference of the last node points back to the head. This creates a loop, allowing for infinite traversal. Circular linked lists are useful in situations where you need to continuously iterate over a set of elements.

Conclusion

Linked lists are an important data structure that can be used in various scenarios. In this article, we explained the main concepts of linked lists, discussed their practical applications, and provided examples of how to implement and use them in Python. We also introduced advanced types of linked lists, such as doubly linked lists and circular linked lists. By mastering linked lists, you can enhance your understanding of data structures and boost your programming skills in Python.

Remember to practice and experiment with the provided sample code to grasp the concepts better.