双向链接列表

Harshit Jindal 2023年10月12日
  1. 双向链接列表 vs 链接列表
  2. 双向链接列表遍历算法
  3. 双向链接列表插入
  4. 双向链接列表插入插图
  5. 双向链接列表遍历和插入实现
  6. 双向链接列表遍历和插入算法的复杂性
双向链接列表

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

双向链接列表 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() 的开头

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

Append()DLL 末尾插入节点

  • 创建一个新节点 temp,其数据为 x,并且其 prevNULL
  • 初始化指向 headtail
  • 如果链接列表为空,则将 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 以完成插入。

双向链接列表插入插图

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

Append()DLL 末尾插入节点

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

在给定节点 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)

作者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Data Structure