GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-2) Linked Lists – Doubly Linked Lists

In the official GESP C++ Level 5 exam outline, there are a total of <span>9</span> key points. This article analyzes and introduces the <span>3</span> key point.

(3) Master the creation, insertion, deletion, traversal, and reversal operations of linked lists, and understand the differences between singly linked lists, doubly linked lists, and circular linked lists.

Due to the extensive content and the involvement of code writing and verification, this knowledge point will be introduced in three parts: singly linked lists, doubly linked lists, and circular linked lists.

I am also learning, experimenting, and summarizing, and my grasp of the depth and breadth of the exam outline is based on personal understanding. Therefore, this article is more of a personal knowledge review rather than a tutorial. Any omissions or oversights are welcome for correction and discussion.

Review of other Level 5 key points:

• 【GESP】C++ Level 5 Exam Outline Knowledge Points Review, (1) Elementary Number Theory
• 【GESP】C++ Level 5 Exam Outline Knowledge Points Review, (2) Simulating High-Precision Calculations
• 【GESP】C++ Level 5 Exam Outline Knowledge Points Review, (3-1) Linked Lists – Singly Linked Lists

1. Basic Concepts of Doubly Linked Lists

A doubly linked list (Doubly Linked List) is a type of linked data structure where each node contains three parts:

1. Data Field (data)
2. Previous Pointer (prev): points to the previous node
3. Next Pointer (next): points to the next node

Compared to singly linked lists, the advantage of doubly linked lists is that they allow for bidirectional traversal, and insertion and deletion are more efficient when the node pointer is known; the disadvantage is that it requires additional space to store the <span>prev</span> pointer.

1.1 Characteristics of Doubly Linked Lists

Characteristic	Doubly Linked List
Pointer Direction	Each node has <span>prev</span> and <span>next</span> pointers
Advantages	Supports forward and backward traversal; insertion/deletion can be done when the node pointer is known
Disadvantages	Uses more memory; implementation is slightly more complex

2. Basic Operations of Doubly Linked Lists

2.1 Node Definition

