问题：

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

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

💯链表的概念及结构

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

“链表就像火车，一个车厢一个车厢通过车钩链接在一起 ”

注意:

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

💯链表的分类

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

1.单向或双向

2.带头或者不带头

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);

⭐链表创建

typedef int SLTDateType;
typedef struct SListNode
{
    SLTDateType data;//该结构体的数据
    struct SListNode* next;//指向下一个结构体
}SListNode;

struct SListNode* next 用于存放下一个结构体的地址，可通过解引用进行访问

代码理解：

⭐单链表打印

void SLTPrint(SLTNode*phead)
{
    SLTNode* cur = phead;
    while(cur != NULL)
    {
        printf("%d->",cur->data);
        cur =cur->next;
    }
    printf("NULL\n");
}

⭐单链表尾插

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

⭐单链表头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

“单链表头插的时候为什么要传二级指针？”

1. 理解单链表结构

在单链表中，每个节点包含数据域和指向下一个节点的指针域。单链表通过头指针来标识整个链表。

2. 头插法操作

当进行头插操作时，要在链表头部插入一个新节点。如果只传一级指针（即头指针），在函数内部对这个指针进行修改（使其指向新插入的节点），这种修改只是在函数内部有效。
因为C语言中函数参数传递是值传递，对于指针来说，传递的是指针的值（即地址值）。如果只传一级指针，函数内部修改这个指针并不会影响到函数外部的指针。
传二级指针就不同了。二级指针指向的是头指针的地址。在函数内部通过二级指针修改头指针的值，就可以真正改变链表的头指针，使得在函数外部也能看到链表头指针的更新。
例如，假设有函数void insertHead(struct Node **head, int data)，在函数内部*head就是原来的头指针，通过*head = newNode;（newNode是新插入的节点）这样的操作，就可以更新链表的头指针。

⭐单链表尾删

void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;


	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}	
}

⭐单链表头删

void SLTPopFront(SLTNode** pphead)
{
	// 暴力检查
	assert(*pphead);

	// 温柔的检查
	//if (*pphead == NULL)
	//	return;

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

💯双向链表的实现（带头双向循环链表）

// 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);

⭐双向链表创建

循环:

尾next指向哨兵位的头
哨兵位的头的prev指向尾

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

⭐双向链表销毁

void ListDestroy(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

⭐双向链表打印

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

⭐双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	 phead            tail  newnode
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

}

⭐双向链表尾删

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}

⭐双向链表头插

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* newnode = BuyListNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;

	
	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;

}

⭐双向链表头删

void LTPopFront(LTNode* phead)
{
	LTNode* fro = phead->next;
	LTNode* second = fro->next;
	phead->next = second;
	second->prev = phead;
	free(fro);
	fro = NULL;
}

⭐双向链表查找pos

ListNode* ListFind(ListNode* phead, LTDateType x)
{
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->date == x) return cur;
		cur = cur->next;
	}
	return NULL;
}

⭐双向链表pos前面进行插入

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// prev newnode pos

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

⭐双向链表在pos的删除

void ListErase(ListNode* pos)
{
	ListNode* next = pos->next;
	ListNode* prev = pos->prev;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

💯传指针的困惑

你是否有这样的疑问：😖“什么时候传一级指针，什么时候传二级指针？”

⭐传递一级指针的情况

1.当需要修改函数外部一个变量的值时：

如果只需要在函数内部修改一个普通变量的值，并将这个修改反映到函数外部，可以传递该变量的地址，即一级指针。
例如，以下代码中，通过传递一级指针来修改num的值：
void increment(int *ptr) {
    (*ptr)++;
}

int main() {
    int num = 5;
    increment(&num);
    printf("%d\n", num); // 输出 6
    return 0;
}

2.当处理动态分配的单个对象时：

如果在程序中动态分配了一个内存空间（如使用malloc或new），并且希望函数能够操作这个对象，可以传递指向该对象的指针，即一级指针。
例如，对于一个动态分配的结构体：
struct Person {
    char name[20];
    int age;
};

void setPersonInfo(struct Person *personPtr) {
    strcpy(personPtr->name, "John");
    personPtr->age = 30;
}

int main() {
    struct Person *p = (struct Person *)malloc(sizeof(struct Person));
    setPersonInfo(p);
    free(p);
    return 0;
}

⭐传递二级指针的情况

1.当需要在函数内部修改指针本身时：

如果希望函数能够修改一个指针变量的值，使其指向不同的内存地址，就需要传递指向这个指针的指针，即二级指针。
例如，以下代码中，changePointer函数通过二级指针修改了ptr所指向的地址：
void changePointer(int **ptr) {
    int *newPtr = (int *)malloc(sizeof(int));
    *newPtr = 10;
    *ptr = newPtr;
}

int main() {
    int *p = NULL;
    changePointer(&p);
    printf("%d\n", *p); // 输出 10
    free(p);
    return 0;
}

2.当处理动态分配的数组时：

如果动态分配了一个数组，并且希望函数能够重新分配这个数组的大小或者修改数组的首地址，通常需要传递指向数组指针的指针（二级指针）。
例如：
void resizeArray(int **arrPtr, int newSize) {
    int *newArr = (int *)realloc(*arrPtr, newSize * sizeof(int));
    *arrPtr = newArr;
}

int main() {
    int *arr = (int *)malloc(5 * sizeof(int));
    resizeArray(&arr, 10);
    free(arr);
    return 0;
}

总之，传递一级指针主要用于修改普通变量的值或操作单个对象，而传递二级指针通常用于修改指针本身或者处理动态分配的数组等需要修改指针指向的情况。