1 定义

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表解决了顺序表带来的弊端。
特点：按需向堆申请内存，不用了就释放空间
优点：增删数据不需要挪动数据；不存在空间浪费
缺点：每存一个数据都要存一个指针去链接后面的数据节点；不支持随机访问

2 分类

2.1 单向或双向

在这里插入图片描述

2.2 带头或不带头

在这里插入图片描述

2.3 循环或非循环

在这里插入图片描述

原理：
phead头节点是一个指针，存的是链表第一个值的地址，

3 实现

3.1 不带头单向不循环链表SList

每个节点的结构体包括一个值和一个指向下一个节点的指针

3.1.1 代码实现

// SList.h
#pragma once
#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
// 打印
void SListPrint(SLTNode* phead);
// 创建结点
SLTNode* BuyListNode(SLTDataType x);
// 尾插
void SListPushBack(SLTNode** phead, SLTDataType x);
// 头插
void SListPushFront(SLTNode** phead, SLTDataType x);
// 尾删
void SListPopBack(SLTNode** pphead);
//头删
void SListPopFront(SLTNode** pphead);
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 任意位置插入
// 在pos之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos之后插入
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 任意位置删除
// 删除当前位置pos
void SListErase(SLTNode** pphead, SLTNode* pos);
// 删除pos之后的
void SListEraseAfter(SLTNode** pphead, SLTNode* pos);

// 销毁
void SListDestroy(SLTNode** pphead);

// SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//typedef struct SListNode
//{
//	SLTDataType data;
//	struct SListNode* next;
//}SLTNode;

//  创建节点
SLTNode* BuyListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//打印
void SListPrint(SLTNode* phead) {
	SLTNode* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** phead, SLTDataType x) {
	/*SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;*/

	SLTNode* newnode = BuyListNode(x);
	if (*phead == NULL) {
		*phead = newnode;
	}
	else {
		SLTNode* tail = *phead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

// 头插
void SListPushFront(SLTNode** phead, SLTDataType x) {
	SLTNode* newnode = BuyListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}
// 尾删
void SListPopBack(SLTNode** pphead) {
	assert(*pphead != NULL);
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next->next) {
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
//头删
void SListPopFront(SLTNode** pphead) {
	if (*pphead == NULL) {
		return;
	}
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x) {
	SLTNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		else {
			cur = cur->next;
		}
	}
	return NULL;
	/*while (cur) {
		if (cur->data == x) {
			break;
		}
		cur = cur->next;
	}
	if (cur != NULL) {
		return cur;
	}
	else {
		printf("没找到\t");
		return NULL;
	}*/
}
// 任意位置插入
// 在pos之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	// 头节点，相当于头插
	if (pos == *pphead) {
		SListPushFront(pphead, x);
	}
	else {
		// 找到pos的前一个位置prev
		SLTNode* newnode = BuyListNode(x);
		SLTNode* prev = *pphead; // 
		while (prev->next) {
			if (prev->next == pos) {
				break;
			}
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}

}
// 在pos之后插入
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {

	assert(pos);

	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

// 任意位置删除
// 删除当前位置pos
void SListErase(SLTNode** pphead, SLTNode* pos) {
	assert(pos);
	assert(*pphead);
	// pos是头节点
	if (*pphead == pos) {
		/*if (pos->next == NULL) {
			*pphead = NULL;
		}
		else {*/
		// 如果只有一个节点pos那pos->next本来也是null，不用分类
		*pphead = pos->next;
		free(pos);
		//}
	}
	else {
		SLTNode* prev = *pphead;
		// pos的前一个
		while (prev->next != pos) {
			prev = prev->next;
		}
		// pos = pos->next;

		prev->next = pos->next;
		free(pos);
	}
}
// 删除pos之后的值
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	SLTNode* next = pos->next;

	pos->next = next->next;
	free(next);

}
// 销毁
 所有节点都要释放，避免内存泄漏
//void SListDestroy(SLTNode** pphead) {
//	free(*pphead);
//	*pphead = NULL;
//}
void SListDestroy(SLTNode** pphead) {
	SLTNode* cur = *pphead;
	while (cur) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;// plist置空
}

// 测试用例
// Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void TestSList1()
{
	printf("TEST1：\n");
	SLTNode* plist = NULL;// 初始化
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 7);
	SListPushFront(&plist, 6);
	SListPrint(plist);

	// 6 7 2 1 2 3 4
	SListPopBack(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	// 1 2 3 
	//SListPopFront(&plist);
	SListPrint(plist);
	printf("TEST1 END\n");
	SListDestroy(&plist);
}
void TestSList2()
{
	printf("TEST2：\n");
	SLTNode* plist = NULL;// 初始化
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 2);
	// 2 1 2 3 4
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 1);
	SListEraseAfter(&plist, pos);
	SListErase(&plist, pos);
	// 2 3 4
	SListPrint(plist);
	pos = SListFind(plist, 2);
	SListInsert(&plist, pos, 5);
	SListInsertAfter(&plist, pos, 9);
	// 5 2 9 3 4
	SListPrint(plist);
	pos = SListFind(plist, 8);
	printf("%p\n", pos);
	printf("TEST2 END\n");
	SListDestroy(&plist);
}

