[Blog 008] Data Structures: Linked List Implementation

Linked lists can be implemented in various programming languages, including Python, Java, and C++. The basic idea behind linked lists is to store data in nodes and have each node point to the next node in the list. In this section, we'll walk through the process of implementing a linked list in Python.

Defining the Node Class

The first step in implementing a linked list is to define the node class. A node class should contain two properties: data and next_node. The data property stores the value of the node and the next_node property stores the reference to the next node in the list. Here is an example implementation of the node class in Python:

python code
class Node:
    def __init__(self, data):
        self.data = data
        self.next_node = None

Defining the Linked List Class

The next step is to define the linked list class. The linked list class should have two properties: head and tail. The head property points to the first node in the list and the tail property points to the last node in the list. Here is an example implementation of the linked list class in Python:

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

Adding Nodes to the List

To add a node to the linked list, we create a new node and update the next_node property of the current tail node to point to the new node. If the linked list is empty, we update both the head and tail properties to point to the new node. Here is an example implementation of the add_node method in the linked list class in Python:

python code
class LinkedList:
    # ...def add_node(self, data):
        new_node = Node(data)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next_node = new_node
            self.tail = new_node

Removing Nodes from the List

To remove a node from the linked list, we need to update the next_node property of the node before the node we want to remove to point to the node after the node we want to remove. Here is an example implementation of the remove_node method in the linked list class in Python:

pythonCopy code
class LinkedList:
    # ...def remove_node(self, data):
        previous = None
        current = self.head
        while current is not None:
            if current.data == data:
                if previous is None:
                    self.head = current.next_node
                else:
                    previous.next_node = current.next_node
                return
            previous = current
            current = current.next_node

Iterating Over the List

To iterate over the linked list, we can start at the head node and follow the next_node properties until we reach the tail node. Here is an example implementation of the iterate method in the linked list class in Python:

python code
def iterate(self):
    node = self.head
    while node:yield node.value
        node = node.next_node

This method uses a while loop to traverse the linked list. The loop continues until the node variable is None, indicating that we have reached the tail node. In each iteration of the loop, the current node's value is returned using the yield statement. This allows us to easily loop over the linked list and access the values of all its nodes in order.

Here's an example of how you could use this method:

python code
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

for value in linked_list.iterate():
    print(value)

This code creates a linked list and adds three nodes to it. The for loop then uses the iterate method to loop over the linked list and print the values of each node. The output of this code will be:

output:
1
2
3

And that's it! By implementing the linked list data structure, we've seen how to create, insert, and traverse a linked list in Python. The linked list is a powerful and versatile data structure that can be used for a variety of tasks, from simple lists of data to more complex algorithms.