数据结构：链表详解（单链表、双链表、循环链表）

2. 单链表判空

这是带头结点单链表的判空函数，给它传链表的头指针，它就帮你检查这个链表有没有存有效数据的节点，要是链表啥数据都没有，就返回 true，有数据的话就返回 false。

bool Empty(LinkList L) 
{ 
    if (L->next == NULL) //如果 L->next 为 NULL，说明链表没有任何有效数据节点，是空链表 
        return true; 
    else 
        return false; 
}

3. 求表长的操作

这函数是用来算链表长度的，也就是数链表里有多少个存数据的节点。它会顺着链表一个一个往下走，每数到一个节点就给计数器加 1，直到走到链表的末尾，最后把数出来的总个数返回给你。

int Length(LinkList L) 
{ 
    int len = 0; //定义计数器 len，初始值为 0，用来统计数据节点的个数 
    LNode* p = L; //定义遍历用的指针 p，初始指向链表的头结点 
    while (p->next != NULL) //只要当前节点的下一个节点不为空，说明还有未统计的数据节点，继续遍历 
    { 
        p = p->next; //指针向后移动，走到下一个数据节点 
        len++; //每遍历到一个数据节点，计数器加 1 
    } 
    return len; //遍历结束，返回统计好的链表长度 
}

4. 按序号查找结点

这是按序号找节点的函数，给他要查的链表、还有要找的是第几个节点，它就顺着链表挨个往下找，找到对应节点就把这个节点的地址返回给你；要是你给的序号不对、或者链表没这么长，就返回 NULL，告诉你没找到对应的节点。

LNode* GetElem(LinkList L, int i) 
{ 
    LNode* p = L; //定义遍历用的指针 p，初始指向链表的头结点 
    int j = 0; //定义计数器 j，记录当前指针指向的节点序号，初始值 0 对应头结点 
    while (p != NULL && j < i) //只要指针没走到链表末尾，且还没到达目标序号 i，就继续遍历查找 
    { 
        p = p->next; //指针向后移动，走到下一个节点 
        j++; //计数器加 1，更新当前节点的序号 
    } 
    return p; //遍历结束，返回找到的节点地址（没找到对应节点则返回 NULL） 
}

5. 按值查找表结点

这是按值找节点的函数，给它要查的链表、还有要找的目标数值，它就顺着链表挨个节点看，找到第一个存了这个数值的节点，就把节点的地址返回给你；要是整个链表都找完了都没这个数，就返回 NULL，告诉你查找失败了。

LNode* LocateElem(LinkList L, ElemType e) 
{ 
    LNode* p = L->next; //定义遍历用的指针 p，初始指向第一个数据节点（跳过不存数据的头结点） 
    while (p != NULL && p->data != e) //只要指针没走到链表末尾，且当前节点的数据不等于目标值 e，就继续向后查找 
        p = p->next; //指针向后移动，检查下一个节点 
    return p; //遍历结束，返回找到的匹配节点地址（没找到对应节点则返回 NULL） 
}

6. 插入结点操作（指定位置）

这是带头结点链表的按位置插入函数，给它要操作的链表、要在第几个位置插、还有要插入的数，它会先检查你给的位置是否合法，然后找到要插的位置的前一个节点，把新节点插进去，插成功了就返回 true，位置不对就返回 false。

bool ListInsert(LinkList& L, int i, ElemType e) 
{ 
    if (i < 1) //检查位序合法性 
        return false; 
    LNode* p = L; //定义遍历指针 p，初始指向链表的头结点 
    int j = 0; //定义计数器 j，记录当前 p 指向的节点序号，初始 0 对应头结点 
    while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 不为空，且还没到第 i-1 个节点，就继续遍历 
    { 
        p = p->next; //指针向后移动，走到下一个节点 
        j++; //计数器加 1，更新当前节点的序号 
    } 
    if (p == NULL) //如果 p 为空，说明 i 超过了链表的长度，位置不合法，返回 false 
        return false; 
    LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点 s 
    s->data = e; //给新节点的 data 域赋值，存入要插入的元素 e 
    s->next = p->next; //新节点的 next 指向 p 原来的下一个节点，把链表后续的节点接在新节点后面 
    p->next = s; //p 的 next 指向新节点，把新节点接在 p 的后面，完成插入 
    return true; //插入成功，返回 true 
}

