Optimizing Singly Linked Lists with a Tail Pointer

In a standard singly linked list, inserting an element at the end requires traversing the entire list, resulting in an O(n) time complexity. To optimize this operation to O(1), we can introduce a tail pointer that always references the last node in the sequence. The structure remains a singly linked list, but the internal bookkeeping changes to allow immediate access to the end.

Below is the implementation using a sentinel head node and a dedicated tail pointer. The node structure is standard, containing data and a pointer to the next element.

#include <iostream>
#include <cstdlib>

template <typename T>
struct ListNode {
    T data;
    ListNode* next;

    ListNode() : data(T()), next(nullptr) {}
    ListNode(T val) : data(val), next(nullptr) {}
};

template <typename T>
class LinkedList {
    using Node = ListNode<T>;
private:
    Node* m_head;
    Node* m_tail;

    Node* allocateNode(const T& value) {
        Node* newNode = new Node(value);
        if (!newNode) {
            std::cerr << "Memory allocation failed" << std::endl;
            std::exit(EXIT_FAILURE);
        }
        return newNode;
    }

public:
    LinkedList() {
        m_head = new Node(); // Sentinel node
        m_tail = m_head;
    }

    void pushBack(const T& value) {
        Node* newNode = allocateNode(value);
        m_tail->next = newNode;
        m_tail = newNode; // Update tail to the new last node
    }

    void display() {
        Node* current = m_head->next;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "NULL" << std::endl;
    }
};

Implementing Circular Linked Lists

A circular linked list modifies the traversal logic by connecting the end of the list back to the begining. Specifically, the next pointer of the last node points to the head (or the sentinel node), rather than being nullptr. This structure is useful for applications requiring continuous iteration, such as round-robin scheduling.

When initializing an empty list with a sentinel node, the sentinel's next pointer points to itself. Insertions at the tail must ensure the new node links back to the head.

template <typename T>
class CircularLinkedList {
    using Node = ListNode<T>;
private:
    Node* m_head;
    Node* m_tail;

public:
    CircularLinkedList() {
        m_head = new Node(); 
        m_tail = m_head;
        m_tail->next = m_head; // Point back to head to form a circle
    }

    void pushBack(const T& value) {
        Node* newNode = new Node(value);
        
        m_tail->next = newNode;
        m_tail = newNode;
        
        // Crucial step: Close the loop
        m_tail->next = m_head; 
    }

    void display() {
        Node* current = m_head->next;
        // Loop stops when we circle back to the head
        while (current != m_head) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "(HEAD)" << std::endl;
    }
};

Expanding to Doubly Linked Lists

While singly linked lists allow forward traversal, moving backward requires traversing from the head again. A doubly linked list solves this by adding a prev pointer to each node, enabling bidirectional traversal. This addition increases memory usage per node but significantly simplifies operations like reverse deletion or backward iteration.

The insertion logic must update both the next pointer of the previous tail and the prev pointer of the new node.

template <typename T>
struct DoublyListNode {
    T data;
    DoublyListNode* next;
    DoublyListNode* prev;

    DoublyListNode() : data(T()), next(nullptr), prev(nullptr) {}
    DoublyListNode(T val) : data(val), next(nullptr), prev(nullptr) {}
};

template <typename T>
class DoublyLinkedList {
    using Node = DoublyListNode<T>;
private:
    Node* m_head;
    Node* m_tail;

public:
    DoublyLinkedList() {
        m_head = new Node();
        m_tail = m_head;
        m_head->prev = nullptr; 
    }

    void pushBack(const T& value) {
        Node* newNode = new Node(value);

        m_tail->next = newNode;
        newNode->prev = m_tail;
        
        m_tail = newNode;
    }

    void display() {
        std::cout << "Forward: ";
        Node* current = m_head->next;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "NULL" << std::endl;

        std::cout << "Backward: ";
        current = m_tail;
        while (current != m_head) {
            std::cout << current->data << " ";
            current = current->prev;
        }
        std::cout << "HEAD" << std::endl;
    }
};

The Doubly Circular Linked List

The doubly circular linked list combines the features of the previous variations. It allows traversal in both directions and wraps around at both ends. In this configuration, the prev pointer of the head node points to the tail, and the next pointer of the tail node points to the head.

This structure is robust as it eliminates edge cases associated with null pointers; every node has a valid predecessor and successor. Consequently, we can access the tail node directly via m_head->prev, potentially eliminating the need for a separate m_tail member variable, though keeping it can improve code readability.

template <typename T>
class DoublyCircularList {
    using Node = DoublyListNode<T>;
private:
    Node* m_head;

public:
    DoublyCircularList() {
        m_head = new Node();
        // Initialize circular links for the sentinel
        m_head->next = m_head;
        m_head->prev = m_head;
    }

    void pushBack(const T& value) {
        Node* newNode = new Node(value);
        
        // The node before the new node is currently the last node (head->prev)
        Node* lastNode = m_head->prev;

        // Insert new node between lastNode and head
        lastNode->next = newNode;
        newNode->prev = lastNode;
        
        newNode->next = m_head;
        m_head->prev = newNode;
    }

    void display() {
        std::cout << "Forward: ";
        Node* current = m_head->next;
        while (current != m_head) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "(HEAD)" << std::endl;

        std::cout << "Backward: ";
        current = m_head->prev; // Start from the tail
        while (current != m_head) {
            std::cout << current->data << " ";
            current = current->prev;
        }
        std::cout << "(HEAD)" << std::endl;
    }
};