链表（详解）

一、链表

1.1、什么是链表

1、链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。

2、结点包括两个部分：（1）存储数据元素的数据域（内存空间），（2）存储指向下一个结点地址的指针域。

3、相对于线性表顺序结构，操作复杂。

1.2、链表的分类

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

（1）单项和双向

（2）带头和不带头

（3）循环和不循环

1.3、链表和顺序表的比较

（1）数组：使用一块连续的内存空间地址去存放数据，但

例如：
int  a[5]={1,2,3,4,5}。突然我想继续加两个数据进去，但是已经定义好的数组不能往后加，只能通过定义新的数组

int b[7]={1,2,3,4,5,6,7};  这样就相当不方便比较浪费内存资源,对数据的增删不好操作。

（2）链表：使用多个不连续的内存空间去存储数据， 可以 节省内存资源（只有需要存储数据时，才去划分新的空间），对数据的增删比较方便

注意：

1.链式结构在逻辑上是连续的，但在物理上不一定连续

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

二、无头单向非循环链表

2.1、无头单向非循环链表的结构

链表有一个数据域存放数据，一个指针域存放下一个结点的地址。

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

2.2、无头单向非循环链表的实现

//打印
void SLTPrint(SLTNode* phead);

//创建一个新节点
SLTNode* BuySListNode(SLTDataType x);

//尾增
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头增
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

// 作业
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// 在pos以后插入x   
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 删除pos的后一个位置
void SLTPopAfter(SLTNode* pos);

// 单链表的销毁
void SListDestroy(SLTNode** pphead);

2.2.1、创建一个新节点

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

创建一个新节点，用malloc开辟一个链表节点空间，强制转换成链表结构体，将data置为X，将next置为空，并返回新节点。

2.2.2、单链表的尾插

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	//没有一个节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表的尾插首先需要判断是否是空链表，如果为空就把该节点置为头节点，若不为空，先便利找到尾结点，然后将新节点插入尾节点后面。

2.2.3、单链表的头插法

//单链表的头插法   效率高，简单
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插法相对简单，只需要将新节点插到头结点的前面，并且将头结点指针赋给新节点。

2.2.4、单链表的尾删

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//空
	assert(*pphead);
	// 1个节点
	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;*/

		//方法二
		SLTNode* tail = *pphead;
		SLTNode* tailprev = NULL;
		while (tail->next)
		{
			tailprev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		tailprev->next = NULL;

	}
}

和尾插法一样，首先先判断链表是否只有一个节点或者没有节点（为空），将会最后一个链表置空，如果超过一个节点，先找到倒数第二个节点，然后置空最后一个节点，将倒数第二个节点的next置空

2.2.5、单链表的头删法

//链表的头删法   效率高，简单
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

free第一个节点，将头指针后移一位。

2.2.6、单链表的查找

//查找元素  修改
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

借助cur指针，便利链表，cur=cur->next;若cur->data==x,返回cur,没找到返回NULL。

2.2.7、在pos之前插入

//在pos之前插入
//  传头指针是因为有可能时头插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTNode* newnode = BuySListNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

在pos位置插入，相对

2.2.8、在pos之后插入

//在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next=newnode;

}

2.2.9、删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos == NULL;  //可有可无，因为pos只是形参，对他的操作不影响外部的节点
	}
}

2.2.10、删除pos后一位置

//删除pos后一位置
void SLTPopAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next == NULL);
	SLTNode* posnext = pos->next;
	pos->next = posnext->next;
	free(posnext);
	posnext = NULL;
}
//删除一个pos,没有头节点
// 把pos下一个节点的值赋给pos,将下一个节点删除
//但是无法删除尾结点

2.2.11、单链表的销毁

//单链表的销毁
void SListDestroy(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* pre = *pphead;
	SLTNode* p = pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre->next);
	pre->next = NULL;
}

三、带头双向循环链表

双向链表的原理与单链表类似，双向链表需要两个指针来链接，一个指向前面的，一个指向后面的。同时需要一个head，头链表，方便操作。

3.1带头双向链表实现

3.1.1、创建结构体

typedef int DataType;
typedef struct ListNode
{
	struct ListNode *next;
	struct ListNode *pre;
	DataType data;
}LTNode;

此结构中比单链表结构增加一个结构体指针pre，用于存放上一个节点的地址。
next是存放一个节点的地址。
data是存放数据。

3.1.2、申请结点

LTNode* BuyListNode(DataType x)//申请结点
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror( "malloc fail");
		exit(-1);
	}
	node->next = NULL;
	node->pre = NULL;
	node->data = x;
	return node;
}

动态申请结点，函数返回的是一个指针类型，用malloc开辟一个LTNode大小的空间，并用node指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把要存的数据x存到newnode指向的空间里面，把指针置为空。

3.1.3、初始化创建头结点

LTNode* LTInit()//初始化创建头结点
{
	LTNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->pre = phead;
	return phead;
}

单链表开始是没有节点的，可以定义一个指向空指针的结点指针，但是此链表不同，需要在初始化函数中创建个头结点，它不用存储有效数据。因为链表是循环的，在最开始需要让头结点的next和pre指向头结点自己。
因为其他函数也不需要用二级指针（因为头结点指针是不会变的，变的是next和pre，改变的是结构体，只需要用结构体针即可，也就是一级指针）为了保持一致此函数也不用二级指针，把返回类型设置为结构体指针类型。

