Reverse a Singly Linked List in Go

This document provides a complete Go program to reverse a singly linked list. The explanation covers the program structure, logic, and detailed documentation of each part of the code.

Program Structure

The program is structured into the following components:

• Node Structure: A struct to represent a node in the singly linked list.
• LinkedList Structure: A struct to encapsulate operations on the linked list, including the reversing function.
• Main Function: The entry point of the program where the linked list is created, populated, reversed, and displayed.

Go Program to Reverse a Singly Linked List

package main

import (
    "fmt"
)

// Node represents a single node in a singly linked list.
type Node struct {
    data int
    next *Node
}

// LinkedList represents the singly linked list itself.
type LinkedList struct {
    head *Node
}

// Insert adds a new node with the provided data to the end of the list.
func (ll *LinkedList) Insert(data int) {
    newNode := &Node{data: data, next: nil}
    if ll.head == nil {
        ll.head = newNode
    } else {
        current := ll.head
        for current.next != nil {
            current = current.next
        }
        current.next = newNode
    }
}

// Reverse reverses the singly linked list.
func (ll *LinkedList) Reverse() {
    var prev, next *Node
    current := ll.head
    for current != nil {
        next = current.next   // Store the next node
        current.next = prev   // Reverse the current node's pointer
        prev = current        // Move prev to this node
        current = next        // Move to the next node
    }
    ll.head = prev // Update the head to the new front of the list
}

// Display prints all elements of the linked list.
func (ll *LinkedList) Display() {
    current := ll.head
    for current != nil {
        fmt.Printf("%d -> ", current.data)
        current = current.next
    }
    fmt.Println("nil")
}

// Main function to demonstrate the reversal of the linked list.
func main() {
    ll := &LinkedList{}
    ll.Insert(1)
    ll.Insert(2)
    ll.Insert(3)
    ll.Insert(4)
    ll.Insert(5)

    fmt.Println("Original List:")
    ll.Display()

    ll.Reverse()

    fmt.Println("Reversed List:")
    ll.Display()
}

Explanation

Node Structure

The Node struct represents a node in the singly linked list. Each node has two fields:

• data: Holds the integer data.
• next: Points to the next node in the list.

LinkedList Structure

The LinkedList struct manages the list. It contains the head pointer that refers to the first node of the list.

• Insert Method: This method adds a new node to the end of the list.
• Reverse Method: This method reverses the linked list by iterating through it and adjusting the next pointers of each node.
• Display Method: This method prints the data of each node in the list in order.

Reversing Logic

The reversal of the list is done iteratively. Three pointers are used:

• prev: Initially set to nil, it will eventually point to the new head of the list.
• current: Points to the current node being processed.
• next: Stores the next node to prevent losing the remaining list during the reversal.

During each iteration, the next pointer of the current node is redirected to the prev node. Then, prev and current are moved one step forward until the entire list is reversed.

Main Function

The main function creates an instance of LinkedList, inserts several nodes, displays the original list, reverses it, and finally displays the reversed list.