Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Mastering Doubly Linked Lists in C++: Build a Queue/Stack with Location Coordinates

Learn to implement a templated doubly linked list in C++ with queue and stack operations, using location coordinates as data. This tutorial covers node structure, iterator methods, and practical tips for your COP3504C lab assignment.

doubly linked list C++ templated linked list queue implementation C++ stack implementation C++ iterator pattern C++ COP3504C lab 09 linked list tutorial 2026 C++ data structures linked list remove method memory leak detection C++ enqueue dequeue C++ linked list iterator C++ programming assignment help location coordinates linked list FIFO LIFO C++ linked list edge cases

Why Linked Lists Matter in 2026

Linked lists are the backbone of many real-world applications, from undo features in apps like Photoshop to managing player queues in online games. In 2026, as AI-powered apps and metaverse platforms grow, understanding data structures like doubly linked lists becomes essential for efficient memory management. This tutorial will guide you through building a templated doubly linked list that can function as both a queue and a stack, using location coordinates (x,y) as sample data. By the end, you'll be ready to tackle your COP3504C lab 09 assignment with confidence.

What is a Doubly Linked List?

A doubly linked list is a sequential data structure where each node contains data and two pointers: one pointing to the next node and one to the previous node. The list starts at a front node and ends at a back node, both pointing to nullptr at the ends. This bidirectional linking allows efficient insertion and deletion from both ends, making it ideal for implementing queues (FIFO) and stacks (LIFO).

Think of it like a two-way street in a smart city: each intersection (node) knows the next and previous intersection, so a navigation app can traverse in either direction. In your lab, each node stores a coordinate pair like (3,4) or (5,12), representing a location in a grid.

Node Structure

Each node in your linked list holds three things:

  • Data: The element (e.g., a std::pair<int, int> for coordinates)
  • Next pointer: Points to the next node in the list
  • Previous pointer: Points to the previous node
template <typename T>
struct Node {
    T data;
    Node* next;
    Node* prev;
    Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};

LinkedList Class Overview

Your LinkedList class will manage pointers to the front and back nodes, and provide methods for adding, removing, and accessing elements. The class is templated so it can work with any data type, but your lab uses location coordinates.

Key Methods

  • enqueue(): Adds to the back – like adding a new player to the end of a queue in a battle royale game.
  • dequeue(): Removes from the front – like the first player in the queue getting into a match.
  • pop(): Removes from the back – like undoing the last action in a drawing app.
  • clear(): Removes all nodes – like resetting a game board.
  • remove(T element): Deletes the first node with matching data – think of removing a specific item from a shopping cart.

These methods allow your list to behave as a queue (using enqueue/dequeue) or a stack (using enqueue/pop or push/pop if you add a push method).

Implementing the Iterator

Iterators let you traverse the list without exposing internal pointers. Your nested Iterator class must support:

  • operator*(): Returns the current element.
  • operator++(): Moves to next node (pre-increment).
  • operator--(): Moves to previous node (pre-decrement).
  • operator== and operator!=: Compare iterators.

When an iterator moves past the last node, it should equal end() (a state where the internal pointer is nullptr). Similarly, decrementing before the first node also yields end().

class Iterator {
    Node* current;
public:
    Iterator(Node* ptr) : current(ptr) {}
    T operator*() const { return current->data; }
    Iterator& operator++() {
        if (current) current = current->next;
        return *this;
    }
    Iterator& operator--() {
        if (current) current = current->prev;
        return *this;
    }
    bool operator==(const Iterator& rhs) const { return current == rhs.current; }
    bool operator!=(const Iterator& rhs) const { return current != rhs.current; }
};

Note: For decrement, you might need to handle the case where current is nullptr (end) by moving to the back node. However, the spec says if the iterator is before the first element, it should be equal to end(). Typically, end() represents past-the-end, so decrement from end() should give the last node. Check your assignment details.

Building the LinkedList Methods

Constructor and isEmpty

template <typename T>
LinkedList<T>::LinkedList() : front(nullptr), back(nullptr) {}

template <typename T>
bool LinkedList<T>::isEmpty() const { return front == nullptr; }

getFront and getBack

