Traversing a Linked List Data Structure

Linked lists are made up of a sequence of nodes where each node links to the next node, forming a chain-like structure. Traversing a linked list involves visiting each node in the list in sequence, access the contents of each node, and navigating to the subsequent nodes until reaching the end of the list. This article focuses on visiting all nodes in a linked list sequentially while printing the values present in each node of the linked list.

Prerequisites

Before we look at the actual algorithm and code for traversing a linked list in forward or reverse direction, let’s briefly go through how a linked list is represented and how a sample linked list is created.

In all the code snippets included in this article, each linked list node is represented with the below structure:


# Node class to store a item/value and link to the next node
class Node:
  def __init__(self, item):
    self.item = item
    self.next = None

In the Node class defined above, “item” field is used to store the data of linked list node. It’s type is set to string for this article. “next” field is used to store a reference to the next node in the linked list.

And this is how the linked list is created before the traversal operation:


# Node class to store a item/value and link to the next node
class Node:
  def __init__(self, item):
    self.item = item
    self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store references to Head node and Tail node
head = node1
tail = node4

# We can now traverse the linked list using the head pointer

In order to keep the linked list creation logic simple, all the nodes of the linked list are created together and then they are linked in a sequence. Reference to the first node (also called as the head node) is stored which can be used during iteration of all the nodes in the linked list.

Traversing a Linked List in forward direction

Below is the code to iterate through all nodes in a linked list in forward direction, while printing the values present in each node.


# Node class to store a item/value and link to the next node
class Node:
  def __init__(self, item):
    self.item = item
    self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store reference to Head node
head = node1

# Function which takes in first node (head) of a linked list
# and prints all elements in it in forward direction
def print_linked_list(head):
    # Check if the list is empty
    if head is None:
        print("The given linked list is empty")
        return

    current = head
    print("Elements in the linked list:")

    # Traverse the linked list until we reach the end
    while current is not None:
        # print item present in current node
        print(current.item, end=" ")
        
        # Move forward to the next node
        current = current.next

# We can now traverse the linked list using the head pointer
print_linked_list(head)

When you run this code, the output will be:

Elements in the linked list in forward order:
A B C D

Here is how the above code works:

  • Node class is defined to create nodes for the linked list, where each node has
    • an item attribute which stores data and
    • a next pointer which stores reference to the next node in the list.
  • print_linked_list function takes the head node pointer as an argument and traverses the entire linked list while printing the values of each node.
  • It first checks if the list is empty by verifying if the head pointer is None.
  • If the linked list is empty, it prints a message stating that the list is empty and returns.
  • If the linked list is not empty, it initializes a pointer/reference variable “current” to point to the head node of the list.
  • It then traverses the linked list starting from the head node:
    • Prints the value present in current node.
    • Moves the current pointer to the next node using current = current.next.
    • Stops when the current node reaches the end of linked list.

Traversing a Linked List in reverse direction

Below is the code to iterate through all nodes in a linked list in reverse direction, while printing the values present in each node.


# Node class to store a item/value and link to the next node
class Node:
  def __init__(self, item):
    self.item = item
    self.next = None

# Create all the nodes we need for creating linked list
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")

# Let us now link/chain the nodes in order
# to form a linked list
node1.next = node2
node2.next = node3
node3.next = node4

# Store reference to Head node
head = node1

# Function which takes in first node (head) of a linked list
# and prints all elements in it in reverse direction
def reverse_print_linked_list(head):
  # Return if we reached the end of linked list
  if head is None:
    return
  
  # Recursively traverse the list to the end
  reverse_print_linked_list(head.next)
  
  # Print the current node's data
  print(head.item, end=" ")

# We can now traverse the linked list using the head pointer
print("Elements in the linked list in reverse order:")
reverse_print_linked_list(head)

When you run this code, the output will be:

Elements in the linked list in reverse order:
D C B A

In this code, we have a Node class that represents a single node in the linked list. The reverse_print_linked_list function takes the head node of the linked list as input and recursively traverses the list in reverse direction while printing the values.

Here’s how the code works:

  • The reverse_print_linked_list function first checks if the head node is None. If it is, the function simply returns, as there’s no other node to traverse.
  • If the head node is not None, the function recursively calls itself with the next node of the current head node. This allows the function to reach the end of the linked list.
  • Once the function reaches the end of the list, it starts printing the data of each node in reverse order. This is achieved by the print statement at the end of the function.