Reversing a Linked List: A Hallway Analogy

Imagine that you are walking through a hallway that has several doors on either side. Each door has a name written on it, and each name is related to the one next to it in some way. You are holding a piece of paper that has the names of all the doors in the hallway, but they are in the wrong order.

As you walk down the hallway, you start to feel frustrated because you are not sure which door to go through next. Suddenly, you remember that you can use the paper to help you figure out the correct order of the doors.

You start at the end of the hallway, and look at the last name on the paper. You walk through the door with that name on it, and then look at the name on the previous line of the paper. You walk through the door with that name on it, and repeat the process until you reach the beginning of the hallway.

As you walk through each door, you cross it off on the paper to keep track of where you have been. When you reach the end of the hallway, you realize that you have successfully reversed the order of the doors!

In programming terms, the paper with the names is like a linked list, where each name is a node in the list that points to the next node. Reversing the linked list involves changing the pointers so that each node points to the previous node, instead of the next node. The hallway with the doors is just a visual representation of the linked list, where each door corresponds to a node in the list.

linkedlist.jl

module LinkedList

  export Person, reverse_list
  
  mutable struct Person
      name::String
      next::Union{Person, Nothing}
  end
  
  function reverse_hallway(person::Person)
      current_orig = person
      previous = nothing
      while current_orig != nothing
          next_person = current_orig.next
          current_orig.next = previous
          previous = current_orig
          current_orig = next_person
      end
      return previous
  end

end # end of module

main.jl

include("linkedlist.jl")

using .LinkedList: Person, reverse_hallway

# example linked list of people
person4 = Person("Alice", nothing)
person3 = Person("Bob", person4)
person2 = Person("Charlie", person3)
person1 = Person("Dave", person2)

function printoriginal_order(person1) 
  current = person1
  while current != nothing
    println(current.name)
    current = current.next
  end
end

function print_reverse_order(person1) 
  person1 = reverse_hallway(person1)
    # print new order
  current = person1
  while current != nothing
      println(current.name)
      current = current.next
  end
end


printoriginal_order(person1)
println("---")
print_reverse_order(person1)

Demo — Code Walkthrough