这是不带头结点链表的按位置插入函数，和带头的不一样，插第一个位置的时候要单独处理，因为要修改链表的头指针；其他位置的话，也是先找到要插的位置的前一个节点，再把新节点插进去，插成功了返回 true，位置不合法就返回 false。

bool ListInsert(LinkList& L, int i, ElemType e) 
{ 
    if (i == 1) //单独处理插入第 1 个位置的情况（不带头结点的链表，插第一个位置要修改头指针） 
    { 
        LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s 
        s->data = e; //给新节点赋值元素 e 
        s->next = L; //新节点的 next 指向原来的头节点，把原来的链表接在新节点后面 
        L = s; //头指针 L 指向新节点，新节点成为新的头节点 
        return true; 
    } 
    int j = 1; //处理插入位置不是第 1 位的情况：定义计数器 j，初始 1 对应第一个节点的序号 
    LNode* p = L; //定义遍历指针 p，初始指向链表的第一个节点（头指针 L） 
    while (p != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 不为空，且还没到第 i-1 个节点，就继续遍历 
    { 
        p = p->next; //指针向后移动，走到下一个节点 
        j++; //计数器加 1，更新当前节点的序号 
    } 
    if (p == NULL) //如果 p 为空，说明 i 超过了链表的长度，位置不合法，返回 false 
        return false; 
    LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s 
    s->data = e; //给新节点赋值元素 e 
    s->next = p->next; //新节点的 next 指向 p 原来的下一个节点，接好后续链表 
    p->next = s; //p 的 next 指向新节点，完成插入 
    return true; 
}

7. 插入结点操作（指定结点）

这是给已知节点前插元素的函数，传入已知的节点指针 p，有要插入的数 e，它就能直接在 p 的前面插入新节点，不用从头遍历链表。操作成功就返回 true，要是你给的 p 是空的，就返回 false。

bool InsertPriorNode(LNode* p, ElemType e) 
{ 
    if (p == NULL) //如果节点 p 为空，位置不合法，直接返回 false 
        return false; 
    LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s 
    s->next = p->next; //新节点的 next 指向 p 的下一个节点，把新节点插在 p 的后面 
    p->next = s; 
    s->data = p->data; //把 p 原来的数据复制到新节点 s 里 
    p->data = e; //把要插入的元素 e 存入 p 节点，相当于 p 变成了新插入的节点，s 变成了原来的 p 节点，实现前插效果 
    return true; 
}

这是给已知节点后插元素的函数，传入已知节点的指针 p、要插入的元素 e，函数会在节点 p 的后面插入新元素 e。不用从头遍历链表，直接修改节点的指针即可完成插入，操作成功返回 true，若节点 p 为空则返回 false。

bool InsertNextNode(LNode* p, ElemType e) 
{ 
    if (p == NULL) //如果传入的节点 p 为空，位置不合法，直接返回 false，终止操作 
        return false; 
    LNode* s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建一个新的节点 s，用来存放要插入的元素 
    s->data = e; //给新节点的 data 域赋值，存入要插入的元素 e 
    s->next = p->next; //新节点 s 的 next 指向 p 原来的下一个节点，把 p 后续的链表接在新节点后面 
    p->next = s; //把 p 的 next 指向新节点 s，将新节点接在 p 的后面，完成后插操作 
    return true; 
}

8. 删除结点操作

入链表头指针 L、要删除的位置 i、用来接收被删除元素的变量 e，函数会检查删除位置的合法性，找到第 i-1 个前驱节点，删除第 i 个节点并释放内存，删除成功返回 true，位置不合法返回 false。

bool ListDelete(LinkList& L , int i, ElemType& e) 
{ 
    LNode* p = L; //定义遍历指针 p，初始指向链表的头结点 
    int j = 0; //定义计数器 j，记录当前 p 指向的节点序号，初始 0 对应头结点 
    while (p->next != NULL && j < i - 1) //循环找到第 i-1 个前驱节点：只要 p 的下一个节点不为空，且还没到第 i-1 个节点，就继续遍历 
    { 
        p = p->next; //指针向后移动，走到下一个节点 
        j++; //计数器加 1，更新当前节点的序号 
    } 
    if (p->next == NULL || j > i - 1) //校验位置合法性：如果 p 的下一个节点为空（要删除的节点不存在），或者 j 超过了 i-1（位置非法），返回 false 
        return false; 
    LNode* q = p->next; //用指针 q 指向要删除的第 i 个节点（p 的下一个节点） 
    e = q->data; //把被删除节点的元素值赋值给 e，带出去给调用者 
    p->next = q->next; //把 p 的 next 指向 q 的下一个节点，跳过要删除的节点，把链表接好 
    free(q); //释放 q 节点的内存，避免内存泄漏 
    return true; 
}

9. 采用头插法建立单链表

传入链表头指针 L，函数会初始化带头结点的空链表，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表头结点的后，直到输入 9999 停止，最终返回建立好的链表头指针。

LinkList List_HeadInsert(LinkList& L) 
{ 
    LNode* s; //定义新节点指针 s，和用来接收用户输入的变量 x 
    int x; 
    L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点 
    L->next = NULL; //头结点的 next 置为 NULL，初始化空链表 
    scanf("%d", &x); //读取用户输入的第一个整数，存入 x 
    while (x != 9999) //循环：只要输入的 x 不是 9999，就继续插入节点 
    { 
        s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s 
        s->data = x; //给新节点赋值，存入用户输入的 x 
        s->next = L->next; //新节点的 next 指向头结点原来的下一个节点，接好链表的后续部分 
        L->next = s; //头结点的 next 指向新节点，把新节点插到链表头部 
        scanf("%d", &x); //读取下一个用户输入的整数，继续循环 
    } 
    return L; 
}

10. 采用尾插法建立单链表

传入链表头指针 L，函数会初始化带头结点的空链表，用尾指针 r 记录链表的最后一个节点，循环读取用户输入的整数，每读一个数就把它作为新节点插到链表的尾部，直到输入 9999 停止，最终返回建立好的链表头指针。

LinkList List_TailInsert(LinkList& L) 
{ 
    int x; //定义用来接收用户输入的变量 x 
    L = (LNode*)malloc(sizeof(LNode)); //申请内存，创建链表的头结点 
    LNode* s, * r = L; //定义新节点指针 s，和尾指针 r，初始 r 指向头结点（空链表的尾部就是头结点） 
    scanf("%d", &x); //读取用户输入的第一个整数，存入 x 
    while (x != 9999) //循环：只要输入的 x 不是 9999，就继续插入节点 
    { 
        s = (LNode*)malloc(sizeof(LNode)); //申请内存，创建新节点 s 
        s->data = x; //给新节点赋值，存入用户输入的 x 
        r->next = s; //尾指针 r 的 next 指向新节点，把新节点接到链表的尾部 
        r = s; //尾指针 r 移动到新节点，更新为新的链表尾部 
        scanf("%d", &x); //读取下一个用户输入的整数，继续循环 
    } 
    r->next = NULL; //循环结束，把链表最后一个节点的 next 置为 NULL，标记链表结束 
    return L; //链表建立完成，返回链表的头指针 
}

三、双链表的定义

单链表中只有一个指向后继结点的指针，这导致其在执行查找、插入和删除等操作的时候只能从头开始遍历，时间复杂度为 O(n) 。所以双链表的产生就是为了解决这种问题，其拥有 prior 指针和 next 指针，分别指向其直接前驱和直接后继。双链表结点结构图示如下：

单链表中的结点声明如下：

typedef struct DNode { //定义双链表结点类型 
    ElemType data; //数据域 
    struct DNode* prior, * next; //前驱指针和后驱指针 
}DNode, *DLinklist;

注意：代码使用 DNode 时，强调这是一个结点；代码使用 DLinkList 时，强调这是一个双链表。*

双链表的按值查找和按位查找时间复杂度与单链表持同，因为其都为顺序存取结构；但是其插入与操作快于单链表，因为双链表拥有前驱指针，可以很容易地找到前一结点，时间复杂度为 O(1) 。

四、双链表的基本操作

1. 双链表的初始化

这是带头结点的双链表初始化函数，说白了就是给双链表建一个头结点，先申请一块内存当这个头结点，要是内存申请失败就返回 false；申请成功的话，就把头结点的前驱指针 prior 和后继指针 next 都设成 NULL，代表现在链表是空的，最后返回初始化成功的 true。

bool InitDLinklist(DLinklist& L) 
{ 
    L = (DNode*)malloc(sizeof(DNode)); //申请一块内存，大小是一个 DNode 节点的大小，把申请到的地址赋值给头指针 L，也就是创建头结点 
    if (L == NULL) //如果 L 是 NULL，说明刚才申请内存失败了，直接返回 false 
        return false; 
    L->prior = NULL; //把头结点的前驱指针 prior 设为 NULL，头结点前面没有节点 
    L->next = NULL; //把头结点的后继指针 next 设为 NULL，头结点后面也没有节点，现在链表是空的 
    return true; 
}

2. 双链表的插入

这是双链表的节点后插函数，给它一个已知的节点 p，还有要插入的新节点 s，它就能把 s 插到 p 的后面。因为双链表有前后两个指针，所以要把新节点和前后的节点的指针都接好，要是 p 或者 s 是空的，就直接返回 false，操作成功就返回 true。

bool InsertNextDNode(DNode* p, DNode* s) 
{ 
    if (p == NULL || s == NULL) //如果 p 是空的，或者 s 是空的，位置不合法，直接返回 false 
        return false; 
    s->next = p->next; //让新节点 s 的后继指针，指向 p 原来的下一个节点，先把 p 后面的链表接在 s 的后面 
    if (p->next != NULL) //如果 p 原来的下一个节点不是空的 
        p->next->prior = s; //让 p 原来的后继节点的前驱指针，指向新节点 s，把后面节点的前向指针接好 
    s->prior = p; //让新节点 s 的前驱指针，指向节点 p，把 s 和 p 的前向关系接好 
    p->next = s; //让 p 的后继指针，指向新节点 s，把 p 和 s 的后向关系接好，完成插入 
    return true; 
}

3. 双链表的删除

这是双链表的节点删除函数，作用是删掉节点 p 后面的那个节点。它会先检查 p 是不是空的，还有 p 后面有没有节点可以删，要是没的删就返回 false；有的话就把链表的前后指针重新接好，跳过要删的节点，再释放掉这个节点的内存，避免内存泄漏，删成功了就返回 true。

bool DeleteNextNode(DNode* p) 
{ 
    if (p == NULL) //如果 p 是空的，位置不合法，直接返回 false 
        return false; 
    DNode* q = p->next; //用指针 q 指向 p 的后继节点，也就是我们要删掉的节点 
    if (q == NULL) //如果 q 是空的，说明 p 后面没有节点，没的可删，返回 false 
        return false; 
    p->next = q->next; //让 p 的后继指针，直接指向 q 的下一个节点，跳过要删的 q 节点，把链表的后向接好 
    if (q->next != NULL) //如果 q 的下一个节点不是空的（也就是 q 不是链表最后一个节点） 
        q->next->prior = p; //让 q 的后继节点的前驱指针，指向 p，把链表的前向接好 
    free(q); //释放掉 q 节点的内存，把要删的节点彻底清掉，避免内存泄漏 
    return true; 
}

4. 双链表的销毁

这是销毁整个双链表的函数，说白了就是把整个链表的所有节点都删掉，释放所有占用的内存，避免内存泄漏。它会循环调用刚才的删除函数，一直删掉头结点后面的所有节点，最后把头结点也释放掉，再把头指针设成 NULL，整个链表就彻底销毁了。

void DestroyList(DLinklist& L) 
{ 
    while (L->next != NULL) //循环：只要头结点的后面还有节点，就继续删 
        DeleteNextNode(L); //调用删除函数，删掉头结点后面的第一个节点，循环执行直到所有数据节点都被删掉 
    free(L); //所有数据节点都删完了，现在释放头结点的内存 
    L = NULL; //把头指针 L 设为 NULL，避免变成野指针 
    return; 
}

五、循环链表的定义

1. 循环单链表

循环单链表与单链表的区别就是，原来表尾指针指向 NULL 的，现在改为指向头结点。

循环单链表结点结构图示如下：

因此循环单链表中不会出现指针域指向 NULL 的结点，因此判空条件从是否头结点指向 NULL 改为是否等于头指针 L。

**判空：*L->next == L;

**判 p 是否为尾：*p->next == L;

2. 循环双链表

循环双链表相比循环单链表增加了头结点的 prior 指针也将指向表尾结点这一点。

循环双链表结点结构图示如下：

同理，循环双链表的判空条件是头结点的 prior 指针和 next 指针是否都指向头指针 L。

**判空：*L->next == L; L->prior == L;

**判 p 是否为尾：*p->next == L;

六、静态链表的定义

静态链表说白了就是用数组来实现线性表的链式存储结构，结点同样也分为用来存我们要放的实际数据的数据域 data 和指针域 next。不过这里的'指针'不是真正的内存地址，而是下一个节点在数组里的下标（也叫游标）。

**注意：**静态链表的数组大小是我们提前定好的，所以它能存的节点数量有固定上限，不能像动态链表那样随便加节点。

静态链表结点结构图示如下：

静态链表中的结点声明如下：

#define MaxSize 50 //宏定义一个静态链表的最大长度 
typedef struct { //静态链表结构类型的定义 
    ElemType data; //存储数据元素 
    int next; //下一个元素的数组下标 
}SLinkList[MaxSize];

静态链表以 next == -1 作为结束标志，因为数组的下标都是 ≥0 的正数，-1 就代表'这个节点后面没有其他节点了'，作用和动态链表最后一个节点的 next=NULL 是一模一样的。

其余操作与动态链表几乎相同，比如插入、删除节点，都只需要修改 next 指针，不用移动其他元素。唯一的小区别是，静态链表不用手动申请、释放节点的内存，而是从我们提前开好的数组里找空闲的位置来用，动态链表则是需要的时候才申请内存。

七、顺序表和链表的区别

1. 存取方式

顺序表：支持随机存取和顺序存取。

顺序表的本质是数组，只要给出元素的下标，就可以直接通过内存地址计算一步找到对应元素，时间复杂度为 O(1) 。比如我们要找顺序表的第 5 个元素，直接访问 data[4] 就能拿到，不需要遍历前面的元素。

链表：仅支持顺序存取。

链表的节点在内存中是分散的，要找到第 i 个元素，必须从链表的头结点开始，顺着指针一个一个遍历到目标位置，无法直接跳转到对应节点，时间复杂度为 O(n) 。比如要找链表的第 5 个元素，必须从第 1 个开始，依次往后数 4 次才能找到。

2. 逻辑结构与物理结构

顺序表：采用顺序存储。逻辑上相邻，物理存储位置也相邻。

链表：采用链式存储。逻辑上相邻，物理存储位置不一定相邻。

3. 查找、插入和删除操作

**按序查找：**顺序表的随机存取结构使得时间复杂度为 O(1) ;链表必须从头开始遍历查找，所以时间复杂度为 O(n) 。

**按值查找：**如果表内元素是无序的，则顺序表和链表都必须从头开始找，时间复杂度均为 O(n) ；如果表内元素是有序的，则顺序表可以用二分法查找，时间复杂度为 O(nlog2n) ，而链表时间复杂度依旧为 O(n) 。

4. 空间分配

顺序表：分为静态分配顺序表和动态分配顺序表。

对于静态分配顺序表，数组大小在初始化的时候就已经定死了，若分配量过小，元素量超出存储空间上限就会溢出导致运行崩溃；若分配量过大，会使得空间闲置浪费。

而动态分配顺序表，虽然可以在存储空间不够用时随时扩容，但是它的扩容是开一个新空间，然后把旧空间装不下的内容全部复制到新空间中，操作量大，效率极低。并且还可能因为找不到足够大的连续内存而扩容失败.

**链表：**其结点内存是在插入时才申请、删除时就释放的，不需要提前确定链表的最大长度，只要系统还有可用内存，就可以继续添加结点；同时结点可以利用内存中零散的空闲空间，不会出现大块内存闲置的问题，唯一的空间开销是每个结点需要额外的内存来存放指针。