活动地址：CSDN21天学习挑战赛

线性表

1.前言

学习数据结构，肯定绕不开的就是线性表，而线性表又分为顺序表和链表，本文就来分享一波线性表的入门学习文章，水平有限，难免存在纰漏，欢迎互相交流学习。

2.定义与理解

---

​ 定义：线性表（linear list）是n个具有相同特性的数据元素的有限序列。

​ 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
​ 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储 。

​ 线性表强调的是有序和有限。

​ 若将线性表记为(a₁ ,…,a_i-1 ,a_i,a_i+1,…,a_n)，则a_i-1 领先于a_i ，a_i 领先于a_i+1 ，称a_i-1 是a_i 的直接前驱元素，a_i+1 是a_i 的直接后继元素。第一个元素无前驱，最后一个元素无后继，其他元素有且仅有一个前驱和后继。

​ 所以线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。在非空表中每个数据元素都有一个确定的位置，用下标（比如a_i）来表示，称i为数据元素a_i在线性表中的位序。

---

3.顺序表

---

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

​ 顺序表一般可以分为：静态顺序表和动态顺序表

3.1静态顺序表：使用定长数组存储元素

​ 数据结构中的命名要有一定的规范，我们把要用到的类型int重命名为DataType，方便日后修改，不过为了表明这是顺序表特有的，在前面加个前缀，即SLDataType，SL即sequent list（顺序表）的首字母大写缩写。接下来我们定义结构体，顺便重命名一下为SeqList，其中第一个成员是顺序表的主体——定长数组，这里用宏定义一个常量来作为数组长度，第二个成员就是顺序表中有效数据的个数size。

3.2动态顺序表：使用动态开辟的数组存储

3.2.1说明

​ 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组一般需要N定大些，空间开多了浪费，而开少了又不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。 动态顺序表使用的是动态开辟的内存，通过realloc函数来实现扩容，那么问题来了，是不是每次增加一个元素我就扩容一格？这样效率太低了，因为使用realloc扩容是有一定代价的，你一次才扩容一个，次数太频繁了，realloc有两种扩容方式，一是原地伸长，这倒还好些，另一个是另寻空间，拷贝元素到新空间，再把旧空间释放，确实麻烦。那怎么设计扩容呢？

​ 我们知道，扩容：一次扩多了，存在空间浪费；一次扩少了，需要频繁扩容，有效率的损失。

​ 我们这里可以先暂时考虑每次扩充为容量的2倍，相对来说比较合适，不会太多，也不会太少。

​ 顺序表的结构声明要有所变化了：数组用动态开辟的内存，新增一个记录顺序表容量大小的变量capacity。

3.2.2初始化和销毁

​ 在设计函数的时候，基本上都要传结构指针，因为要对顺序表做改动，如果传结构体的话无法修改，形参是实参的一份临时拷贝，改变形参并不会影响实参，除非传入实参的地址，解引用后修改。

​ 初始化的话直接把顺序表中的指针置零，也可以在这里先用malloc开辟一段初始空间，不过我们这里先置为零。

void InitSeqList(SeqList* ps1)
{
	assert(ps1);
	ps1->array = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}
1
2
3
4
5
6
7

​ 销毁顺序表的话也很简单，记得free释放动态开辟的内存，然后全部置为零即可。

void DestorySeqList(SeqList* ps1)
{
	assert(ps1);
	free(ps1->array);
	ps1->array = NULL;
	ps1->size = 0;
	ps1->capacity = 0;
}
1
2
3
4
5
6
7
8

3.2.3头插尾插

​ 即顺序表的头部插入和尾部插入操作。先看看尾插，是不是感觉好像挺简单的嘛，直接在ps1->size位置处插入元素并让ps1->size自增1不就行了吗？但是你有没有想过一个问题，我们还没有开辟动态内存呢，而且满容了需要扩容怎么办，这些要综合考虑。

​ 尾插前要先检查容量看是否需要扩容，这一部分其实不止会在尾插过程中出现，所以我们把它封装成一个函数先。