// Define the structure of a doubly linked list node
struct DNode {
    int data;         // Data field
    DNode* prev;      // Points to the previous node
    DNode* next;      // Points to the next node
    // Constructor
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

2.2 Creating a Doubly Linked List

Creating a doubly linked list mainly involves the following steps:

1. Initialize Pointers

• Create head pointer <span>head</span> and tail pointer <span>tail</span>, both initially null
• Used to track the positions of the head and tail nodes of the list

Create New Nodes

• Create new nodes for each data value
• Set the data field and pointer fields of the nodes

Establish Connections Between Nodes

• Set the <span>prev</span> pointer of the new node to point to the current tail node
• Set the <span>next</span> pointer of the current tail node to point to the new node
• Update the tail pointer to the new node

• Point both head and tail pointers to this node

• If it is the first node:
• If it is not the first node:

Return the Head of the List

• Return the head pointer of the created list

// Create a doubly linked list
// @param vals: Array of data used to create the list
// @return: Returns the head pointer of the created doubly linked list
DNode* createDList(const vector<int>& vals) {
    DNode* head = nullptr;  // Head pointer, points to the first node of the list
    DNode* tail = nullptr;  // Tail pointer, points to the last node of the list

    // Traverse the input array and create nodes one by one
    for (int val : vals) {
        DNode* newNode = new DNode(val); // Create a new node
        if (!head) {
            // If it is the first node, update head and tail pointers
            head = tail = newNode;
        } else {
            // Otherwise, append the new node at the tail
            tail->next = newNode;      // Current tail node's next points to the new node
            newNode->prev = tail;      // New node's prev points to the old tail node
            tail = newNode;            // Update tail pointer to the new node
        }
    }
    // Return the head pointer of the list
    return head;
}

2.3 Inserting Nodes

2.3.1 Inserting at a Given Position

Inserting a node at a given position mainly involves the following steps:

1. Check Position Validity

• If the position is 0, insert at the head
• If the position is greater than the length of the list, insert at the tail
• Otherwise, traverse to the node before the specified position

Create New Node

• Create a new linked list node for the new value

Insert Node

• Insert the new node at the target position and update pointers
• If inserting at the head, update the head pointer
• If inserting in the middle, update the <span>next</span> pointer of the previous node and the <span>prev</span> pointer of the new node
• If inserting at the tail, update the tail pointer and the <span>next</span> pointer of the previous node

// Insert a node at position pos (0-based)
// @param head: Reference to the head pointer of the doubly linked list, to modify the head pointer
// @param pos: The position to insert (0 means head)
// @param val: The value of the new node to insert
void insertAtPosition(DNode*& head, int pos, int val) {
    DNode* newNode = new DNode(val);  // Create a new node

    // If inserting at the head
    if (pos == 0) {
        newNode->next = head;  // New node's next points to the original head node
        if (head) {
            head->prev = newNode;  // If the original head node exists, prev points to the new node
        }
        head = newNode;  // Update head pointer to the new node
        return;
    }

    DNode* cur = head;  // Start traversing from the head node
    // Traverse to the node before the insertion position
    for (int i = 0; i < pos - 1 && cur; ++i) {
        cur = cur->next;
    }

    // If the previous node for the insertion position is found
    if (cur) {
        newNode->next = cur->next;      // New node's next points to the next node at the current position
        newNode->prev = cur;            // New node's prev points to the current node
        if (cur->next)                  // If the next node at the current position exists
            cur->next->prev = newNode;  // The next node's prev points to the new node
        cur->next = newNode;            // Current node's next points to the new node
    }
}

2.3.2 Inserting After a Given Node

Inserting a new node after a given node mainly involves the following steps:

1. Check if the Target Node is Null

• If the target node is null, return directly without performing the insertion operation

Create New Node

• Create a new linked list node for the new value

Insert Node

• Insert the new node at the target position and update pointers
• The new node’s <span>next</span> points to the next node of the target node
• The new node’s <span>prev</span> points to the target node
• If the next node of the target node exists, update its <span>prev</span> pointer to point to the new node
• The target node’s <span>next</span> points to the new node

// Insert a new node after the specified target node
// @param target: Pointer to the target node, where the new node will be inserted after
// @param val: The value of the new node to insert
void insertAfter(DNode* target, int val) {
    if (!target) {
        return;  // If the target node is null, return directly
    }

    DNode* newNode = new DNode(val);  // Create a new node

    // New node's next points to the target node's next node
    newNode->next = target->next;
    // New node's prev points to the target node
    newNode->prev = target;

    // If the target node's next node exists, let its prev point to the new node
    if (target->next)
        target->next->prev = newNode;

    // Target node's next points to the new node
    target->next = newNode;
}

2.4 Deleting Nodes

2.4.1 Deleting at a Specified Position

Deleting a node at a specified position mainly involves the following steps:

1. Check if the List is Empty

• If the list is empty, return directly without performing the deletion operation

Check the Position to Delete

• If the position to delete is 0, delete the head node
• Otherwise, traverse to the node before the specified position

Delete Node

• If the previous node for the position to delete exists, update its <span>next</span> pointer to point to the next node of the node to be deleted
• If the next node of the node to be deleted exists, update its <span>prev</span> pointer to point to the previous node of the node to be deleted
• Free the memory of the node to be deleted

// Delete the node at the specified position
// @param head: Reference to the head pointer of the doubly linked list
// @param pos: The position of the node to delete (0-based)
void deleteAtPosition(DNode*& head, int pos) {
    if (!head) {
        // If the list is empty, return directly
        return;
    }

    DNode* cur = head;  // Pointer for traversal

    // If the node to delete is the head node
    if (pos == 0) {
        head = head->next;         // Head pointer points to the next node
        if (head) {
            head->prev = nullptr;  // New head node's prev set to nullptr
        }
        delete cur;                // Free the original head node
        return;
    }

    // Traverse to the node to delete
    for (int i = 0; i < pos && cur; ++i) {
        cur = cur->next;
    }

    // If the node to delete is found
    if (cur) {
        if (cur->prev) {
            cur->prev->next = cur->next;  // Previous node's next points to the next node of the current node
        }
        if (cur->next) {
            cur->next->prev = cur->prev;  // Next node's prev points to the previous node of the current node
        }
        delete cur;  // Free the current node
    }
}

2.4.2 Deleting a Node with a Specified Value

Deleting the first node with the value val in the list mainly involves the following steps:

1. Check if the List is Empty

• If the list is empty, return directly without performing the deletion operation

Traverse the List to Find the Node

• Start traversing the list from the head node to find the first node with the value val

Delete Node

• If the node is found, update the next pointer of the previous node to point to the next node of the current node
• If the node to delete is the head node, update the head pointer to the next node
• If the current node is not the tail node, update the prev pointer of the next node to point to the previous node of the current node
• Free the memory of the current node

// Delete the first node with the value val in the list
// @param head: Reference to the head pointer of the doubly linked list, to modify the head pointer
// @param val: The value of the node to delete (only deletes the first matching node)
void deleteNode(DNode*& head, int val) {
    DNode* cur = head;  // Pointer for traversing the list

    // Traverse the list to find the first node with the value val
    while (cur && cur->data != val) {
        cur = cur->next;
    }

    // If the node is found
    if (cur) {
        // If the node to delete is not the head node
        if (cur->prev) {
            // Previous node's next points to the current node's next node
            cur->prev->next = cur->next;
        } else {
            // If the node to delete is the head node, update the head pointer
            head = cur->next;
        }

        // If the current node is not the tail node
        if (cur->next) {
            // Next node's prev points to the current node's previous node
            cur->next->prev = cur->prev;
        }

        // Free the current node's memory
        delete cur;
    }
}

2.5 Traversing the List

2.5.1 Forward Traversal

Forward traversing the list mainly involves the following steps:

1. Check if the List is Empty

• If the list is empty, return directly without performing the traversal operation

Traverse the List

• Start traversing the list from the head node, moving to the next node each time
• Output the data of the current node
• Continue until reaching the tail node, ending the traversal

// Forward traverse the doubly linked list
void traverseForward(DNode* head) {
    // Start traversing from the head node
    // Continue traversing while cur is not null, moving to the next node each time
    for (DNode* cur = head; cur; cur = cur->next)
        // Output the data of the current node
        cout << cur->data << " ";
    // New line
    cout << endl;
}

2.5.2 Backward Traversal

Backward traversing the list mainly involves the following steps:

1. Check if the List is Empty

• If the list is empty, return directly without performing the traversal operation

Traverse the List

• Start traversing the list from the tail node, moving to the previous node each time
• Output the data of the current node
• Continue until reaching the head node, ending the traversal

// Backward traverse the doubly linked list
void traverseBackward(DNode* tail) {
    // Start traversing from the tail node
    // Continue traversing while cur is not null, moving to the previous node each time
    for (DNode* cur = tail; cur; cur = cur->prev)
        // Output the data of the current node
        cout << cur->data << " ";
    // New line
    cout << endl;
}

2.6 Reversing the List

Reversing the list mainly involves the following steps:

1. Check if the List is Empty

• If the list is empty, return directly without performing the reversal operation

Reverse the List

• Start traversing the list from the head node, moving to the next node each time
• Swap the <span>prev</span> and <span>next</span> pointers of the current node
• Continue until reaching the tail node, ending the traversal
• Finally, return the new head node

// Reverse the doubly linked list
// @param head: Head pointer of the doubly linked list
// @return: Head pointer of the reversed list
DNode* reverseDList(DNode* head) {
    DNode* cur = head;     // Current node being traversed
    DNode* tmp = nullptr;  // Temporary variable to hold the previous pointer

    // Traverse the list, swapping each node's prev and next pointers
    while (cur) {
        // First save the current node's prev pointer (original predecessor of the list)
        tmp = cur->prev;
        // Swap the current node's prev and next pointers
        cur->prev = cur->next;
        cur->next = tmp;
        // Move to the next node (since prev and next have been swapped, use cur->prev)
        cur = cur->prev;
    }

    // During the reversal, each node's prev and next have been swapped.
    // When the loop ends, cur is null, and tmp is the previous node of the tail node (original second to last node)
    // Since prev and next have been swapped, tmp->prev actually points to the last node of the original list (i.e., the new head node).
    // Therefore, we need to assign head to tmp->prev to get the new head node after reversal.
    if (tmp) {
        head = tmp->prev;
    }
    return head;
}

3. Summary

• The insertion/deletion of doubly linked lists can be completed when the node pointer is known, while searching remains .
• Maintaining an additional <span>prev</span> pointer increases space usage, but provides stronger functionality.
• Backward traversal, deleting the tail node, and other operations are more convenient than singly linked lists.

4. Complete Test Code

// Example usage
int main() {
    // Create a vector containing integers from 1 to 5
    vector<int> vals = {1, 2, 3, 4, 5};
    // Create a doubly linked list from the vector
    DNode* head = createDList(vals);
    // Forward traverse the list and output
    traverseForward(head);
    // Backward traverse the list and output (starting from the last node)
    traverseBackward(head->next->next->next->next);

    // Insert a node with value 6 at position 2
    insertAtPosition(head, 2, 6);
    // Forward traverse the list and output
    traverseForward(head);

    // Insert a node with value 0 at the head
    insertAtPosition(head, 0, 0);
    // Forward traverse the list and output
    traverseForward(head);

    // Insert a node with value 7 after the 3rd node (value 3)
    insertAfter(head->next->next, 7);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the head node
    deleteAtPosition(head, 0);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the middle node (originally the 3rd node, now the 2nd node, value 3)
    deleteAtPosition(head, 2);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the node with value 7
    deleteNode(head, 7);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the node with value 6
    deleteNode(head, 6);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the node with value 1
    deleteNode(head, 1);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the node with value 0
    deleteNode(head, 0);
    // Forward traverse the list and output
    traverseForward(head);

    // Delete the node with value 5
    deleteNode(head, 5);
    // Forward traverse the list and output
    traverseForward(head);

    // Insert a node with value 1 at the head
    insertAtPosition(head, 0, 1);
    // Forward traverse the list and output
    traverseForward(head);

    // Insert a node with value 5 at position 4
    insertAtPosition(head, 4, 5);
    // Forward traverse the list and output
    traverseForward(head);

    // Reverse the list
    head = reverseDList(head);
    // Forward traverse the list and output
    traverseForward(head);

    // End of program
    return 0;
}

Example Output:

1 2 3 4 5 
5 4 3 2 1
1 2 6 3 4 5
0 1 2 6 3 4 5
0 1 2 7 6 3 4 5
1 2 7 6 3 4 5
1 2 6 3 4 5
1 2 6 3 4 5
1 2 3 4 5
2 3 4 5
2 3 4 5
2 3 4
1 2 3 4
1 2 3 4 5
5 4 3 2 1

Please open in the WeChat client

For GESP exam outlines, real questions explanations, knowledge expansion, and practice lists, see:

[Top] [GESP] C++ Certification Learning Resource Summary

“luogu-” series problems can be evaluated online in the Luogu Problem Bank.

“bcqm-” series problems can be evaluated online in the Programming Enlightenment Problem Bank.