template <typename T>
T LinkedList<T>::getFront() const {
    if (isEmpty()) throw std::out_of_range("List is empty");
    return front->data;
}

template <typename T>
T LinkedList<T>::getBack() const {
    if (isEmpty()) throw std::out_of_range("List is empty");
    return back->data;
}

enqueue (add to back)

template <typename T>
void LinkedList<T>::enqueue(T element) {
    Node* newNode = new Node(element);
    if (isEmpty()) {
        front = back = newNode;
    } else {
        back->next = newNode;
        newNode->prev = back;
        back = newNode;
    }
}

dequeue (remove from front)

template <typename T>
void LinkedList<T>::dequeue() {
    if (isEmpty()) return;
    Node* temp = front;
    front = front->next;
    if (front) front->prev = nullptr;
    else back = nullptr;
    delete temp;
}

pop (remove from back)

template <typename T>
void LinkedList<T>::pop() {
    if (isEmpty()) return;
    Node* temp = back;
    back = back->prev;
    if (back) back->next = nullptr;
    else front = nullptr;
    delete temp;
}

clear

template <typename T>
void LinkedList<T>::clear() {
    while (!isEmpty()) {
        dequeue(); // or pop, either works
    }
}

contains

template <typename T>
bool LinkedList<T>::contains(T element) const {
    Node* current = front;
    while (current) {
        if (current->data == element) return true;
        current = current->next;
    }
    return false;
}

remove (first occurrence)

This is the trickiest method. You must handle four cases:

  1. Remove the only node
  2. Remove the first node (front)
  3. Remove a middle node
  4. Remove the last node (back)
template <typename T>
void LinkedList<T>::remove(T element) {
    Node* current = front;
    while (current) {
        if (current->data == element) {
            if (current == front && current == back) {
                // only node
                front = back = nullptr;
            } else if (current == front) {
                front = front->next;
                front->prev = nullptr;
            } else if (current == back) {
                back = back->prev;
                back->next = nullptr;
            } else {
                current->prev->next = current->next;
                current->next->prev = current->prev;
            }
            delete current;
            return;
        }
        current = current->next;
    }
}

Notice that after removing, you must update the adjacent nodes' pointers accordingly.

Iterator begin, end, tail

template <typename T>
typename LinkedList<T>::Iterator LinkedList<T>::begin() const {
    return Iterator(front);
}

template <typename T>
typename LinkedList<T>::Iterator LinkedList<T>::end() const {
    return Iterator(nullptr);
}

template <typename T>
typename LinkedList<T>::Iterator LinkedList<T>::tail() const {
    return Iterator(back);
}

Using the List as a Queue or Stack

To use as a queue (FIFO):

  • Add elements with enqueue()
  • Remove elements with dequeue()

To use as a stack (LIFO):

  • Add elements with enqueue() (or a dedicated push() method that adds to front)
  • Remove elements with pop()

Your lab likely expects you to use enqueue/pop for stack behavior, but you could also add a push method. Check the specification.

Common Pitfalls and Tips

  • Memory leaks: Always delete nodes when removing. Use a memory leak detector like nvwa to check.
  • Null pointer dereference: Before accessing current->next or current->prev, ensure current is not nullptr.
  • Edge cases: Test with empty list, single element, removing first/middle/last.
  • Iterator decrement from end: If your end() iterator points to nullptr, decrementing it should ideally move to the last node. But the spec says if iterator is before first, it should equal end. Clarify with your instructor or test driver.

Real-World Analogy: AI Chat History

Imagine an AI chatbot that stores conversation history as a doubly linked list. Each message is a node. You can traverse forward (next messages) or backward (previous messages). The list can act as a queue (new messages added at back, oldest removed from front) or as a stack (undo last message by popping from back). This structure is efficient for managing dynamic sequences where insertions and deletions happen at both ends.

Conclusion

Doubly linked lists are a fundamental data structure that every C++ programmer should master. By implementing a templated list with queue and stack operations, you gain hands-on experience with pointers, memory management, and iterator design. Use the code snippets and tips in this tutorial to complete your COP3504C lab 09 successfully. Remember to test thoroughly and match the expected output exactly. Happy coding!