数据结构：顺序表与链表详解

链表的操作

操作链表需要传入的参数为链表地址（即头节点的地址）。链表操作的函数在头文件定义部分声明为外部函数，在调用头文件时可直接调用。

简单操作

操作小结：创建、插入（头/尾）、移除、遍历、更改、查询、销毁。

1. 链表的生成

本质：插入（生成）头节点。

实现思路：

1. 定义一个头节点的指针，申请头节点空间（插入必备）。
2. 在头节点的指针区存放 NULL 地址。

LinkNode *CreateEmptyLinkList(void) { //创建链表的本质是创建一个头节点 (空白节点)
    //1. 头节点的空间准备
    LinkNode *pHeadNode = NULL;
    pHeadNode = malloc(sizeof(LinkNode)); //给头节点申请堆区空间，避免函数结束后被释放
    if (NULL == pHeadNode) {
        perror("fail to malloc");
        return NULL;
    }
    //2. 头节点的内容存放（数据区，指针区）
    pHeadNode->pNextnode = NULL; //数据区存放内容随意，但指针区必须为空
    return pHeadNode;
}

2. 节点的插入（头插入）

实现思路：

1. 定义一个插入节点指针，申请插入节点的空间（插入必备）。
2. 在该插入节点的数据区存放插入数据，在该插入节点的指针区存放原链表首位有效节点的地址。
3. 在头节点的指针区存放该插入节点的地址。

int HeadInsertNode(LinkNode *pHeadNode, DataType tmpData) { //头插法
    //1. 插入节点的空间准备
    LinkNode *pInsertNode = NULL;
    pInsertNode = malloc(sizeof(LinkNode)); //给插入节点申请一块空间
    if (pInsertNode == NULL) {
        perror("fail to malloc");
        return -1;
    }
    //2. 插入节点的内容存放（数据区，指针区）
    pInsertNode->data = tmpData; //数据区存放插入数值
    pInsertNode->pNextnode = pHeadNode->pNextnode; //指针区存放首位有效节点地址
    //3. 搭建插入节点和链表的连接关系
    pHeadNode->pNextnode = pInsertNode; //头节点的指针区存放插入节点的地址
    return 0;
}

3. 节点的插入（尾插入）

实现思路：

1. 定义一个插入节点指针，申请节点空间（插入必备）。
2. 在该节点的数据区存放插入数据，在该节点的指针区存放 NULL 地址。
3. 定义一个流动指针，遍历找到原链表的末尾节点。
4. 在原链表末尾节点的指针区存放该插入节点的地址。

int TailInsertNode(LinkNode *pHeadNode, DataType tmpData) { //尾插法
    LinkNode *pFlow = NULL;
    LinkNode *pInsertNode = NULL;
    
    //1. 插入节点的空间准备
    pInsertNode = malloc(sizeof(LinkNode));
    if (pInsertNode == NULL) {
        perror("fail to malloc");
        return -1;
    }
    //2. 插入节点的内容存放
    pInsertNode->data = tmpData;
    pInsertNode->pNextnode = NULL;
    
    //3. 流动指针遍历，寻找末尾节点
    pFlow = pHeadNode->pNextnode;
    while (pFlow->pNextnode != NULL) { //寻找末尾节点的遍历
        pFlow = pFlow->pNextnode;
    }
    
    //4. 搭建插入节点和链表的连接关系
    pFlow->pNextnode = pInsertNode; //原链表末尾节点的指针区存放插入节点的地址
    return 0;
}

3 种插入的比较

四步插入法：申请插入空间，寻找插入位置，存放插入内容，建立连接。

4. 节点的遍历（节点数据显示）

遍历方式 1 实现思路：判断指向当前节点的指针是否为 NULL。

while (pNowNode != NULL) {
    pNowNode = pNowNode->pNextnode;
}

注：此遍历方式无法找到末尾节点。

遍历方式 2 实现思路：当前节点的指针区为 NULL，则其为末尾节点。

while (pNowNode->pNextnode != NULL) {
    pNowNode = pNowNode->pNextnode;
}

应用：节点数据的显示 实现思路：定义一个流动指针，从链表首个有效节点开始遍历，实现对各有效节点数据区内容的访问，并展示数据区具体内容。

void NodeDataShow(LinkNode *pHeadNode) { //节点数据显示
    LinkNode *pFlow = NULL;
    pFlow = pHeadNode->pNextnode; //遍历从链表首个有效节点开始
    while (pFlow != NULL) { //实现对各有效节点数据区内容的访问
        printf("%d ", pFlow->data); //展示节点数据区内容
        pFlow = pFlow->pNextnode;
    }
    printf("\n");
    return;
}

