C、C++常用数据结构：链表

基本概念

参考：链表基础知识详解（非常详细简单易懂）-CSDN博客

1. 链表是一种线性存储结构，链表在物理存储上是非连续的，数据元素的逻辑顺序通过链表中的指针链接
2. 链表由一系列的结点组成，每个节点主要包含两个部分：数据域+指针域
3. 数据域存放实际的数据；指针域存放下一个节点的地址（首地址）
4. 链表分为单向链表和双向链表：单向链表由一个指针next，存放下一个节点的首地址；双向链表由next和previous，分别存放下一个节点和上一个节点的首地址
5. 常见面试题：链表和数组的对比。链表的内存是不连续的，链表通过节点把离散的数据链接成一个表；而数组是通过开辟一段连续的内存来存储数据。数组成员和链表节点的数据类型可以是标准的C类型或者是用户自定义的类型。数组有起始地址和结束地址，链表没有明确的起始地址和结束地址，为了方便操作，可能会人为规定一个根节点（当然这是对于双向链表来说的，单向链表还是有头尾之分的）

以下代码只针对单链表

链表的创建

链表结点定义

// 定义一个链表节点结构体
typedef struct listNode
{int val;struct listNode *next;
} listNode;

链表创建

/*** 创建链表*  用到了二级指针要改变指针指向的值，传入指针要改变指针的指向（指针本身），传入二级指针*/
void listCreate(listNode **p_head, listNode *p_new)
{listNode *p_move = *p_head;if (*p_head == NULL){*p_head = p_new;}else{while (p_move->next != NULL){p_move = p_move->next;}p_move->next = p_new;p_new->next = NULL;}
}

链表遍历

/*** 遍历链表*/
void listPrint(listNode *head)
{if (head == NULL){cout << "list is NULL" << endl;return;}listNode *p = head;while (p != NULL){cout << p->val << " ";p = p->next;}cout << endl;
}

链表释放

/*** 释放链表*/
void listFree(listNode **head)
{listNode *p = *head;while (*head != NULL){p = *head;*head = (*head)->next;free(p);p = NULL; // 防止野指针}cout << "list free" << endl;
}

链表查找

/*** 链表查找*/
void listFind(listNode *head, int val)
{if (head == NULL)return;listNode *p = head;while (p != NULL){if (p->val == val){cout << "I find " << p->val;}p = p->next;}cout << endl;
}

链表删除

/*** 链表删除*/
void listDelete(listNode **head, int val)
{if (*head == NULL){return;}listNode *slow = NULL;listNode *fast = *head;while (fast != NULL){if (fast->val == val){if (fast == *head){*head = (*head)->next;free(fast);cout << "delete done" << endl;fast = *head;}else{slow->next = fast->next;free(fast);cout << "delete done" << endl;fast = slow->next;}}else{slow = fast;fast = fast->next;}}
}

链表插入

/*** 链表插入* 根据val值来判断插入位置（从小到大）*/
void listInsert(listNode **head, listNode *p_new)
{// 如果链表为空，则插入的结点为头结点if (*head == NULL){*head = p_new;p_new->next = NULL;return;}// 定义快慢指针listNode *slow = NULL;listNode *fast = *head;while (p_new->val >= fast->val && fast->next != NULL){slow = fast;fast = fast->next;}if (p_new->val < fast->val) // 如果找到了大于新结点val的结点，则新结点插入该结点左边{if (fast == *head){p_new->next = *head;*head = p_new;}else{p_new->next = slow->next;slow->next = p_new;}}else // 没有找到就插入右边{fast->next = p_new;p_new->next = NULL;}
}

测试用例

#include <iostream>
#include <vector>
#include <cstdio>using namespace std;// 定义一个链表节点结构体
typedef struct listNode
{int val;struct listNode *next;
} listNode;/*** 创建链表*  用到了二级指针要改变指针指向的值，传入指针要改变指针的指向（指针本身），传入二级指针*/
void listCreate(listNode **p_head, listNode *p_new)
{listNode *p_move = *p_head;if (*p_head == NULL){*p_head = p_new;}else{while (p_move->next != NULL){p_move = p_move->next;}p_move->next = p_new;p_new->next = NULL;}
}/*** 遍历链表*/
void listPrint(listNode *head)
{if (head == NULL){cout << "list is NULL" << endl;return;}listNode *p = head;while (p != NULL){cout << p->val << " ";p = p->next;}cout << endl;
}/*** 释放链表*/
void listFree(listNode **head)
{listNode *p = *head;while (*head != NULL){p = *head;*head = (*head)->next;free(p);p = NULL; // 防止野指针}cout << "list free" << endl;
}/*** 链表查找*/
void listFind(listNode *head, int val)
{if (head == NULL)return;listNode *p = head;while (p != NULL){if (p->val == val){cout << "I find " << p->val;}p = p->next;}cout << endl;
}/*** 链表删除*/
void listDelete(listNode **head, int val)
{if (*head == NULL){return;}listNode *slow = NULL;listNode *fast = *head;while (fast != NULL){if (fast->val == val){if (fast == *head){*head = (*head)->next;free(fast);cout << "delete done" << endl;fast = *head;}else{slow->next = fast->next;free(fast);cout << "delete done" << endl;fast = slow->next;}}else{slow = fast;fast = fast->next;}}
}/*** 链表插入* 根据val值来判断插入位置（从小到大）*/
void listInsert(listNode **head, listNode *p_new)
{// 如果链表为空，则插入的结点为头结点if (*head == NULL){*head = p_new;p_new->next = NULL;return;}// 定义快慢指针listNode *slow = NULL;listNode *fast = *head;while (p_new->val >= fast->val && fast->next != NULL){slow = fast;fast = fast->next;}if (p_new->val < fast->val) // 如果找到了大于新结点val的结点，则新结点插入该结点左边{if (fast == *head){p_new->next = *head;*head = p_new;}else{p_new->next = slow->next;slow->next = p_new;}}else // 没有找到就插入右边{fast->next = p_new;p_new->next = NULL;}
}int main(int argc, char const *argv[])
{listNode *head = NULL, *p_new = NULL;int num = 0;for (int i = 0; i < 10; i++){p_new = (listNode *)malloc(sizeof(listNode));p_new->val = i;listCreate(&head, p_new);}listPrint(head);listFind(head, 3);listDelete(&head, 3);listPrint(head);cout << "结点插入测试" << endl;listNode *p_insert = (listNode *)malloc(sizeof(listNode));p_insert->val = 3;listInsert(&head, p_insert);listPrint(head);listFree(&head);return 0;
}