JIYIK CN >

A circular doubly linked list is a combination of a circular linked list and a doubly linked list. Its two nodes are connected by a previous and next pointer. The next pointer of the last node points to the first node, and the previous pointer of the first node points to the last node. It can be traversed in both directions, either by jumping from the tail to the head or from the head to the tail. It is also used to implement advanced data structures such as Fibonacci heaps.

Circular doubly linked list traversal

We simply check the condition that the next node in the iteration is not head, and then traverse the circular doubly linked list, and then move out of the iteration tempfrom temp->nextor depending on forward/backward temp->prev.

Positive

Let headbe the first node of the linked list.

• Initializes a pointer headto a node in a linked list curr.
• While currthe end of the list has not been reached, i.e. curr->next! = head, do this:
  • Prints the data stored in the current node.
  • curr=curr->next;

Likewise, we can traverse backwards by tailstarting at and currchanging to .curr->prev

Reverse

Let tail(i.e. head->prev) be the last node of the linked list.

• Initializes a node currpointing to a linked list tail.
• While currhas not yet reached the head of the list, i.e. curr->prev!= tail, do this:
  • Prints the data stored in the current node.
  • curr = curr->上一个

Insertion into a circular doubly linked list

There are 3different insertion situations.

Insert an element at the beginning of a circular doubly linked list

• Create a node with the given data temp.
• Set temp->nextto headand temp->prevset to tailto insert between headand .tailtemp
• Set tail->nextand head->prevto tempto complete the insertion.
• Set headto tempto move head to the newly inserted element.

Insert an element at the end of a circular doubly linked list

• Create a node with the given data temp.
• If the list is empty, creates a node with the given data temp, points both temp->prevand temp->nextto itself, and sets it to headand returns it.
• Execute the steps you want to insert at the beginning, except the last step.

Inserting an element in the middle of a circular doubly linked list

Let Xbe the value of the node after which the element is to be inserted.

• Create a node with the given data temp.
• Initializes heada pointer to curr.
• Iterate until you find a node with 数据= X. Store its next node as 下一个.
• Set curr->nextto temp.
• Set temp->prevto curr, and temp->nextset to next.
• Finally, 下一个->上一个set it to 温度.

Insertion process of circular bidirectional linked list

1. Insert an element at the beginning of a circular doubly linked list
2. Insert an element at the end of a circular doubly linked list
3. Inserting an element in the middle of a circular doubly linked list

Circular bidirectional linked list traversal and insertion implementation

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int data;
    Node *next;
    Node *prev;
};
void insertEnd(Node** head, int value)
{
    if (*head == NULL)
    {
        Node* temp = new Node;
        temp->data = value;
        temp->next = temp->prev = temp;
        *head = temp;
        return;
    }
    Node *tail = (*head)->prev;
    Node* temp = new Node;
    temp->data = value;
    temp->next = *head;
    (*head)->prev = temp;
    temp->prev = tail;
    tail->next = temp;
}

void insertBegin(Node** head, int value)
{

    Node *tail = (*head)->prev;

    Node* temp = new Node;
    temp->data = value;
    temp->next = *head;
    temp->prev = tail;


    tail->next = (*head)->prev = temp;

    *head = temp;
}

void insertAfter(Node** head, int value1,
                 int value2)
{
    Node* temp = new Node;
    temp->data = value1;
    Node *curr = *head;
    while (curr->data != value2)
        curr = curr->next;
    Node *next = curr->next;

    curr->next = temp;
    temp->prev = curr;
    temp->next = next;
    next->prev = temp;
}


void printList(Node* head)
{
    Node *curr = head;

    printf("Forward Traversal:");
    while (curr->next != head)
    {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("%d ", curr->data);

    printf("\nBackward Traversal:");
    Node *tail = head->prev;
    curr = tail;
    while (curr->prev != tail)
    {
        printf("%d ", curr->data);
        curr = curr->prev;
    }
    printf("%d ", curr->data);
    cout << "\n";
}

int main()
{
    Node* head = NULL;
    insertEnd(&head, 2);
    insertBegin(&head, 1);
    insertEnd(&head, 4);
    printList(head);
    insertEnd(&head, 5);
    insertAfter(&head, 3, 2);
    printList(head);
    return 0;
}

Complexity of traversal and insertion algorithms for circular doubly linked lists

Traversal

• Average situation

To traverse the complete doubly linked list, we have to visit every node. If we have nnodes, the average case time complexity of the traversal is about O(n). The time complexity is about O(n).

• Best Case

The time complexity of the best case is O(n). It is the same as the time complexity of the average case.

• Worst case scenario

The worst case time complexity is O(n). It is the same as the best case time complexity.

The space complexity of the traversal algorithm is O(1), because currno additional space is required except for the pointer.

insert

• Average situation

To insert the element we want to insert at tailand , we need to change at most links, so the time complexity is . But to insert between the two, we may have to move nodes, so the time complexity is .head4O(1)n-1O(n)

• Best Case

For all 3cases, the best case time complexity is O(1).

• Worst case scenario

For the first two cases, the worst case time complexity is O(1), and for the third case O(n), it is the same as the average case time complexity.

For all 3 types of insertion, the space complexity of the insertion algorithm is O(1).