5. 节点的删除

实现思路：定义两个指针，流动指针和前节点指针；流动指针用于遍历链表，查询删除节点；前节点指针用于建立删除节点的前后节点的连接关系。

具体过程：

1. 流动指针采用遍历方式 1，从链表的首个有效节点开始，基于对有效节点数据区内容的匹配，查询到要删除的节点。
2. 前节点指针实时指向流动指针指向节点的前一节点，流动指针到达删除节点时，前节点指针借助流动节点的指针区内容直接指向删除节点的后一节点，建立前后节点的连接关系。
3. 通过流动指针释放删除节点的堆空间，同时借助前节点指针使流动指针指向删除节点的后节点，避免野指针。

int DeleteNode(LinkNode *pHeadNode, DataType rmData) { //节点删除函数
    int cnt = 0;
    LinkNode *pPreNode = NULL;
    LinkNode *pNowNode = NULL;
    
    pPreNode = pHeadNode;
    pNowNode = pHeadNode->pNextnode;
    
    while (pNowNode != NULL) {
        if (pNowNode->data == rmData) {
            pPreNode->pNextnode = pNowNode->pNextnode;
            free(pNowNode);
            pNowNode = pPreNode->pNextnode; //避免野指针
            cnt++;
        } else {
            pPreNode = pPreNode->pNextnode;
            pNowNode = pNowNode->pNextnode;
        }
    }
    return cnt;
}

*注：无头链表对第一个节点需要特殊处理。

6. 节点的查询

7. 节点数据的更改

8. 链表的销毁

定义两个指针（遍历指针，释放指针），均从头节点开始。遍历指针只要非空，则后移，释放指针释放掉当前的，而后后移。

操作小结：创建、插入、移除、遍历展示、更改、查询、销毁。

复杂操作

1. 寻找中间节点

实现思路：快慢指针法。快指针走两格，慢指针走一个。快指针先走一格，判断是否为空指针，若为空，停止前进。

2. 找倒数第 k 个节点

实现思路：差额指针法。快指针先走 k 格，随后快慢指针一同前进，快指针到空指针处。

3. 倒置

实现思路：头插法实现倒置。定义两个指针（遍历指针/流动，节点插入指针/用于节点插入），使其均指向链表首位有效节点，断开头节点和链表的连接，进入遍历。

4. 冒泡排序

定义 2 个遍历（流动）指针，1 个终止指针，1 个暂存数据（用于数据交换）。先判断链表中有效数据的个数，有效数据个数为 0 个或 1 个时，直接退出，无需排序。进入排序，给遍历指针 1 号首位有效节点，给遍历指针 2 号第二位有效节点。

5. 选择排序

定义指针：遍历节点指针，记录最小值节点的指针，需要交换节点的指针。寻找最小值，比较，交换，后移。设定未排序部分的首位节点为可交换节点，并假设未排序部分的首位节点为最小值节点。遍历从第二位节点开始，若有遍历数据小于最小值节点的数据，则更新最小值节点（非数据交换）。完成一次遍历后，比较最小值节点的数据和未排序部分的首位节点的数据，若小于，则发生数据交换，以完成前小后大的排序。直到未排序部分的首位节点到达链表的最后一个节点。

6. 头节点未知，删除某位节点（了解）

只能删除中间节点，无法删除末尾节点。后一位节点的数据赋值给目标位节点，删除后一位节点。

7. 判断链表是否有环

有环：链表中的某位节点指向其前侧的节点。

判断是否有环，获得环长，获得环入口。 倍数遍历指针：单倍遍历指针，二倍遍历指针，两指针差值增长，每次增长一（自然增长）。指针重逢，差值即为环长。

判断有环：快走 2，慢走 1，有相遇，则有环。

环长：相遇不一定在环入口。

双向链表

创建、头插、尾插、遍历、删除、销毁。

创建：一个数据区，两个指针区。

插入

1. 申请空间 pNewNode。
2. 插入节点的数据存放：存放数据到 pNewNode->data。
3. 插入节点的指针存放：将 pNewNode->next 赋值为空白节点的 next，pNewNode->pre 赋值为空白节点地址。
4. 将空白节点的 pNext 赋值为新节点。
5. 后续有节点，需要将后面节点的 pre 指向新申请的节点。