static void CheckCapacity(SeqList* ps1)
{
	assert(ps1);
	if (ps1->capacity == ps1->size)
	{
		int newCapacity = (ps1->capacity == 0) ? 4 : ps1->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps1->array, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc NULL");
			return;
		}
		ps1->array = tmp;
		ps1->capacity = newCapacity;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

​ 用static修饰是因为我希望该函数仅在当前文件中使用，作为其他操作函数的辅助函数。判断容量是否已满（如果当前有效数据个数达到容量就是满了），满了的话就扩容。如果是刚初始化的顺序表，就先扩容到四个元素大小，不然就让容量翻倍（乘以2）。对于动态内存的扩容，我们选用realloc函数，如果遇到刚初始化的顺序表，ps1->array还是NULL的话也不打紧，正好realloc函数传空指针后作用类同于malloc函数，会找一块空闲内存来开辟动态内存。

​ 不过realloc后要记得检查一次是否返回空指针，不为空指针的话就把指针值交给ps1->array，同时容量更新。

​ 接下来就是尾插函数的实现了，其实有了上面的检查容量的函数，剩下的就很简单了。

void PushBackSeqList(SeqList* ps1, SLDataType targ)
{
	assert(ps1);

	CheckCapacity(ps1);

	ps1->array[ps1->size] = targ;
	ps1->size++;
}
1
2
3
4
5
6
7
8
9

​ push就是推的意思，back在这里是指顺序表的尾部，连起来就是把数值推入表的尾部。

​ 讲了尾插，紧接着就是头插函数了。先把第一个元素后面的所有元素挨个向后移动一位，注意要从后向前移动，从前向后会在中途覆盖掉一些值，然后把目标元素覆盖第一个元素。

void PushFrontSeqList(SeqList* ps1, SLDataType targ)
{
	assert(ps1);

	CheckCapacity(ps1);

	SLDataType end = ps1->size;

	while (end > 0)
	{
		ps1->array[end] = ps1->array[end - 1];
		end--;
	}

	ps1->array[0] = targ;
	ps1->size++;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

​

​ 小经验：一般free或realloc报错是因为下标逻辑有误或者访问越界

3.2.4头删尾删

​ 删除就比插入简单了，对于尾删，只要把ps1->size-1不就行了吗？因为这个size表示表中有效数据个数，-1就是从后向前减少一个有效元素，那要不要把内容置为0呢？大可不必，下次要插入元素时会自动把它覆盖。

void PopBackSeqList(SeqList* ps1)
{
	assert(ps1);
	assert(ps1->size > 0);

	ps1->size--;
}
1
2
3
4
5
6
7

​ pop在这里是弹出的意思，也就是把尾部元素弹出，不过要注意先检查一下ps1->size有没有可能这次删完就变为负数了，防止越界，这里用assert检测。

​ 对于头删，直接让第一个元素往后的元素全部向前移动一位就行了，覆盖掉第一个元素。同时也要注意ps1->size的值不要越界。

void PopFrontSeqList(SeqList* ps1)
{
	assert(ps1);
	assert(ps1->size > 0);

	SLDataType begin = 0;
	for (begin = 1; begin < ps1->size; begin++)
	{
		ps1->array[begin - 1] = ps1->array[begin];
	}
	ps1->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.2.5在pos位置插入或删除

​ 我们这里的pos位置是基于数组下标的，具体如何插入的参考下图：

​ 注意检测传入的pos是否小于等于ps1->size，为什么是小于等于而不是小于？因为我们要让end初始值为ps1->size，从最后一个元素后面的空位开始把元素一个一个向后移动，这样移动结束标志就是end等于pos，再怎样都不会越界。

void InsertSeqList(SeqList* ps1, size_t pos, SLDataType targ)
{
	assert(ps1);
	assert(pos <= ps1->size);

	CheckCapacity(ps1);
	size_t end = ps1->size;

	while (end > pos)
	{
		ps1->array[end] = ps1->array[end - 1];
	}
	ps1->array[pos] = targ;
	ps1->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

​

​ 那删除呢？其实可以参考前面讲的头删，具体如图所示

​ 注意要先检测pos是否会越界，然后就是pos往后的所有元素全部向前移动一位。

void EraseSeqList(SeqList* ps1, size_t pos)
{
	assert(ps1);
	assert(pos < ps1->size);

	size_t begin = pos;
	while (begin < ps1->size - 1)
	{
		ps1->array[begin] = ps1->array[begin + 1];
		begin++;
	}

	ps1->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2.6修改元素

​ 这个就很简单了，直接在对应位置上覆盖即可。

void ModifySeqList(SeqList* ps1, size_t pos, SLDataType targ)
{
	assert(ps1);
	assert(pos < ps1->size);
	ps1->array[pos] = targ;

}
1
2
3
4
5
6
7

3.2.7查找元素

​ 在顺序表中查找目标元素，如果找到了就返回下标，如果找不到就返回-1。这里直接用遍历查找，因为对于较小的数据量而言，遍历查找便捷，有人可能想到二分查找时间复杂度为O(logn)而遍历查找为O(n)因而觉得用二分查找更好，其实不然，二分查找前提是数组要保证有序，我们的顺序表中本身就是无序的，若要使用二分查找还得先排个序，排序快的都要O(nlogn)，比O(n)大，没有必要用二分查找，这里遍历更好些，除非数据量很大。

int FindSeqList(SeqList* ps1, SLDataType targ)
{
	assert(ps1);

	size_t i = 0;
	for (i = 0; i < ps1->size; i++)
	{
		if (targ == ps1->array[i])
			return i;
	}

	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2.8为什么不建议缩容

​ 既然容量不够时需要扩容，那么容量较多的时候需不需要缩容以节省空间呢？并不建议这样做，在硬件较为发达的当下，时间资源相对于空间资源更加宝贵，况且这里缩容节省下来的空间相对而言没有多少，也不缺这点空间，但是缩容也是要付出代价的：使用realloc不管是扩容还是缩容，都有可能“异地扩”或“异地缩”，也就是另寻一块合适的空间，把数据拷贝过去，然后再销毁原来空间，这样做对效率是有消耗的。如果容量一有空余就缩容，下次插入不还得再扩容吗，这样会使得扩容、缩容使用realloc调整内存更加频繁，完全是用时间换空间的做法，我们并不提倡这样做。而不设计缩容的话，遇到满容就扩容，删除元素不缩容，下次再插入就有可能不用扩容（使用空余的容量），这是用空间换时间的做法，性价比更高。

3.3顺序表的优缺点

优点

1. 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。

   因为顺序表中元素的逻辑关系和物理关系一致。

2. 可以快速地存取表中任意位置的元素。

   直接根据下标可以找到表的任一元素所在位置而取出元素，也可以找到表的任一位置而放入元素，时间复杂度仅为O(1)。

缺点

1. 插入和删除操作需要移动大量元素，时间复杂度为O(n)。
2. 当顺序表长度变化较大时，难以确定容量大小，扩容的多了有可能浪费较多空间。
3. 增容需要申请新空间，有可能“异地扩”，另寻空间，拷贝数据，释放旧空间。会有不小的消耗

4.链表

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

​ 实际中链表的结构非常多样 ，

1. 单向或者双向

   

2. 带头或者不带头

   

3. 循环或者非循环

   

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

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
   构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
   是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
   来很多优势，实现反而简单了。

4.1单链表

​ 单链表顾名思义就是单向的链表，链表与顺序表不同，链表在物理结构上是松散无序的，链表的基本组成单元我们称为结点，一个结点包括了数据和下一个结点的地址，通过指针就能把各个结点串联起来了。

结点的声明

​ 声明一个结构体作为结点模板，包括数据和下一个结点指针。这里的命名仅供参考，个人风格明显，实际上能够准确表达意思即可。

typedef int SLLDataType;
typedef struct SLinkListNode
{
	SLLDataType data;
	struct SLinkListNode* next;
}SLLNode;

1
2
3
4
5
6
7

创建结点

​ 我们要创建链表并进行各种操作，首先得创建结点，因为结点是链表的基本组成单位。由于创建结点这一行为在各种操作中可能会被广泛使用，我们不妨封装成一个函数。那好，结点能是临时的吗？不能，所以我们要把结点创建在堆区上，使用malloc开辟动态内存，把地址交给一个指针，再把这个指针保管的地址返回，返回这一步很重要！注意判断结点是否开辟成功，不成功的话也就搞不下去了，直接exit退出程序。在返回结点指针之前，先通过指针把结点初始化，其中的next指针得置为NULL。

SLLNode* CreateSLLNode(SLLDataType data)
{
	SLLNode* node = (SLLNode*)malloc(sizeof(SLLNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->data = data;
	node->next = NULL;

	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

单链表头插

​ 与顺序表相比，单链表又是如何头插的呢？需要移动后面的数据吗？不需要，前面说过，链表的逻辑顺序是由指针链接实现的，也就是说，要把结点头插入链表，只需要改变指针链接的关系即可。

​ 我们先来看一个问题：头插函数的形参应该如何设计？是传入SLLNode*类型的吗？我们创建单链表，首先会定义一个指向SLLNode类型的指针pList也就是头指针，然后根据需要传入这个pList的值或地址。地址？为什么要传指针的地址呢？

​ 不知道读者的函数章节学的如何，我们知道，在函数传参时，形参是实参的一份临时拷贝，仅改变形参的值并不会影响实参，那如何通过形参来修改实参呢？那就把传值调用改成传址调用，把实参的地址传给形参，然后解引用形参就可以得到并改变实参的值。

​ 现在知道为什么要传入指针的地址了吗？因为我们要获取并修改这个指针的内容。那形参就要设计一个指针的指针类型也就是二级指针——SLLNode**。还有一件事，这个二级指针能不能为NULL？不能，因为它要接收的是头指针的地址，那么正常情况下传入头指针的地址会是NULL吗？绝对不会，那要是传入NULL了怎么说？那肯定就是传入出错，所以要及时检测出来，就用assert(ppHead) 来检测。

​ 为什么说要修改这个指针的内容呢？你想啊，要在头部插入一个结点，而头指针就是指向第一个结点的，插入就要改变指向关系，让头指针pList指向新插入的结点，所以要改变头指针。

​ 那好了，讲了这么一大堆，到底怎么实现函数呢？

​ 先创建新结点，这一步可以直接复用CreateSLLNode函数，再改变指向关系，那头指针就肯定得指向新结点嘛，设新结点指针为newNode，接收pList的二级指针为ppHead，那不就是*ppHead = newNode; 了嘛，搞定~…个屁啊！！哪里搞定了呀？如果原来链表为空倒还好，但是链表不为空的话这样做完全有问题。

​ 问题在哪？这样做只是把新结点的地址给了头指针pList，那原来头指针指向的结点不就“断了线”吗？单链表具有严格的单向关系，只有头指针指向头结点，把头指针内容一改，不再指向原来的头结点，那不就没有方法再找到原来的头结点了吗？就好像警察局派遣卧底到黑帮，由于是绝密的，所以只有上一级唯一知道下一级是卧底，其他人都不知道，那如果上一级完蛋了，不就没有人知道卧底其实是警察而不是黑帮了吗？

​ 如何修改？先把头指针的内容拷贝给新结点的next指针，这样新结点就指向了原来的头结点，再把新结点的地址拷贝给头指针，这样头指针就指向了新结点，同时还断开了头指针和原来的头结点的关系，这不就插好了嘛。

void PushFrontSLList(SLLNode** ppHead, SLLDataType tar)
{
    assert(ppHead);
    
    SLLNode* newNode = CreateSLLNode(tar);
    
    newNode->next = *ppHead;
    *ppHead = newNode;
    
}
1
2
3
4
5
6
7
8
9
10

单链表尾插

​ 尾插函数的形参也要是二级指针的，为啥？你尾插又不关头指针的事，需要吗？需要，如果链表为空，是不是就变成了和头插类似？只需要把newNode的值给头指针pList，让头指针指向新结点即可。

​ 当链表不为空时，先创建新结点，要从尾部插入结点，关键在于让尾结点的next指针指向新结点，那是不是要先找到尾结点啊，怎么找？还能怎么找，遍历过去呗。创建指针tail找尾，如果指向的结点的next指针不为NULL，就说明指向的结点还不是尾结点，那就继续向后找tail = tail->next; ，直到找到尾结点为止。

void PushBackSLList(SLLNode** ppHead, SSLDataType tar)
{
    assert(ppHead);
    
    SLLNode* newNode = CreateSLLNode(tar);
    
    if(*ppHead = NULL)
        *ppHead = newNode;
    else
    {
        SLLNode* tail = *PPHead;
        while(tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newNode;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

单链表头删

​ 有人可能会说，这我知道，这还不简单吗，直接把第二个结点的地址给头指针pList，这样头指针就不再指向原来的头结点了，转而指向原来的第二个结点，这不就搞定了吗？NO!其实少了重要的一个步骤——释放内存！

​ 在研究顺序表的时候，我们需不需要每删除一个元素就释放一次内存？完全不需要嘛，顺序表要释放是一起释放的，因为它们是一块儿申请的。但是啊，对于链表各结点，它们可是分别独立地创建的，而且是在堆区创建的，要删除的话就得把它的内存也一块儿释放掉，不然一旦删除了链接关系而没有释放内存，就再也无法释放该块内存从而造成内存泄漏。

​ 所以要先备份pList的值，再把pList改成指向第二个结点，最后用备份的pList释放掉删除的结点。

​ 如果链表已经为空还能再删吗？不能，这样做会对NULL指针解引用，程序会崩溃。所以我们还得检测一下*ppHead是不是NULL。

void PopFrontSLList(SLLNode** ppHead)
{
    assert(ppHead);
    assert(*ppHead);
    
    SLLNode* del = *ppHead;
    *ppHead = (*pphead)->next;
    free(del);
}
1
2
3
4
5
6
7
8
9

单链表尾删

​ 首先明确一个问题，链表为空能不能再删？不能，理由在讲头删时讲过了。

​ 要尾删，是不是要先找到尾，那就是要先找尾，但是，这里的找尾和尾插时的找尾可不太一样。如果直接找到尾，然后释放掉，这时候会有什么问题？对啦，会出现野指针！因为尾结点前一个结点的next指针还保留着尾结点的地址，尾结点释放后，这个指针就是指向未知内存的野指针了。所以在这里，找尾并不是要真的找到尾，只需要找到尾的前一个结点就行了，可以怎么找？设指针tail，tail->next->next 就是下个结点的next指针，只要它不为NULL就tail = tail->next 向后移动，直到下个结点的next指针为NULL就说明下个结点就是尾结点，此时tail指向的就是尾结点的前一个结点，然后就释放掉尾结点并且把tail指向的结点的next指针置为NULL即可。

void PopBackSLList(SLLNode** ppHead)
{
    assert(ppHead);
    assert(*ppHead);
    
    if((*ppHead)->next = NULL)
        PopFrontSLList(ppHead);
    else
    {
        SLLNode* tail = *ppHead;
        while(tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

单链表查找

​ 类似于顺序表的查找，单链表的查找直接一个一个比对，不过找到了返回的不是下标，这里也没有下标可言，那返回什么呢？返回结点的地址。

SLLNode* FindSLList(SLLNode* pHead, SLLDataType tar)
{
    SLLNode* tmp = pHead;
    
    while(tmp->next != NULL)
    {
        if(tmp->data == tar)
            return tmp;
        tmp = tmp->next;
    }
    
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单链表修改

​ 修改的前提是什么？得先找到要修改的元素的位置所在，所以可以使用查找函数，找到位置后直接把值改了就好。

void ModifySLList(SLLNode* pHead, SLLDataType tar, SLLDataType mod)
{
	assert(pHead);
	SLLNode*  tmp= FindSLList(pHead, tar);
	tmp->data = mod;
}
1
2
3
4
5
6

单链表插入

​ 一般讲插入都是在某个位置前面插入，设某位置为pos，能不能在pos后面插入呢？都可以，只不过对于单链表来说前插麻烦些，为什么？因为单链表的关系是单向的啊，在pos前面插入就必须要有pos前一个结点的信息，而pos无法得到前一个结点的位置。不过虽然麻烦点，但是还是可以实现的，我们先来看前插。

​ 如何得到前面结点的信息？创建指针prev，只要prev->next不为pos也就是下一个结点不是pos所在结点就继续往后找，直到找到为止，找到的话prev就指向pos前一个结点了。这时候插入新结点，先把pos的值给新结点的next指针，这样新结点就指向pos位置的结点，再把新结点的地址给prev的next指针，这样prev位置的结点就指向新结点了，这样就完成了插入。要注意有可能找不到pos，这种情况一般是pos传的有问题，属于异常情况，用assert(pos)检测一下即可。

​ 那要是pos指向的是第一个结点呢？那不就变成头插了吗，直接复用头插函数就行了。

void InsertSLList(SLLNode** ppHead, SLLNode* pos, SLLDataType tar)
{
    asseert(ppHead);
    assert(pos);
    
    if(*ppHead == pos)
        PushFrontSLList(ppHead, tar);
    else
    {
    	SLLNode* prev = *ppHead;
        SLLNode* newNode = CreateSLLNode(tar);
        while(prev->next != pos)
    	{
            prev = prev->next;
            assert(prev);
        }
   		newNode->next = pos;
        prev->next = newNode;
    }
   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

​ 那么后插如何实现呢？其实更简单些，先把pos->next的值给新结点的next指针，让新结点指向pos后面的结点，再把新结点的地址给pos的next指针，让pos位置的结点指向新结点，这样就完成了插入。

void InsertAfterSLList(SLLNode* pos, SLLDataType tar)
{
    assert(pos);
    
    SLLNode* newNode = CreateSLLNode(tar);
    newNode->next = pos->next;
    pos->next = newNode;
}
1
2
3
4
5
6
7
8

	在pos位置之前插入需要改变pos位置前一个结点的指向关系，就要拿到该结点，由于单链表的结构特性，pos位置的结点无法找到前一个结点，就需要从头去找pos位置前一个结点，比较麻烦。
	而要是在pos位置之后插入，pos位置的结点就是要插入结点的前一结点，这时候要修改指向关系就很方便了。
1
2

进阶思考

​ 在pos位置前插入，要求时间复杂度为O(1)。

思路：替换法插入

​ 这要求什么意思呢？我们原来要在pos位置的前面插入结点是不是要先找到pos位置前面的结点呀，那可不可以不找就实现插入了呢？

​ 我们先在pos位置后面插入一个结点，再把pos位置结点的data值和新插入结点的值交换一下，这样是不是就可以了呢？妙啊~🤩

void InsertSLList(SLLNode* pos， SLLDataType tar)
{
    assert(pos);
    
    SLLNode* newNode = CreateSLLNode(tar);
    newNode->next = pos->next;
    pos->next = newNode;
    
    SLLDataType tmp = pos->data;
    pos->data = newNode->data;
    newNode->data = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

​ 算是使用了InsertAfterSLList的思路而克服了InsertSLList的一些缺点，比如说时间复杂度更低了。

​ 缺陷：无明显缺陷

单链表移除

​ 其实单链表移除也有两种，一是移除pos当前位置结点，二是移除pos位置后面一个结点。

​ 先看第一种。有没有可能pos指向的是第一个结点？那这时候是不是就变成头删啦？直接复用头删函数。当pos不指向头结点时，如何移除结点？可以参考一下尾删的思路，我们要找到pos前一个结点，然后把pos的值先拷贝到一个指针中，再把pos->next的值给前一个结点的next指针，这样就改变了前一个结点的指向，越过pos位置的结点转而指向pos后面一个结点，最后再把pos位置的结点释放即可。要注意一下，链表为空时就不能再删了，所以要检测一下assert(*ppHead)。

void EraseSLList(SLLNode** ppHead, SLLNode* pos)
{
    assert(ppHead);
    assert(pos);
    assert(*ppHead);

    if(*ppHead == pos)
        PopFrontSLList(ppHead);
    else
    {
        SLLNode* prev = *ppHead;
        while(prev->next!= pos)
        {
            prev = prev->next;
            assert(prev);
        }
        prev->next = pos->next;
        free(pos);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

​ 第二种删后面的就比较简单了，也是可以参考尾删，先把pos后面一个结点的地址放到创建的del指针，把pos下一个结点的next指针给pos位置结点的的next指针，从而让pos位置结点的next指针指向下下个结点，然后再通过del指针释放pos后面一个结点。要注意，链表只有一个结点时就无法再删除了，所以要检测一下，assert(pos->next) 。

void EraseAfterSLList(SLLNode* pos)
{
    assert(pos);
    assert(pos->next);

    SLLNode* del = pos->next;
    pos->next = pos->next->next; 
   	free(del);
}
1
2
3
4
5
6
7
8
9

	删除pos位置的结点同样需要拿到前一结点去修改指向关系，由于单链表的结构特性，pos位置的结点无法找到前一个结点，就需要从头去找pos位置前一个结点，比较麻烦。
	而要是删除pos位置后一个结点，那就方便多了，pos位置的结点就是要删除结点的前一结点，直接就可以修改指向关系了。
1
2

进阶思考

​ 删除pos位置结点，但是要求是时间复杂度为O(1)。

**思路：**替换法删除

​ 这个要求是什么意思呢？原来我们要删除pos位置结点是不是还要去找到pos前面的结点？是不是就要从头去找？那可不可以不用pos前面的结点而实现pos位置结点的删除呢？

​ 在这种情况下，由于单链表本身的结构特性，我们无法直接删除pos位置的结点，但是我们不是可以删除pos后面的一个结点吗？那可不可以先把pos位置的结点的data值和它后面结点的值交换一下，然后再把它后面结点给删掉，来一手“狸猫换太子”。

void EraseSLList(SLLNode* pos)
{
    assert(pos);
    assert(pos->next);
    
    SLLDataType tmp = pos->data;
    pos->data = pos->next->data;
    pos->next->data = tmp;
    
    SLLNode*del = pos->next;
    pos->next = pos->next->next;
    free(del);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

​ 本质上就是EraseAfterSLList的改进版，所以也有着相同的缺陷。

​ 缺陷：pos不能是尾结点。

单链表打印

​ 把每个结点的data打印出来，直接像找尾一样向后遍历，遇到NULL打印NULL；

void PrintSLList(SLLNode* pHead)
{
	while (pHead)
	{
		printf("%d->", pHead->data);
		pHead = pHead->next;
	}
	if (pHead == NULL)
		printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

单链表销毁

​ 单链表的销毁就是要把剩下的所有结点全部释放掉，怎么实现？定义两个指针cur和next，一前一后，如果只定义一个指针cur，那么释放完当前结点后就找不到后面的结点了，所以在释放之前要先把下一个结点的地址放到next指针，等释放完后再把地址转交给cur，再向后移动释放后面的结点。链表为空不用担心，因为这种情况下函数什么也不干。

void DestorySLList(SLLNode** ppHead)
{
	assert(ppHead);

	SLLNode* cur = *ppHead;
	SLLNode* next = cur->next;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

带头单链表

​ 这里的头指的是哨兵头结点，里面存的值不是有效数据，该结点只是作为辅助结点。

​ 设计为带头单链表就不需要在头插尾插和插入移除等函数中传入二级指针了，因为不会改变头指针。

​ 单链表实际运用中很少带头，OJ题也基本不带头，所以相对来说不怎么深入带头的单链表，有些题可能会用到带哨兵结点的思路。

总结

​ 单链表只适合头插头删，时间复杂度都是O(1)，其他的操作其实都不太高效。所以什么时候用单链表呢？只需要头插、头删或者只用于作为其他数据结构的子结构时比较适用，不然一般都不会单独使用。

​ 任意位置高效插入删除——双向链表。

刷题推荐

1. 删除链表中等于给定值 val 的所有结点。 203. 移除链表元素 - 力扣（LeetCode）
2. 反转一个单链表。206. 反转链表 - 力扣（LeetCode）
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则
   返回第二个中间结点。876. 链表的中间结点 - 力扣（LeetCode）
4. 输入一个链表，输出该链表中倒数第k个结点。 链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有
   结点组成的。21. 合并两个有序链表 - 力扣（LeetCode）
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结
   点之前 。链表分割_牛客题霸_牛客网 (nowcoder.com)
7. 链表的回文结构。链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
8. 输入两个链表，找出它们的第一个公共结点。160. 相交链表 - 力扣（LeetCode）
9. 给定一个链表，判断链表中是否有环。141. 环形链表 - 力扣（LeetCode）
10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL。142. 环形链表 II - 力扣（LeetCode）
11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点
    或空结点。要求返回这个链表的深度拷贝。 138. 复制带随机指针的链表 - 力扣（LeetCode）

4.2带头双向循环链表

​ 我们前面学习的就是最最简单的链表结构——无头单向非循环链表，接下来就要学习最复杂的一种链表结构。

​ 这种结构可以完美解决顺序表的缺陷，具体的优势在逐步实现的时候就能慢慢体会到了。

结点的声明

​ 相比于单链表，这里就只是多了个指向前面结点的指针。

typedef int DLLDataType;

typedef struct DLinkListNode
{
	DLLDataType data;
	struct DLinkListNode* prev;
	struct DLinkListNode* next;
}DLLNode;
1
2
3
4
5
6
7
8

初始化链表

​ 由于是带头链表，我们初始化时要创建哨兵头结点，然后把两个指针都指向自己，这就是带头双向循环链表的初始状态，此时链表为空时（这里指的是有效结点为空，哨兵头结点算是辅助结点），函数返回哨兵头结点的地址，外面再用一个头指针接收，DLLNode* pList = InitDLList(); 。

DLLNode* InitDLList()
{
	DLLNode* guard = (DLLNode*)malloc(sizeof(DLLNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->prev = guard;
	guard->next = guard;
	
	return guard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

创建结点

​ 没什么好讲的。

DLLNode* CreateDLLNode(DLLDataType tar)
{
	DLLNode* newNode = (DLLNode*)malloc(sizeof(DLLNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = tar;
	newNode->prev = NULL;
	newNode->next = NULL;

	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

尾插结点

​ 由于带上了哨兵结点，所以各个函数都可以不用传二级指针了，因为不会再修改头指针了。同时链表也不可能为空，所以传入指针为空的情况是异常情况，需要检测。

​ 尾插很容易，单链表的话还需要特意遍历找尾结点，但是带头双向循环链表就不需要这么麻烦了，要找到尾结点，只需要哨兵头结点的prev指针就行，因为头尾是通过两个指针连在一起了的。让要插入的结点先和原来的尾结点互相链接，此时循环链接断开，新插入的结点作为新的尾结点，再把循环链接补上。

​ 即使是链表为空（这里指的是有效结点为空，哨兵头结点算是辅助结点）也是相同的做法，不需要额外分情况。

代码实现

void PushBackDLList(DLLNode* pHead, DLLDataType tar)
{
    assert(pHead);
    
    DLLNode* newNode = (DLLNode*)malloc(sizeof(DLLNode));
    
    pHead->prev->next = newNode;
    newNode->prev = pHead->prev;
    newNode->next = pHead;
    pHead->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

头插结点

​ 很简单，但是要注意一下链接的顺序，应该先改变新结点和后面结点的关系，然后再改变新结点与哨兵头结点的关系。

void PushFrontDLList(DLLNode* pHead, DLLDataType tar)
{
    assert(pHead);
    
    DLLNode* newNode = (DLLNode*)malloc(sizeof(DLLNode));
    
    pHead->next->prev = newNode;
    newNode->next = pHead->next;
    newNode->prev = pHead;
    pHead->next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11

尾删结点

​ 只要是删除结点就要先判断一下链表是否为空，我们这里直接封装一个函数，链表为空返回真，不为空返回假。实现逻辑很简单，要是链表为空（这里指的是有效结点为空，哨兵头结点算是辅助结点）的话哨兵头结点的prev和next指针就会指向它自己。

bool DLListEmpty(DLLNode* pHead)
{
    assert(pHead);
    
	return pHead->next == pHead;    
}
1
2
3
4
5
6

​ 尾结点很容易通过哨兵头结点找到，找到尾结点的话它前面一个结点也能通过prev指针找到，让它前面一个结点作为新的尾结点，改变循环链接关系，再把原来的尾结点free掉即可。

void PopBackDLList(DLLNode* pHead)
{
    assert(pHead);
    assert(!DLListEmpty(pHead));
    
   	DLLNode* tail = pHead->prev;
    DLLNode* tail_prev = tail->prev;
    
    pHead->prev = tail_prev;
    tail_prev->next = pHead;
    free(tail);
}
1
2
3
4
5
6
7
8
9
10
11
12

头删结点

​ 头删也很简单就能实现，而且不需要分情况考虑，因为即使是删掉第一个有效结点后链表为空（这里指的是有效结点为空，哨兵头结点算是辅助结点）也只是变回了初始状态，无论链表状态如何都用同样的思路进行头删。

​ 设置两个指针，指针first指向第一个有效结点，second指向第二个有效结点，改变链接关系，让哨兵头结点直接和second指向结点链接，释放掉first指向结点。

void PopFrontDLList(DLLNode* pHead)
{
    assert(pHead);
    assert(!DLListEmpty(pHead));
    
    DLLNode* first = pHead->next;
    DLLNode* second = first->next;
    
    pHead->next = second;
    second->prev = pHead;
    free(first);
}
1
2
3
4
5
6
7
8
9
10
11
12

求取链表长度

​ 这个一般都直接遍历用计数器计数即可。

size_t LengthOfDLList(DLLNode* pHead)
{
    assert(pHead);
    size_t cnt = 0;
    DLLNode* cur = pHead->next;
    
    while(cur != pHead)
    {
        cnt++;
        cur = cur->next;
    }
    
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

查找结点

​ 这个也很简单，直接遍历查找即可，在查找以后如果有修改需求可以直接修改，就不需要额外封装一个修改函数了。

DLLNode* FindDLList(DLLNode* pHead, DLLDataType tar)
{
    assert(pHead);
    
    DLLNode* cur = pHead->next;
    
    while(cur != pHead)
    {
        if(cur->data == tar)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入结点

​ 由于是双向循环链表，实际上插入可以统一操作思路，头插尾插可以复用插入函数，一般来说插入函数是在目标位置pos前面插入结点，我们就再创建一个指针prev指向pos前一结点，要插入新结点的话直接修改链接关系即可。

void InsertDLList(DLLNode* pos, DLLDataType tar)
{
    assert(pos);
    
    DLLNode* prev = pos->prev;
    DLLNode* newNode = CreateDLLNode(tar);
    
    prev->next = newNode;
    newNode->prev = prev;
    newNode->next = pos;
    pos->prev = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

头插函数可以改为：

void PushFrontDLList(DLLNode* pHead, DLLDataType tar)
{
    assert(pHead);
    InsertDLList(pHead->next, tar);
}
1
2
3
4
5

尾插函数可以改为：

void PushBackDLList(DLLNode* pHead, DLLDataType tar)
{
    assert(pHead);
    InsertDLList(pHead, tar);
}
1
2
3
4
5

删除结点

​ 由于是双向循环链表，实际上删除也可以统一操作思路，头删尾删可以复用删除函数，一般来说删除函数是删除目标位置pos的结点，我们创建两个指针一前一后，也就是将pos前后的结点直接链接起来，再释放掉pos位置的结点。

void EraseDLList(DLLNode* pos)
{
    assert(pos);
    
    DLLNode* prev = pos->prev;
    DLLNode* next = pos->next;
    
    prev->next = next;
    next->prev = prev;
    free(pos);
}
1
2
3
4
5
6
7
8
9
10
11

头删函数可以改为：

void PopFrontDLList(DLLNode* pHead)
{
    assert(pHead);
    EraseDLList(pHead->next);
}
1
2
3
4
5

尾删函数可以改为：

void PopBackDLList(DLLNode* pHead)
{
    assert(pHead);
    EraseDLList(pHead->prev);
}
1
2
3
4
5

打印链表

​ 打印链表是不是得遍历链表呀，不过没有NULL指针怎么让它停下来呢？既然是从头开始的，那就也从头结束，就是说从头结点开始遍历直到再次回到头结点就结束。

void PrintDLList(DLLNode* pHead)
{
    asssert(pHead);
    printf("pHead<=>");
    DLLNode* cur = pHead->next;
    while(cur != pHead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

销毁链表

​ 和单链表差不多的思路，遍历链表一个一个结点释放呗，要记得先把下一个结点地址暂存一下，在释放掉当前结点后更新指针，哨兵头结点要最后释放。其实这样销毁以后还要求用户自己把头指针置为NULL，不然就是野指针。

void DestoryDLList(DLLNode* pHead)
{
    assert(pHead);
    
    DLLNode* cur = pHead->next;
    while(cur != pHead)
    {
        DLLNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(pHead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.3总结

顺序表和链表的区别

顺序表的优势

1. 尾插尾删效率高

2. 支持随机访问（下标访问）

3. cpu高速缓存命中率更高

顺序表的缺陷

1. 头部和中间的插入效率低——O(n)

2. 扩容时可能：性能消耗+空间浪费

链表优势

1. 任意位置插入删除效率很高——O(1)
2. 按需申请和释放+不存在空间浪费

链表缺陷

1. 不支持随机访问

关于“cpu高速缓存命中率更高”的简单解释：

​ cpu执行指令，不会直接访问内存。

1. 先看数据在不在三级缓存，如果在就是命中，直接访问缓存
2. 如果不在就是不命中，先把数据加载到换存，再访问缓存

​ 而且数据加载到缓存是一次一块的，如果需要的数据在物理结构上临近的话直接就把一整块加载到缓存了，顺序表就是这样的，命中率就更高，而链表的各个结点在物理结构上是松散无关联的，命中率就更低。