🔗链表复习笔记

userId_undefined
这里是无名的帅树
快乐小狗荣耀黄金超能小狗勇敢小狗

2026-10-17 11:30:47

发布于：广东

7阅读
0回复
0点赞

一、单链表

1. 结点定义

struct node {
    int data;       // 数据域：存储当前结点的值
    node *next;     // 指针域：存储下一个结点的地址
};

2. 建立单链表（尾插法）

node *head = new node;   // 创建头结点（不存数据，仅作为起点）
head->next = nullptr;    // 指针域初始化为空
node *tail = head;       // 尾指针指向头结点，此时头结点也是尾结点

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    node *p = new node;  // 动态申请新结点
    cin >> p->data;      // 数据域赋值
    p->next = nullptr;   // 指针域初始化为空

    tail->next = p;      // 尾结点链接新结点
    tail = p;            // 更新尾指针
}

3. 遍历输出

node *p = head->next;    // 从第一个有效结点开始
while (p != nullptr) {
    cout << p->data << " ";
    p = p->next;         // 移动到下一个结点
}
cout << endl;

4. 插入结点（在 p 之后插入 s）

s->next = p->next;   // 1. s 指向 p 的下一个结点
p->next = s;         // 2. p 指向 s

️ 顺序不能反！ 必须先连 s->next，再改 p->next，否则会丢失后续结点。

5. 删除结点（删除 p 的下一个结点）

node *del = p->next;   // 暂存待删除结点
p->next = del->next;   // p 跳过 del，直接指向 del 的下一个
delete del;            // 释放内存（竞赛中常省略，但好习惯要养成）

二、双向链表

1. 结点定义

struct dnode {
    int data;
    dnode *prev;   // 前驱指针
    dnode *next;   // 后继指针
};

2. 建立（尾插法）

dnode *head = new dnode;
head->prev = nullptr;
head->next = nullptr;
dnode *tail = head;

for (int i = 0; i < n; i++) {
    dnode *p = new dnode;
    cin >> p->data;
    p->next = nullptr;
    p->prev = tail;    // 新结点的前驱指向尾结点

    tail->next = p;    // 尾结点后继指向新结点
    tail = p;          // 更新尾指针
}

3. 插入（在 p 之后插入 s）

s->next = p->next;
s->prev = p;
if (p->next != nullptr)
    p->next->prev = s;
p->next = s;

4. 删除（删除 p 的下一个结点）

dnode *del = p->next;
p->next = del->next;
if (del->next != nullptr)
    del->next->prev = p;
delete del;

三、单向循环链表

最后一个结点的 next 指向头结点，形成环：

tail->next = head;   // 建表完成后，尾结点指回头结点

遍历终止条件改为 p != head：

node *p = head->next;
while (p != head) {
    cout << p->data << " ";
    p = p->next;
}

四、对比速记表

类型 指针数量 遍历方向 尾结点指向
单链表 1 个 next 单向 nullptr
双向链表 2 个 prev+next 双向 nullptr
单向循环链表 1 个 next 单向 head

五、易错点总结

  1. 头结点不存数据，有效数据从 head->next 开始。
  2. 插入时先连后断，否则会丢失后续结点。
  3. 删除前先暂存，否则 delete 后无法访问。
  4. **双向链表插入/删除要同时维护 **prev** 和 ****next**。
  5. **循环链表遍历时终止条件是回到 **head**，不是 ****nullptr**。
userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    曾语琛

    我是曾语琛

    2天前 来自 广东

    0

热门讨论