int InsertHeadDouList(LinkNode *pHead, DataType TmpData) {
    //1. 插入节点的空间申请
    LinkNode *pInsertNode = NULL;
    pInsertNode = malloc(sizeof(LinkNode));
    if (pInsertNode == NULL) {
        perror("fail to malloc");
        return -1;
    }
    //2. 插入节点的数据存放
    pInsertNode->data = TmpData;
    //3. 建立插入节点对前后节点的单向连接 (插入节点的指针存放)
    pInsertNode->pPre = pHead;
    pInsertNode->pNext = pHead->pNext;
    //4. 建立前后节点对插入节点的回向连接
    //4.1 建立头节点对插入节点的顺向连接（插入节点前节点）
    pHead->pNext = pInsertNode; //pInsertNode->pPre->pNext = pInsertNode;
    //4.2 链表的首位有效节点是否存在 (即插入节点的后节点是否存在)
    if (pInsertNode->pNext != NULL) { //注：绝对不能用 pHead->pNext(指向内容发生了改变)
        //4.3 存在，则建立链表的首位有效节点对插入节点的逆向连接（插入节点后节点）
        pInsertNode->pNext->pPre = pInsertNode;
    }
    return 0;
}

删除

1. 查找删除节点。
2. 让删除节点的前面节点的 next 指向删除节点的 next。
3. 如果有后面节点，让删除节点的后面节点的 pre 指向删除节点的 pre。
4. 定义 pFree 指向待释放节点。
5. 释放。

存放数据的类型：遍历和单向无差（可反向遍历）。查找、修改也是（遍历找元素，修改）。销毁也一样。

双向循环链表

区别

链表指针区不会存放空指针。遍历终止条件判断更改为是否指向头节点。无需判断后节点为空的情况。寻找末尾节点无需一一顺向遍历，直接取头节点的前节点即可。

创建链表：特点：自己指向自己。

LinkNode *CreateEmptyCirList(void) {
    LinkNode *pHead = NULL;
    pHead = malloc(sizeof(LinkNode));
    if (pHead == NULL) {
        perror("fail to malloc");
        return NULL;
    }
    //自我指向
    pHead->pPre = pHead;
    pHead->pNext = pHead;
    return pHead;
}

头插法插入节点

int InsertHeadCirList(LinkNode *pHead, DataType TmpData) {
    //1. 插入节点的空间申请
    LinkNode *pInsertNode = NULL;
    pInsertNode = malloc(sizeof(LinkNode));
    if (pInsertNode == NULL) {
        perror("fail to malloc");
        return -1;
    }
    //2. 插入节点的数据存放
    pInsertNode->data = TmpData;
    //3. 建立插入节点对前后节点的单向连接 (插入节点的指针存放)
    pInsertNode->pPre = pHead;
    pInsertNode->pNext = pHead->pNext;
    //4. 建立前后节点对插入节点的回向连接
    pInsertNode->pPre->pNext = pInsertNode;
    pInsertNode->pNext->pPre = pInsertNode;
    //循环链表，指向节点始终存在，无需判断空指针问题
    return 0;
}

尾插

int InsertTailCirList(LinkNode *pHead, DataType TmpData) {
    //1. 插入节点的空间申请
    LinkNode *pInsertNode = NULL;
    pInsertNode = malloc(sizeof(LinkNode));
    if (pInsertNode == NULL) {
        perror("fail to malloc");
        return -1;
    }
    //2. 插入节点的数据存放
    pInsertNode->data = TmpData;
    //3. 插入节点的指针存放
    pInsertNode->pNext = pHead;
    pInsertNode->pPre = pHead->pPre; //由于循环指向，无需遍历就可找到末尾节点（即头节点的前位节点）
    //4. 前后节点对插入节点的连接建立
    pInsertNode->pPre->pNext = pInsertNode;
    pInsertNode->pNext->pPre = pInsertNode;
    return 0;
}

插入必须通过头节点来建立插入节点和链表的连接关系。

数据展示

int ShowCirList(LinkNode *pHead) {
    LinkNode *pFlow = NULL;
    pFlow = pHead->pNext;
    while (pFlow != pHead) { //判断条件发生变化，即是否回到头节点表示完成一次全节点遍历
        printf("%d ", pFlow->data);
        pFlow = pFlow->pNext;
    }
    printf("\n");
    return 0;
}

链表拓展

内核链表 目的：设置一种复用性高的链表（数据类型多样，不仅仅是整型）。 数据类型由函数调用者确定。建立结构体，存放链表的节点和数据内容。链表的节点只存放前后指针，只有节点指针，没有数据类型。数据访问的实现：节点的首地址和整个结构体的首地址一样，强制类型转换将节点指针改为结构体指针，从而实现对数据的访问。

面试问题

数组和链表的区别

数组的空间是连续的，链表的空间可以不连续。数组元素必有限，链表元素是没有上限的。数组插入和删除效率比较低，链表的插入和删除效率比较高。数组访问元素比较方便，链表访问元素不方便。