GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-4) Linked List - Doubly Circular Linked List

In the official GESP C++ Level 5 exam outline, there are a total of 9 key points. This article analyzes and introduces the 3 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 list, doubly linked list, and circular linked list.

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 List – Singly Linked List
【GESP】C++ Level 5 Exam Outline Knowledge Points Review, (3-2) Linked List – Doubly Linked List

【GESP】C++ Level 5 Exam Outline Knowledge Points Review, (3-3) Linked List – Singly Circular Linked List

1. Concepts and Characteristics

Doubly Circular Linked List (DCLL) is a combination of doubly linked list and circular linked list:

Each node contains a data field and two pointer fields:

prev → points to the predecessor node
next → points to the successor node

The linked list connects head and tail:

head->prev points to the last node
tail->next points to the head node

Characteristics:

Bidirectional traversal (freely move forward and backward).
Head and tail are connected (forming a closed loop, no need to check for empty tail node).
More flexible insertion and deletion, especially when operating at the head and tail without special handling.

2. Logical Structure Diagram

Assuming the linked list contains 3 nodes: A, B, C

      ┌─────┐      ┌─────┐      ┌─────┐
      │  A  │ &lt;--&gt; │  B  │ &lt;--&gt; │  C  │
      └─────┘      └─────┘      └─────┘
        ↑ ↓                         ↑ ↓
          └────────────►────────────┘ 
        └───────────────◄─────────────┘

A.prev = C
C.next = A

3. Basic Operations

3.1 Node Structure Definition

