双向链表原来是这样实现的！

前言

“我会定期分享我的学习经验，也欢迎大家留言和交流，让我们共同学习和进步！感谢大家的支持，让我们一起开启这段充满技术乐趣的旅程吧！”

---

1. 双向链表的结构

数据结构在计算机科学中扮演着关键角色，其中双链表作为一种强大的动态数据结构在实际编程中发挥着重要作用。在本文中，我们将深入研究双链表的定义、结构、基本操作，以及它在不同应用场景下的性能表现。

2. 双链表的定义和结构

双链表是一种由节点组成的数据结构，每个节点都包含一个数据域和两个指针域，分别指向前一个节点和后一个节点。这种结构为双链表带来了高度的灵活性，使其适用于各种复杂的编程场景。

3. 定义结构体(ListNode)

注意下述代码皆是：
在SList.h头文件中定义函数
在SList.c文件中实现函数
在Test.c文件中函数测试

在SList.h头文件中:

typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDataType val;
}ListNode;
1
2
3
4
5
6
7

---

2.创建返回链表的头结点CreateList

在实现下面的初始化函数之前，还需要一个函数来开辟空间给新的节。
SList.c文件中:

函数实现:

// 创建返回链表的头结点.
ListNode* CreateList(LTDataType x)
{
  // 分配新节点的内存
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  // 检查内存分配是否成功
  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  // 初始化节点的值和指针
  newNode->val = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

3.初始化双向链表ListCreate

SeqList.h文件中:

定义函数：

SList.c文件中:

实现函数：

// 初始化双向链表
ListNode* ListCreate(ListNode* pHead)
{
  // 创建哨兵节点
  pHead = CreateList(-1);
  pHead->next = pHead;
  pHead->prev = pHead;
  return pHead;
}
1
2
3
4
5
6
7
8
9

---

4. 双向链表打印(ListPrint)

SeqList.h文件中

定义函数：

SList.c文件中

实现函数：

// 打印双向链表
void ListPrint(ListNode* pHead)
{
  assert(pHead);
  ListNode* cur = pHead->next;
  printf("哨兵位<=>");

  // 遍历链表并打印每个节点的值
  while (cur != pHead)
  {
    printf("%d<=>", cur->val);
    cur = cur->next;
  }

  printf("哨兵位\n\n\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

5. 尾插函数 (ListPopBack)

定义函数：

实现函数：

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* tail = pHead->prev;
  ListNode* newNode = CreateList(x);

  // 将新节点插入到尾节点之后
  tail->next = newNode;
  newNode->prev = tail;
  newNode->next = pHead;
  pHead->prev = newNode;
  //如果实现了pos前面插入，尾插可以改为在phead前面插入，即尾插ListInsert(pHead, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

函数测试：

void Test1()
{
  printf("尾插测试:\n");
  ListNode* plist = ListCreate();
  ListPushBack(plist, 1);
  ListPushBack(plist, 2);
  ListPushBack(plist, 3);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9

运行结果：

---

6. 头插函数 (ListPushFront)

定义函数：

实现函数：

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* newNode = CreateList(x);
  ListNode* fast = pHead->next;

  // 将新节点插入到头节点之后
  pHead->next = newNode;
  newNode->next = fast;
  newNode->prev = pHead;
  fast->prev = newNode;
  //如果实现了pos前面插入，头插可以改为在phead->next前面插入，即头插ListInsert(pHead->next, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

函数测试：

void Test3()
{
  printf("头插测试:\n");
  ListNode* plist = ListCreate();
  ListPushFront(plist, 2);
  ListPushFront(plist, 4);
  ListPushBack(plist, 2);
  ListPushBack(plist, 4);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10

运行结果：

---

7. 尾删函数(ListPopBack)

定义函数：

实现函数：

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
  // 确保pHead不是空指针
  assert(pHead);

  // 确保链表不为空（至少有一个节点）
  assert(pHead->next != pHead);

  // 获取尾节点和其前一个节点
  ListNode* tail = pHead->prev;
  ListNode* tailPrev = tail->prev;

  // 释放尾节点占用的内存
  free(tail);

  // 更新指针以保持链表的完整性
  pHead->prev = tailPrev;
  tailPrev->next = pHead;
  //如果实现了pos位置删除，尾删可以改为在phead->prev删除，即尾删ListErase(pHead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

函数测试：

void Test2()
{
  printf("尾删测试:\n");
  ListNode* plist = ListCreate();
  ListPushBack(plist, 2);
  ListPushBack(plist, 4);
  ListPushBack(plist, 6);
  ListPopBack(plist);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10

运行结果：

---

8. 头删函数(ListPopFront)

定义函数：

实现函数：

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(pHead->prev != pHead);
  ListNode* first = pHead->next;
  ListNode* second = first->next;

  // 从头部删除节点
  pHead->next = second;
  second->prev = pHead;

  // 释放被删除的节点的内存
  free(first);
  first = NULL;
  //如果实现了pos位置删除，头删可以改为在phead->next删除，即头删ListErase(pHead->next);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

函数测试：

void Test4()
{
  printf("头删测试:\n");
  ListNode* plist = ListCreate();
  ListPushFront(plist, 2);
  ListPushFront(plist, 4);
  ListPushBack(plist, 2);
  ListPushBack(plist, 4);
  ListPopFront(plist);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10
11

运行结果：

9.双向链表查找函数 ListFind

定义函数：

用来确定pos位置，方便后面调用

实现函数：

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  assert(pHead);
  ListNode* cur = pHead->next;

  // 遍历链表查找值为x的节点
  while (cur != pHead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    cur = cur->next;
  }

  return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

函数测试：

void Test5()
{
  printf("查找测试:\n");
  ListNode* plist = ListCreate();
  ListPushFront(plist, 1);
  ListPushFront(plist, 2);
  ListPushFront(plist, 3);
  ListPushFront(plist, 4);
  ListNode* pos = ListFind(plist, 3);
  if(pos)
  {
    pos->val *= 100;	//找到了就乘以100
  }
  else
  {
    printf("没有找到\n\n\n");
  }
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果：

找到了就乘以100

---

10. 双向链表在pos的前面进行插入函数(ListInsert)

定义函数：

实现函数：

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* newNode = CreateList(x);
  ListNode* posPrev = pos->prev;

  // 在pos的前面插入新节点
  newNode->next = pos;
  pos->prev = newNode;
  newNode->prev = posPrev;
  posPrev->next = newNode;
 //如果在phead前面插入，即尾插ListInsert(pHead, x);
 //如果在phead->next前面插入，即头插ListInsert(pHead->next, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

函数测试：

void Test6()
{
  printf("pos前插入测试:\n");
  ListNode* plist = ListCreate();
  ListPushBack(plist, 2);
  ListPushBack(plist, 4);
  ListNode* pos = ListFind(plist, 4);
  ListInsert(pos, 3);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10

运行结果：

---

11.“删除pos位置”函数ListErase

定义函数：

实现函数：

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
  assert(pos);
  ListNode* posPrev = pos->prev;
  ListNode* posNext = pos->next;

  // 删除pos位置的节点
  posPrev->next = posNext;
  posNext->prev = posPrev;

  // 释放被删除的节点的内存
  free(pos);
  pos = NULL;
}

 //如果在phead->prev前面删除，即尾删ListErase(pHead->prev);
 //如果在phead->next前面删除，即头删ListErase(pHead->next);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

函数测试：

void Test7()
{
  printf("pos位置删除测试:\n");
  ListNode* plist = ListCreate();
  ListPushBack(plist, 2);
  ListPushBack(plist, 4);
  ListNode* pos = ListFind(plist, 4);
  ListErase(pos);
  ListPrint(plist);
}
1
2
3
4
5
6
7
8
9
10

运行结果：

---

12.销毁双向链表函数ListDestory

定义函数：

实现函数：

void ListDestroy(ListNode* pHead)
{
  ListNode* cur = pHead->next;

  // 释放每个节点的内存
  while (cur != pHead)
  {
    ListNode* next = cur->next;
    free(cur);
    cur = next;
  }

  // 释放哨兵节点的内存
  free(pHead);
  pHead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整的代码

大家可以参考，我上传到了gitee,希望对你有帮助！
点击这里：双向链表的实现（gitee）

应用场景

双链表在实际编程中有着广泛的应用，其中之一是在LRU缓存算法中。通过双链表，我们能够高效地管理缓存中的数据，提升程序性能

---

性能分析

了解双链表的性能是至关重要的：
插入和删除：O(1) - 在头部或尾部插入或删除节点的操作是常数时间复杂度。
遍历：O(n) - 遍历整个双链表的时间复杂度是线性的。
这种性能表现使得双链表在某些场景下比其他数据结构更为优越。

---

结语

通过本文的学习，希望你对双链表有了更深入的理解。双链表的灵活性使得它成为数据结构中的一颗璀璨明珠，在你的编程旅途中，它将成为你的得力助手。