Step 6 of 6

100% Complete

Traversal Operations

Learn how to traverse and process all elements in a linked list

Traversing a Linked List

Traversal is the process of visiting each node in a linked list. It's a fundamental operation that forms the basis for many other operations like searching, printing, and transforming the list.

There are several common traversal patterns and operations:

Basic traversal: Visit each node in the list
Transforming: Apply a function to each node's value
Filtering: Create a new list with nodes that match a condition
Reversing: Reverse the order of nodes in the list

1. Basic Traversal

The most basic traversal pattern involves visiting each node in the list:

Basic Traversal

traverse() {
  // Start at the head of the list
  let current = this.head;
  
  // Visit each node until reaching the end
  while (current) {
    console.log(current.value);
    current = current.next;
  }
}

Traversing the list:

The linked list is empty

Time Complexity: O(n) - We need to visit each node in the list, making this a linear-time operation.

2. Transforming Values

We can transform a linked list by applying a function to each node's value:

Transform Values

map(callback) {
  const result = new LinkedList();
  
  // Start at the head of the list
  let current = this.head;
  
  // Visit each node and apply the callback function
  while (current) {
    result.append(callback(current.value));
    current = current.next;
  }
  
  return result;
}

Example usage:

// Double each value in the list
const doubled = list.map(value => value * 2);
 
// Original list: 10 → 20 → 30
// Doubled list: 20 → 40 → 60

Original list:

The linked list is empty

After doubling each value:

The linked list is empty

3. Filtering Nodes

We can create a new list containing only nodes that match a certain condition:

Filter Nodes

filter(callback) {
  const result = new LinkedList();
  
  // Start at the head of the list
  let current = this.head;
  
  // Visit each node and check the condition
  while (current) {
    if (callback(current.value)) {
      result.append(current.value);
    }
    current = current.next;
  }
  
  return result;
}

Example usage:

// Keep only even numbers
const evens = list.filter(value => value % 2 === 0);
 
// Original list: 10 → 15 → 20 → 25 → 30
// Filtered list: 10 → 20 → 30

Original list:

The linked list is empty

After filtering for even numbers:

The linked list is empty

4. Reversing a Linked List

Reversing a linked list is a common interview question and a useful operation:

Reverse a Linked List

reverse() {
  // Initialize three pointers
  let previous = null;
  let current = this.head;
  let next = null;
  
  // Traverse the list and reverse the pointers
  while (current) {
    // Save the next node
    next = current.next;
    
    // Reverse the pointer
    current.next = previous;
    
    // Move the pointers forward
    previous = current;
    current = next;
  }
  
  // Update the head to point to the new first node (previously the last)
  this.head = previous;
}

Original list:

The linked list is empty

After reversing:

The linked list is empty

Time Complexity: O(n) - We need to visit each node in the list once.

Space Complexity: O(1) - We only use a constant amount of extra space regardless of the list size.

Interactive Example

Try traversing the linked list below:

The linked list is empty

Use the controls to add nodes

Value

Operation

Check Your Understanding

Congratulations!

You've completed all the tutorials on linked lists! You now understand:

What linked lists are and their basic structure
How to create nodes and build a linked list
How to insert nodes at different positions
How to delete nodes from a linked list
How to search for elements in a linked list
How to traverse and process all elements in a linked list

With this knowledge, you're well-equipped to use linked lists in your own projects and understand more complex data structures that build upon linked lists, such as stacks, queues, and more advanced variants like doubly linked lists and circular linked lists.

Next Steps

To continue your learning journey, consider exploring:

Doubly linked lists
Circular linked lists
Skip lists
Other data structures like stacks, queues, and trees