struct Node {
    // Node data field
    int data;
    // Pointer to predecessor node
    Node* prev;
    // Pointer to successor node
    Node* next;
    // Constructor to initialize node
    // @param val: Node data value
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3.2 Creating a Doubly Circular Linked List

The main steps to create a doubly circular linked list:

Check if the input array is empty:

If the array is empty, return a null pointer directly.

Create the head node:

Initialize the head node, with the data field set to the first element of the array.

Initialize the tail pointer:

The tail pointer points to the head node, and subsequent nodes will connect here.

Traverse the array to create nodes:

Starting from the second element of the array, create new nodes.
The tail node’s next points to the new node.
The new node’s prev points to the current tail node.
Update the tail node to the new node.

Connect head and tail:

The head node’s prev points to the tail node, and the tail node’s next points to the head node, forming a loop.

Return the head pointer:

After completing the linked list creation, return the head node pointer.

/**
 * Create a doubly circular linked list (Doubly Circular Linked List)
 * @param arr Input integer array used to initialize the data field of the linked list nodes
 * @return Returns the head pointer of the linked list, or nullptr if the array is empty
 */
Node* createDCLL(std::vector&lt;int&gt; arr) {
    // If the input array is empty, return a null pointer directly
    if (arr.empty()) {
        return nullptr;
    }

    // Create the head node and initialize the tail pointer
    Node* head = new Node(arr[0]);
    Node* tail = head;

    // Create subsequent nodes and connect the pointers
    for (int i = 1; i &lt; arr.size(); i++) {
        Node* newNode = new Node(arr[i]); // New node
        tail-&gt;next = newNode;             // Current tail node's next points to the new node
        newNode-&gt;prev = tail;             // New node's prev points to the current tail node
        tail = newNode;                   // Update the tail node to the new node
    }

    // Connect the head and tail to form a loop
    // Head node's prev points to the tail node
    head-&gt;prev = tail;  
    // Tail node's next points to the head node
    tail-&gt;next = head;

    // Return the head pointer
    return head;
}

3.3 Inserting Nodes

3.3.1 Insert at a Given Position

The main steps to insert a new node at a specified position in a doubly circular linked list:

Create a new node:

Initialize the new node, with the data field set to the specified value.

Handle head node insertion (pos == 0):

The new node’s next points to the current head node.
The new node’s prev points to the current head node’s prev (i.e., the original tail node).
The original head node’s prev‘s next points to the new node.
Update the head node’s prev to the new node.
Update the head pointer to the new node.

Traverse to the specified position:

Start traversing from the head node, moving pos - 1 times to reach the node before the insertion position.
If traversing reaches nullptr, it indicates an invalid position, return directly.

Insert the new node:

The new node’s next points to the next node at the current position.
The new node’s prev points to the current node.
If the next node at the current position exists, update its prev to the new node.
Update the next node at the current position to the new node.

/**
 * Insert a new node at the specified position in the doubly circular linked list
 * @param head Reference to the head pointer of the doubly circular linked list, used to modify the head pointer
 * @param pos The position to insert (starting from 0)
 * @param val The data value of the node to be inserted
 */
void insertAtPosition(Node*&amp; head, int pos, int val) {
    // Create a new node
    Node* newNode = new Node(val);

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

    Node* cur = head;  // Start traversing from the head node
    for (int i = 0; i &lt; pos - 1 &amp;&amp; cur; ++i) {
        cur = cur-&gt;next;
    }

    // If the position to insert is found (cur is not null)
    if (cur) {
        newNode-&gt;next = cur-&gt;next;  // New node's next points to the next node at the current position
        newNode-&gt;prev = cur;  // New node's prev points to the current node
        if (cur-&gt;next) {  // If the next node at the current position exists
            cur-&gt;next-&gt;prev = newNode;  // The next node's prev points to the new node
        }
        cur-&gt;next = newNode;  // Current node's next points to the new node
    }
}

3.3.2 Insert After a Specified Node

The main steps to insert a new node after a specified node in a doubly circular linked list:

Create a new node:

Initialize the new node, with the data field set to the specified value.

Handle the case where the specified node is null:

If the specified node is null, return directly.

Insert the new node:

The new node’s next points to the next node of the specified node.
The new node’s prev points to the specified node.
The next node of the specified node’s prev points to the new node.
The specified node’s next points to the new node.

/**
 * Insert a new node after the specified node in the doubly circular linked list
 * @param head Reference to the head pointer of the doubly circular linked list, used to modify the head pointer
 * @param pos Pointer to the node after which to insert the new node
 * @param val The data value of the node to be inserted
 */
void insertAfter(Node*&amp; head, Node* pos, int val) {
    // If the specified node is null, return directly
    if (!pos) {
        return;
    }

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

    // New node's next points to the specified node's next
    newNode-&gt;next = pos-&gt;next;

    // New node's prev points to the specified node
    newNode-&gt;prev = pos;

    // The specified node's next's prev points to the new node
    pos-&gt;next-&gt;prev = newNode;

    // The specified node's next points to the new node
    pos-&gt;next = newNode;
}

3.4 Deleting Nodes

3.4.1 Delete at a Specified Position

The core steps to delete a node at a specified position in a doubly circular linked list:

Check for an empty list:

Check if the linked list is empty; if so, return directly.

Handle head node deletion:

Find the tail node (head->prev).
Update the tail node’s next and the new head node’s prev pointers.
Free the memory of the original head node.
Update the head pointer.
Update the new head node’s prev to the original head node’s prev (i.e., the original tail node).

Non-head node deletion:

Traverse to locate the node before the target position.
Check if the position is valid.

Execute the deletion operation:

Temporarily store the node to be deleted.
Point the current node’s next to the next node of the node to be deleted.
Point the next node of the node to be deleted’s prev to the current node.
Free the memory of the target node.

/**
 * Delete the node at the specified position in the doubly circular linked list
 * @param head Reference to the head pointer of the doubly circular linked list, used to modify the head pointer
 * @param pos The position to delete (starting from 0)
 */
void deleteAtPosition(Node*&amp; head, int pos) {
    // If the list is empty, return directly
    if (!head) {
        return;
    }

    // If the node to delete is the head node
    if (pos == 0) {
        // Find the tail node
        Node* tail = head-&gt;prev;
        // Tail node's next points to the head node's next
        tail-&gt;next = head-&gt;next;
        // Free the head node
        delete head;
        // Update the head pointer to the next node
        head = tail-&gt;next;
        // Update the new head node's prev to the original head node's prev (i.e., the original tail node)
        head-&gt;prev = tail;
        return;
    }

    // Traverse to the specified position
    Node* cur = head;
    for (int i = 0; i &lt; pos - 1 &amp;&amp; cur; ++i) {
        cur = cur-&gt;next;
    }

    // If the position to delete is found (cur is not null)
    if (cur) {
        // Save the pointer to the node to delete
        Node* toDelete = cur-&gt;next;
        // Current node points to the next node
        cur-&gt;next = toDelete-&gt;next;
        // Free the memory of the node to delete
        delete toDelete;
        // Update the current node's prev to point to the node to delete's prev
        cur-&gt;next-&gt;prev = cur;
        return;
    }
}

3.4.2 Delete Nodes with a Specified Value

The main steps to delete nodes with a specified value in a doubly circular linked list:

Check for an empty list:

Check if the linked list is empty; if so, return directly.

Traverse the linked list:

Use the cur pointer to traverse the linked list.
Use the prev pointer to record the previous node.
Use a do-while loop to ensure a full traversal.

Handle head node deletion:

Find the tail node (head->prev).
Update the head pointer to the next node.
Update the tail node’s next to point to the new head node.
Free the memory of the original head node.
Update the new head node’s prev to the original tail node.

Non-head node deletion:

Update the previous node’s next to point to the current node’s next.
Free the memory of the current node.
Update the next node’s prev to point to the previous node.
Move the pointer to the next node.

Continue traversing:

Update prev to the current node.
Move cur to the next node.

/**
 * Delete all nodes with the specified value in the doubly circular linked list
 * @param head Reference to the head pointer of the doubly circular linked list, used to modify the head pointer
 * @param val The value of the nodes to be deleted
 */
void deleteNode(Node*&amp; head, int val) {
    // If the list is empty, return directly
    if (!head) {
        return;
    }

    // Pointer for traversing the linked list
    Node* cur = head;
    // Pointer for saving the previous node
    Node* prev = nullptr;

    do {
        // If the current node's value equals the given value
        if (cur-&gt;data == val) {
            // If the current node is the head node
            if (cur == head) {
                // Find the tail node
                Node* tail = head-&gt;prev;
                // Update the head node to the next node
                head = cur-&gt;next;
                // Update the tail node's next to point to the new head node
                tail-&gt;next = head;
                // Free the original head node
                delete cur;
                // Update the new head node's prev to the original tail node
                head-&gt;prev = tail;
                cur = head;
            } else {
                // Point the previous node's next to the current node's next
                prev-&gt;next = cur-&gt;next;
                // Free the current node
                delete cur;
                // Update the previous node's next's prev to the previous node
                prev-&gt;next-&gt;prev = prev;
                // Move to the next node
                cur = prev-&gt;next;
            }
        } else {
            // Move the previous node pointer
            prev = cur;
            // Move to the next node
            cur = cur-&gt;next;
        }
    } while (cur != head);
}

3.5 Forward Traversal

/**
 * Forward traverse the doubly circular linked list
 * @param head The head pointer of the doubly circular linked list
 */
void printForward(Node* head) {
    // If the list is empty, return directly
    if (!head) {
        return;
    }
    
    // Start traversing from the head node
    Node* p = head;
    
    // Use a do-while loop to ensure at least one execution
    // Until returning to the head node again
    do {
        // Print the current node's data
        std::cout &lt;&lt; p-&gt;data &lt;&lt; " ";
        // Move to the next node
        p = p-&gt;next;
    } while (p != head);
    
    // Print a newline
    std::cout &lt;&lt; std::endl;
}

3.6 Backward Traversal

/**
 * Backward traverse the doubly circular linked list
 * @param head The head pointer of the doubly circular linked list
 */
void printBackward(Node* head) {
    // If the list is empty, return directly
    if (!head) {
        return;
    }
    
    // Start traversing from the tail node (the head node's prev points to the tail node)
    Node* p = head-&gt;prev;
    // Save the tail node position for traversal end judgment
    Node* tail = p;
    
    // Use a do-while loop to ensure at least one execution
    // Until returning to the tail node again
    do {
        // Print the current node's data
        std::cout &lt;&lt; p-&gt;data &lt;&lt; " ";
        // Move to the previous node
        p = p-&gt;prev;
    } while (p != tail);
    
    // Print a newline
    std::cout &lt;&lt; std::endl;
}

3.7 Reversing the Doubly Circular Linked List

The main steps to reverse a doubly circular linked list:

Check for an empty list:

Check if the linked list is empty; if so, return directly.

Check for a single node:

Check if the linked list has only one node; if so, return directly.

Traverse the linked list:

Use the cur pointer to traverse the linked list.
Use the prev pointer to record the previous node.
Use a do-while loop to ensure a full traversal.

Reverse the pointers:

Reverse the current node’s next and prev pointers.
Move the prev pointer to the current node.
Move the cur pointer to the next node.

Update the head pointer:

After traversal ends, update the head pointer to prev.

/**
 * Reverse the doubly circular linked list
 * @param head Reference to the head pointer of the doubly circular linked list, used to modify the head pointer
 */
void reverse(Node*&amp; head) {
    // If the list is empty or has only one node, return directly
    if (!head || head-&gt;next == head) {
        return;
    }

    // Pointer for traversing the linked list
    Node* cur = head;
    // Pointer for saving the previous node
    Node* prev = head-&gt;prev;

    do {
        // Save the current node's next node
        Node* next = cur-&gt;next;
        // Reverse the current node's pointers
        cur-&gt;next = prev;
        cur-&gt;prev = next;
        // Move the previous node pointer
        prev = cur;
        // Move to the next node
        cur = next;
    } while (cur != head);

    // Update the head pointer
    head = prev;
}

4. Complete Test Code

int main() {
    // Create a doubly circular linked list containing integers from 1 to 5
    std::vector&lt;int&gt; arr = {1, 2, 3, 4, 5};
    Node* head = createDCLL(arr);

    // Forward traverse the list and output
    printForward(head);

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

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

    // Insert a node with value 7 at the last position
    insertAtPosition(head, 7, 7);
    // Forward traverse the list and output again
    printForward(head);

    // Insert a node with value 8 after the second node (value 2)
    insertAfter(head, head-&gt;next, 8);
    // Forward traverse the list and output again
    printForward(head);

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

    // Delete the third node (originally value 3)
    deleteAtPosition(head, 2);
    // Forward traverse the list and output again
    printForward(head);

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

    // Backward traverse the list and output (starting from the last node)
    printBackward(head);

    // Delete the node with value 8
    deleteNode(head, 8);
    // Backward traverse the list and output again
    printBackward(head);

    // Delete the node with value 7
    deleteNode(head, 7);
    // Backward traverse the list and output again
    printBackward(head);

    // Delete the node with value 4
    deleteNode(head, 4);
    // Backward traverse the list and output again
    printBackward(head);

    // Insert a node with value 4 at the second position
    // Insert a node with value 1 at the head
    insertAtPosition(head, 2, 4);
    insertAtPosition(head, 0, 1);

    // Reverse the list
    reverse(head);

    // Forward traverse the list and output again
    printForward(head);

    // Backward traverse the list and output again (starting from the last node)
    printBackward(head);

    return 0;
}

The output is as follows:

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

5. Linked List Summary

So far, the third linked list-related content in the GESP Level 5 exam outline has been organized, summarized as follows:

Linked List Type	Can Traverse Forward	Can Traverse Backward	Is Head and Tail Connected	Insertion/Deletion Complexity	Applicable Scenarios
Singly Linked List	✅	❌	❌	(known node pointer) (unknown node pointer, traverse to find position)	Basic data structure, simple scenarios
Doubly Linked List	✅	✅	❌	(known node pointer) (unknown node pointer, traverse to find position)	Frequent forward and backward operations, such as browser history
Singly Circular Linked List	✅	❌	✅	(known node pointer) (unknown node pointer, traverse to find position)	Circular scheduling, polling mechanisms, looping playback, etc.
Doubly Circular Linked List	✅	✅	✅	(known node pointer) (unknown node pointer, traverse to find position)	Complex scheduling systems, music playback loops

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

[Pinned] [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.

GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-4) Linked List – Doubly Circular Linked List

1. Concepts and Characteristics

2. Logical Structure Diagram

3. Basic Operations

3.1 Node Structure Definition

3.2 Creating a Doubly Circular Linked List

3.3 Inserting Nodes

3.3.1 Insert at a Given Position

3.3.2 Insert After a Specified Node

3.4 Deleting Nodes

3.4.1 Delete at a Specified Position

3.4.2 Delete Nodes with a Specified Value

3.5 Forward Traversal

3.6 Backward Traversal

3.7 Reversing the Doubly Circular Linked List

4. Complete Test Code

5. Linked List Summary

Leave a Comment Cancel reply

1. Concepts and Characteristics

2. Logical Structure Diagram

3. Basic Operations

3.1 Node Structure Definition

3.2 Creating a Doubly Circular Linked List

3.3 Inserting Nodes

3.3.1 Insert at a Given Position

3.3.2 Insert After a Specified Node

3.4 Deleting Nodes

3.4.1 Delete at a Specified Position

3.4.2 Delete Nodes with a Specified Value

3.5 Forward Traversal

3.6 Backward Traversal

3.7 Reversing the Doubly Circular Linked List

4. Complete Test Code

5. Linked List Summary

Related posts

Leave a Comment Cancel reply