双向链表
不带尾指针实现的双向链表
/**
* @file simple_double_linked_list.cpp
* @author icecreamovo (www.icecreamovo.top)
* @brief 双向链表（不带尾指针）的基本实现
* @version 0.1
* @date 2023-04-19
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
#define N 100
using namespace std;
typedef struct Node
{
int data;
struct Node *prior;
struct Node *next;
} Node, *LinkList;
/**
* 此函数通过创建一个新节点并将其 prior 和 next 指针设置为 NULL 来初始化双向链表。
*
* @param L 对 LinkList 类型指针的引用，它是 struct Node* 的类型定义
*
* @return 一个布尔值。如果链表初始化成功则返回 true，如果失败则返回 false（即第一个节点的内存分配失败）。
*/
bool initList(LinkList &list)
{
list = new Node;
if (list == NULL)
{
return false;
}
list->prior = NULL;
list->next = NULL;
return true;
}
/**
* 此函数在双向链表的末尾插入一个具有给定值的新节点。
*
* @param list 参数“list”是对 LinkList 的引用，它很可能是使用节点实现的链表数据结构。
* @param val 要插入到链表中的值。
*
* @return 一个布尔值。如果插入具有给定值的新节点成功，则返回 true，如果失败则返回 false（例如，如果没有足够的内存来分配新节点）。
*/
bool insert(LinkList &list, int val)
{
Node *p = list;
while (p->next != NULL)
{
p = p->next;
}
Node *q = new Node;
if (q == NULL)
{
return false;
}
q->data = val;
q->next = NULL;
q->prior = p;
p->next = q;
return true;
}
/**
* 此函数在双向链表的指定位置插入一个具有给定值的新节点。
*
* @param list 对 LinkList 的引用，它是一个链表数据结构。
* @param pos 应在链表中插入值为“val”的新节点的位置。
* @param val 要插入到链表中的值。
*
* @return 一个布尔值，true 或 false，取决于插入是否成功。
*/
bool insert(LinkList &list, int pos, int val)
{
if (pos < 0)
{
cout << "插入位置不合法" << endl;
return false;
}
Node *p = list;
for (int i = 0; i < pos; i++)
{
p = p->next;
if (p == NULL)
{
cout << "插入位置不合法" << endl;
return false;
}
}
Node *q = new Node;
if (q == NULL)
{
return false;
}
q->data = val;
q->next = p->next;
q->prior = p;
p->next = q;
if (q->next != NULL)
{
q->next->prior = q;
}
return true;
}
void printList(LinkList list)
{
Node *p = list->next;
while (p != NULL)
{
if (p->next != NULL)
{
cout << p->data << "->";
}
else
{
cout << p->data;
}
p = p->next;
}
cout << endl;
}
int main()
{
LinkList list;
initList(list);
insert(list, 1);
insert(list, 3);
insert(list, 2);
insert(list, 5);
insert(list, 4);
printList(list);
system("pause");
return 0;
}
```带尾指针实现的双向链表
/**
* @file simple_double_linked_list(2).cpp
* @author icecreamovo (www.icecreamovo.top)
* @brief 双向链表（带尾指针）的基本实现
* @version 0.1
* @date 2023-04-20
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
#define N 100
using namespace std;
/**
* 这是具有整数数据的双向链表节点的结构定义。
* @property {int} data - 一个整数值，表示存储在节点中的数据。
* @property prior - “prior”属性是指向双向链表中前一个节点的指针。它允许在两个方向上进行高效遍历。
* @property next - Node 结构的“next”属性是指向链表中下一个节点的指针。它用于通过指向列表中的下一个节点来遍历链表。如果当前节点是列表中的最后一个节点，则“下一个”属性将设置为
*/
typedef struct Node
{
int data;
struct Node *prior;
struct Node *next;
} Node;
/**
* DoubleLinkedList 结构是一种数据结构，包含用于双向链表实现的头指针和尾指针以及长度变量。
* @property {Node} head - 指向双链表中第一个节点的指针。
* @property {Node} tail - DoubleLinkedList 结构中的“tail”属性是指向链表中最后一个节点的指针。它用于跟踪列表的末尾并轻松地将新节点添加到末尾。
* @property {int} length - DoubleLinkedList 结构中的 length 属性表示链表中的节点数。它用于跟踪列表的大小，并且可以在列表中添加或删除节点时进行更新。
*/
typedef struct DoubleLinkedList
{
Node *head;
Node *tail;
int length;
} DoubleLinkedList;
/**
* 该函数使用头节点初始化双向链表。
*
* @param list 指向 DoubleLinkedList 类型指针的指针，这意味着它是对 DoubleLinkedList 指针地址的引用。这允许函数修改作为参数传递的原始指针。
*/
void init(DoubleLinkedList *&list)
{
// 初始化带头指针的双向链表
list->head = (Node *)malloc(sizeof(Node));
list->tail = (Node *)malloc(sizeof(Node));
list->head->next = list->tail;
list->tail->prior = list->head;
list->head->prior = NULL;
list->tail->next = NULL;
list->length = 0;
}
/**
* 此函数在双向链表的末尾插入一个具有给定值的新节点。
*
* @param list 指向 DoubleLinkedList 结构的指针，它包含有关链表的信息，例如它的长度和指向头节点和尾节点的指针。
* @param val 我们要插入双向链表的值。
*
* @return 一个布尔值，true 或 false，取决于插入操作是否成功。
*/
bool insert(DoubleLinkedList *&list, int val)
{
Node *p = list->tail->prior;
Node *q = new Node;
if (q == NULL)
{
return false;
}
q->data = val;
q->next = list->tail;
q->prior = p;
p->next = q;
list->tail->prior = q;
list->length++;
return true;
}
void printList(DoubleLinkedList *&list, int start = 0)
{
if (start < 0 || start >= list->length)
{
cout << "Invalid start index!" << endl;
return;
}
Node *p = list->head->next;
for (int i = 0; i < start; i++)
{
p = p->next;
}
while (p != list->tail)
{
if (p->next != list->tail)
{
cout << p->data << "->";
}
else
{
cout << p->data;
}
p = p->next;
}
cout << endl;
}
int main()
{
srand(time(NULL));
DoubleLinkedList *list = new DoubleLinkedList;
init(list);
for (int i = 0; i < 10; i++)
{
int val = rand() % 100;
cout << "Insert " << val << " into list." << endl;
insert(list, val);
}
printList(list);
system("pause");
return 0;
}Last updated