迹忆客 专注技术分享

双向链接列表是线性数据结构。它是定义为节点的对象的集合。但是与链接列表不同，该节点有两个指针，一个是前一个指针，另一个是下一个指针。就像链表节点存储在内存中的随机位置中，而不是存储在连续位置中一样。

双向链接列表 vs 链接列表

1. 双向链接列表允许我们在向前和向后的方向上遍历链接列表，但这是以 prev 指针为每个节点所需的额外空间为代价的。
2. 在双向链表中插入元素非常容易，因为我们不必维护多个指针或遍历链表来查找先前的指针，但是与链表相比，我们必须修改更多的指针。

双向链接列表遍历算法

前进方向

令 head 成为链接列表的第一个节点。

• 初始化 curr，指向链接列表的 head 节点。
• 虽然 curr 尚未到达列表的末尾，即 curr！=NULL，但请执行以下操作：
  • 打印存储在当前节点内的数据。
  • curr=curr->next;
  • 如果是最后一个节点，则存储为 tail，以方便向后遍历。

同样，我们可以通过从 tail 开始并将 curr 更改为 curr->prev 来进行向后遍历。

反方向

令 tail 为链表的最后一个节点。

• 初始化 curr，指向链接列表的 tail 节点。
• 虽然 curr 尚未到达列表的开头，即 curr!=NULL，但请执行以下操作：
  • 打印存储在当前节点内的数据。
  • curr = curr->上一个

双向链接列表插入

双向链接列表在插入元素时有 4 种情况，就像链表一样。

将节点插入 DLL push() 的开头

• 使用数据 x 和 prev 创建为 NULL 的新节点 temp。
• 将 temp->next 设置为 head，将 head->prev 设置为 temp，以在 head 之前插入 temp。
• 将 temp 设置为链接列表的开头。

在 Append()DLL 末尾插入节点

• 创建一个新节点 temp，其数据为 x，并且其 prev 为 NULL。
• 初始化指向 head 的 tail。
• 如果链接列表为空，则将 temp 设置为链接列表的 head，然后返回。
• 否则，迭代链接列表的末尾，使 tail->next！=NULL，以便你到达最后一个元素
• 将 tail->next 设置为 temp，将 temp->prev 设置为 tail。

在给定节点 insertBefore() 之前插入节点

• 如果 next==NULL，则返回；
• 用数据 x 创建一个新节点 curr。
• 将 curr->prev 设置为 next->prev，以在 next 之前添加一个新节点，将 next->prev 设置为 curr，以建立后向链接。
• 将 curr->next 设置为 next，最后检查 curr->prev 是否为 NULL。
• 如果不是 NULL，则将 curr->prev->next 设置为 curr 以完成插入，否则 curr 是链接列表的第一个节点。将 head 设置为 curr。

在给定节点 insertAfter() 之后插入节点

• 如果 prev==NULL，则返回；
• 用数据 x 创建一个新节点 curr。
• 将 curr->next 设置为 prev->next，以在 prev 之后添加一个新节点，并将 prev->next 设置为 curr，以建立前向链接。
• 将 curr->prev 设置为 prev，最后检查 curr->next 是否为 NULL。如果不是 NULL，则将 curr->next->prev 设置为 curr 以完成插入。

双向链接列表插入过程

1. 将节点插入 DLL push() 的开头
2. 在 Append() DLL 末尾插入节点
3. 在给定节点 insertBefore() 之前插入节点
4. 在给定节点 insertAfter() 之后插入节点

双向链接列表遍历和插入实现

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

void push(Node** head, int x)
{
    Node* curr = new Node();
    curr->data = x;
    curr->next = (*head);
    curr->prev = NULL;
    if ((*head) != NULL)
        (*head)->prev = curr;
    (*head) = curr;
}
void insertAfter(Node* prev, int x)
{
    if (prev == NULL)
    {
        cout << "the given previous node cannot be NULL";
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->next = prev->next;
    prev->next = curr;
    curr->prev = prev;
    if (curr->next != NULL)
        curr->next->prev = curr;
}

void insertBefore(struct Node** head, struct Node* next, int x)
{    if (next == NULL) {
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->prev = next->prev;
    next->prev = curr;
    curr->next = next;
    if (curr->prev != NULL)
        curr->prev->next = curr;
    else
        (*head) = curr;
}

void append(Node** head, int x)
{
    Node* curr = new Node();
    Node* tail = *head;
    curr->data = x;
    curr->next = NULL;
    if (*head == NULL)
    {
        curr->prev = NULL;
        *head = curr;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = curr;
    curr->prev = tail;
    return;
}

void printList(Node* node)
{
    Node* tail = NULL;
    cout << "Forward Traversal:";
    while (node != NULL)
    {
        cout << " " << node->data << " ";
        tail = node;
        node = node->next;
    }

    cout << "\nReverse Traversal:";
    while (tail != NULL)
    {
        cout << " " << tail->data << " ";
        tail = tail->prev;
    }
    cout << "\n";
}

int main()
{

    Node* head = NULL;
    append(&head, 6);
    push(&head, 7);
    push(&head, 1);
    append(&head, 4);
    printList(head);
    insertAfter(head->next, 8);
    insertBefore(&head, head->next->next, 3);
    printList(head);
    return 0;
}

双向链接列表遍历和插入算法的复杂性

遍历

• 平均情况

要遍历完整的双向链表，我们必须访问每个节点。因此，如果它具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。

• 最坏情况

最差的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。

遍历算法的空间复杂度为 O(1)，因为除 curr 指针外不需要其他空间。

插入方式

• 平均情况

在所有 4 情况下插入一个元素最多需要 4 链接更改，因此插入的时间复杂度为 O(1)。

• 最佳情况

最佳情况下的时间复杂度是 O(1)。它与平均情况下的时间复杂度相同。

• 最坏情况

最坏情况下的时间复杂度是 O(1)。它与最佳情况下的时间复杂度相同。

对于所有 4 种插入方式，插入算法的空间复杂度为 O(1)。