int main() {

	TestSList1();
	TestSList2();

	return 0;
}

3.1.2 运行结果

在这里插入图片描述

3.2 带头双向循环链表List

每个节点的结构体包括一个值，一个指向上一个节点的指针和一个指向下一个节点的指针

3.2.1 代码实现

// List.h
#pragma once
#include <stdio.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestroy(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

// List.c
#include "List.h"
#include <assert.h>
#include <stdlib.h>

//typedef struct ListNode
//{
//	LTDataType _data;
//	struct ListNode* _next;
//	struct ListNode* _prev;
//}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate() {
	ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
	if (pHead) {
		pHead->_next = pHead;
		pHead->_prev = pHead;
	}
	return pHead;
}
// 双向链表销毁
void ListDestroy(ListNode* pHead) {
	assert(pHead);
	ListNode* tail = pHead->_prev;
	while (tail != pHead) {
		ListNode* prev = tail->_prev;
		free(tail);
		tail = prev;
	}
	free(pHead);
}

ListNode* BuyListNode(LTDataType x) {
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode) {
		newNode->_data = x;
		newNode->_next = NULL;
		newNode->_prev = NULL;
	}
	return newNode;
}
// 双向链表打印
void ListPrint(ListNode* pHead) {
	ListNode* cur = pHead->_next;
	while (cur != pHead) {
		printf("%d -> ", cur->_data);
		cur = cur->_next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x) {
	/*ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = x;*/
	ListNode* newNode = BuyListNode(x);
	ListNode* tail = pHead->_prev;

	tail->_next = newNode;
	newNode->_prev = tail;
	newNode->_next = pHead;
	pHead->_prev = newNode;

}
// 双向链表尾删
void ListPopBack(ListNode* pHead) {
	assert(pHead);
	assert(pHead->_next != pHead);

	ListNode* tail = pHead->_prev;
	ListNode* prev = tail->_prev;
	prev->_next = pHead;
	pHead->_prev = prev;
	free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x) {
	/*ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = x;*/

	ListNode* newNode = BuyListNode(x);

	ListNode* head = pHead;
	ListNode* next = head->_next;
	newNode->_next = next;
	next->_prev = newNode;
	head->_next = newNode;
	newNode->_prev = head;
}
// 双向链表头删
void ListPopFront(ListNode* pHead) {
	assert(pHead);
	// 避免删掉哨兵位
	assert(pHead->_next != pHead);
	ListNode* head = pHead;
	ListNode* cur = head->_next;
	ListNode* next = cur->_next;
	head->_next = next;
	next->_prev = head;
	free(cur);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x) {
	ListNode* cur = pHead->_next;
	/*while (cur->_data != x) {
		cur = cur->_next;
		if (cur == pHead) {
			return NULL;
		}
	}
	return cur;*/
	while (cur != pHead) {
		if (cur->_data == x) {
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
	assert(pos);
	/*ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->_data = x;*/
	ListNode* newNode = BuyListNode(x);

	ListNode* prev = pos->_prev;

	newNode->_next = pos;
	prev->_next = newNode;
	pos->_prev = newNode;
	newNode->_prev = prev;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {
	assert(pos);
	ListNode* prev = pos->_prev;
	ListNode* next = pos->_next;
	prev->_next = next;
	next->_prev = prev;
	free(pos);
}

// Test.c
// 测试用例
#include "List.h"

void TestList1()
{
	ListNode* plist = ListCreate();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	// 4 3 2 1
	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	//ListPopBack(plist);
	ListPrint(plist);

}

void TestList2()
{
	ListNode* plist = ListCreate();
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	// 4 3 2 1
	ListPrint(plist);

	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	// 4 3 2 1 1 2 3 4
	ListPrint(plist);

	ListNode* pos = ListFind(plist, 2);
	if (pos)
	{
		ListErase(pos);
	}
	// 4 3 1 1 2 3 4
	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	// 1 1 2
	ListPrint(plist);

	ListDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList1();
	printf("\n");
	TestList2();

	return 0;
}

3.2.2 运行结果

在这里插入图片描述

4 顺序表vs链表

4.1 区别(优/缺点)：

4.1.1 顺序表：

优点：
1.支持随机访问；
2.CPU高速缓存命中率高；
缺点：
1.插入删除头部和中间元素的时间复杂度为O(n)，效率低；
2.为避免频繁开辟内存空间，会以倍数形式开辟空间，与此同时会带来空间浪费的问题。

4.1.2 链表（带头双向循环）

优点：
1.效率高，任意位置插入删除元素的时间复杂度都为O(1)；
2.按需申请和释放空间，没有空间浪费；
缺点：
1.不支持随机访问，从而导致一些算法不适用，比如二分查找，部分排序等；
2.每添加一个值都会附带存储链接指针，也会占用一定的资源（不过可忽略）；
3.CPU高速缓存命中率低。