Chapter 3: 顺序表和链表

在C语言的编程世界中，数据结构是支撑程序运行的核心框架之一。它们定义了数据的存储模式，决定了数据操作的效率和方便性。其中，链表和顺序表作为最基本的数据结构，广泛应用于各种程序设计和数据处理中。这两种数据结构各有特点，选择使用哪一种往往取决于具体的应用场景和需求。本篇文章将通过C语言来详细介绍链表和顺序表的基本概念、结构和特性，并通过实际代码演示如何在不同的情境下选择和应用这两种数据结构，使得读者能够在未来的编程实践中做出更加明智的选择。

文章目录

线性表
顺序表
链表
顺序表和链表的区别和联系
总结

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

（1） 静态顺序表：使用定长数组存储元素。

（2）动态顺序表：使用动态开辟的数组存储。

2.2 接口实现

静态顺序表只适用于明确知道需要存多少数据的情况。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面实现动态顺序表。

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array;  // 指向动态开辟的数组
	size_t size;       // 有效数据个数
	size_t capicity;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

2.3 数组相关面试题

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。. - 力扣（LeetCode）

2. 删除排序数组中的重复项。OJ链接

. - 力扣（LeetCode）

3. 合并两个有序数组。OJ链接

. - 力扣（LeetCode）

2.4 顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)。

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

三、链表

3.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

3.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

（1）单向或者双向

（2） 带头或者不带头

（3）循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3.3 链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

3.4 链表面试题

（1）删除链表中等于给定值 val 的所有结点。. - 力扣（LeetCode）1

（2）反转一个单链表。. - 力扣（LeetCode）

（3）给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。. - 力扣（LeetCode）

（4）输入一个链表，输出该链表中倒数第k个结点。

代码如下:

OJ调试可以使用VS

（5）将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。. - 力扣（LeetCode）

（6）编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。链表分割_牛客题霸_牛客网

（7）链表的回文结构。链表的回文结构_牛客题霸_牛客网

代码如下：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
 struct ListNode* reverseList(struct ListNode* head){
        struct ListNode* cur=head;
        struct ListNode* newhead=NULL;

        while(cur)
        {
            struct ListNode* next=cur->next;
            //头插
            cur->next=newhead;
            newhead=cur;

            cur=next;
        }
        return newhead;
    }

    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* slow=head,*fast=head;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }


    bool chkPalindrome(ListNode* A) {
       struct ListNode* mid=middleNode(A);
       struct ListNode* rmid=reverseList(mid);

       while(A && rmid)
       {
        if(A->val!=rmid->val)
        return false;

        A=A->next;
        rmid=rmid->next;
       }
       return true;
    }
};

（8）输入两个链表，找出它们的第一个公共结点。. - 力扣（LeetCode）

有一种思路是错误的：将两个链表逆置，这时意味着一个节点就有两个Next节点，所以是错误的

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;

    int lenA=0;
    while(curA->next)
    {
        ++lenA;
        curA=curA->next;
    }

     int lenB=0;
    while(curB->next)
    {
        ++lenB;
        curB=curB->next;
    }

    //不相交
    if(curA!=curB)
    {
        return NULL;
    }

    int gap=abs(lenA-lenB);//abs求绝对值
    struct ListNode* longList=headA;
    struct ListNode* shortList=headB;
    if(lenB>lenA)
    {
        longList=headB;
        shortList=headA;
    }

    //让长的先走gap步
    while(gap--)
    {
        longList=longList->next;
    }

    //再同时走，找交点
    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }

    return longList;

}

在VS里面调试

（9）给定一个链表，判断链表中是否有环。. - 力扣（LeetCode）

验证：

也就是说N和C-1同时为奇数时，fast指针永远追不上slow指针，现在需要验证N为奇数和C-1为奇数是否能同时成立

所以b假设是不成立的，fast永远追不上slow这个假设不成立

同理

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow == fast)
        return true;

    }
    
    return false;
}

代码简单，难点在思路的逻辑分析

【思路】快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表启始位置开始走，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况。因此，在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走3步，走4步，...n步行吗？

（10）给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL . - 力扣（LeetCode）

判断是否带环，求环的入口点

前提：快指针走一步，慢指针走两步

上面这种解法是错误的

环很小时可以看出明显错误

结论

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

证明

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            struct ListNode* meet=slow;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }

            return meet;
        }
    }

    return NULL;
}

如果实在没有思路，想不到上面的方法，还有一个思路

将相遇点的Next置为空

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;

    int lenA=0;
    while(curA->next)
    {
        ++lenA;
        curA=curA->next;
    }

     int lenB=0;
    while(curB->next)
    {
        ++lenB;
        curB=curB->next;
    }

    //不相交
    if(curA!=curB)
    {
        return NULL;
    }

    int gap=abs(lenA-lenB);//abs求绝对值
    struct ListNode* longList=headA;
    struct ListNode* shortList=headB;
    if(lenB>lenA)
    {
        longList=headB;
        shortList=headA;
    }

    //让长的先走gap步
    while(gap--)
    {
        longList=longList->next;
    }

    //再同时走，找交点
    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }

    return longList;

}
//使用前面相交问题的代码


struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            struct ListNode* meet=slow;
            struct ListNode* headx=meet->next;
            meet->next=NULL;

            return getIntersectionNode(head,headx);
        }
    }

    return NULL;
}

（11）给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。要求返回这个链表的深度拷贝。. - 力扣（LeetCode）

关键部分如下：

具体操作：

（1）

（2）

（3）

完整代码如下：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    //拷贝节点插入到原节点的后面
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;

        //插入
        copy->next=cur->next;
        cur->next=copy;

        //迭代
        cur=cur->next->next;
    }

    //控制拷贝节点的random
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }

        //迭代
        cur=cur->next->next;

    }

	//把copy节点解下来，链接成新链表
    struct Node* copyhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;

        //尾插
        if(tail==NULL)
        {
            copyhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }

        cur->next=next;
        cur=next;
    }
    return copyhead;
}

（12）其他 ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，以后大家自己下去以后 力扣 + 牛客网在线编程_算法篇_面试必刷TOP101

3.5 双向链表的实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);

四、顺序表和链表的区别和联系

与程序员相关的CPU缓存知识 | 酷壳 - CoolShell

总结

本篇博客通过对链表和顺序表的详细探讨，可以发现两者各有优势和局限。顺序表提供了快速的随机访问能力，但受限于预先分配的固定空间，其插入和删除操作相对效率较低。而链表虽然在随机访问上不如顺序表，但其动态的内存分配和高效的插入删除操作使其在处理大量不确定数据时显得更为灵活。在实际应用中，选择哪种数据结构，应基于具体的应用需求，考虑数据量的大小、操作的频繁程度及场景的特点。希望通过本文的介绍，读者能够对这两种基础数据结构有更深的理解，并有效地应用在实际的C语言编程项目中，从而编写出更高效、更高质量的代码。