3.1.4、打印链表

void LTPrint(LTNode* phead)//打印链表
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

打印链表，先断言phead，它不能为空，再把头结点下个地址存到cur中，用while循环去遍历，终止条件是等于头指针停止，因为他是循环的，并更新cur。

3.1.5、在pos位置之前插入

void LTInsert(LTNode* pos, DataType x)//在pos位置之前插入数据
{
	assert(pos);
	LTNode* node = BuyListNode(x);
	LTNode* bef = pos->pre;
	bef->next = node;
	node->pre = bef;
	node->next = pos;
	pos->pre = node;
}

断言pos，不能为空，插入数据先申请一结点放到定义的node指针变量中，为了不用考虑插入顺序，先把pos前面的存到bef中，然后就可以随意链接：
bef指向新节点，新节点前驱指针指向bef，新节点指向pos，pos前驱指针指向新节点。

3.1.6、删除任意位置数据

void LTErase(LTNode* pos)//删除pos位置数据
{
	assert(pos);
	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
}

删除把pos位置之前的结点直接指向pos的下一个结点，把pos下一个结点的前驱指针指向pos之前的结点。

3.1.7、尾插

void LTPushBack(LTNode* phead, DataType x)//尾插
{
    /*assert(phead);//复杂方法
	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

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

	newnode->next = phead;
	phead->prev = newnode;*/
	assert(phead);//简便方法
	LTInsert(phead, x);
}

简便方法：尾插是在尾部插入，用简便方法调用LTInsert函数，传入头指针和x。

复杂方法是：申请结点newnode，把头指针前的上一个结点存到尾指针变量中，再双向链接newnode，最后还得把头和尾（刚申请的结点）循环起来。

3.1.8、尾删

void LTPopBack(LTNode* phead)//尾删
{
	//assert(phead);//复杂方法
	//assert(phead->next != phead);  // 空
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
	//free(tail);
	assert(phead);//简便方法
	assert(phead->next != phead);  // 空

	LTErase(phead->pre);
}

简便方法：因为是尾删，删的是尾部，直接调用LTErase函数传入头指针的上一个结点，也就是尾部，因为是双向循环不用遍历直接直到尾部。

复杂方法：先把头结点上一个结点地址存起来，再把尾部的上一个结点地址存起来，再把第二次存的直接链接头部，头部链接第二次存的结点，再把第一次的结点释放掉。

3.1.9、头插

void LTPushFront(LTNode* phead, DataType x)//头插
{
	//assert(phead);//复杂方法
	//LTNode* newnode = BuyListNode(x);
	//LTNode* back = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next = back;
	//back->prev = newnode;
	assert(phead);//简便方法
	LTInsert(phead->next, x);
}

简便方法：因为是头插直接调用LTInsert函数传 头结点下一个结点指针和x。

复杂方法：申请结点存到newnode，再把头结点下一个结点地址存到指针back里，头部和新节点和back，三节点双向链接。

3.1.10、头删

void LTPopFront(LTNode* phead)//头删
{
	//assert(phead);
	//assert(phead->next != phead); // 空
	/*LTNode* back = phead->next;
	LTNode* second = back->next;
	free(back);
	phead->next = second;
	second->prev = phead;*/
	assert(phead);
	assert(phead->next != phead);  // 空
	LTErase(phead->next);

}

简便方法：因为头删，直接调LTErase函数传入头结点下一个指针。

复杂方法：先把头结点下一个结点地址存到back指针里，再把back一个结点地址存到second指针里，先释放中间的back，最后头结点和second双向链接。

3.1.11、查找元素

LTNode* LTFind(LTNode* phead, DataType x)//查找
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;

}

查找把头结点下一个结点存到cur，然后用while循环遍历，终止条件是cur等于头结点指针，如果cur等于x，直接返回cur指针，再更新cur，最后遍历完返回NULL，表示没有该数据。

3.1.12、释放链表

void LTDestroy(LTNode* phead)//释放链表
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

释放链表从头开始释放，把头结点下一个结点存到cur中，再用用while循环，终止条件是cur不等于头指针，在里面把cur下一个指针存到next中，释放掉cur，再把next更新为cur。
最后头结点也是申请的，也得释放。

3.1.13、判断是否为空

bool LTEmpty(LTNode* phead)//判断是否为空
{
	assert(phead);

	return phead->next == phead;
}

3.1.14、求链表长度

size_t LTSize(LTNode* phead)//求链表长度
{
	assert(phead);

	size_t size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

求链表长度，先把头结点下一个结点存到cur中，再用while循环遍历终止条件是cur等于头结点，用size++记录长度，并更新cur，最后返回size，32位机器下是无符号整型size_t。

到这里链表的基本问题就解释完了，相信多多少少会解决大家心头的疑问，在数据结构的学习中应当善于思考，多画图，死磕代码，注意细节，将伪代码转换为代码，这样才能很好的掌握数据结构的有关知识，共勉，加油！！！