详细说说链表

一、链表的定义

百度百科

        链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

        链表的定义看着很复杂，实际上也不简单。简单来说，链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 逻辑上来说是连续的，由一个个结点构成，每个结点由数据域和指针域构成。

二、链表和顺序表的比较

         1.顺序存储

                线性表的顺序存储也就是我们前面学过的顺序表，是用一段物理地址连续的存储单元依次存储数据元素的顺序结构，一般用数组来实现。

        2.链式存储

                线性表的链式存储，其数据结点在内存中的位置是任意的，但在逻辑上是连续的。

逻辑顺序

    

 物理顺序

3.顺序表和链表的区别

三、链表的结构

        链表是由一个一个结点组成的，结点一般都是在堆上申请的，从堆上申请的空间，可能连续，也可能不连续。

其中指针域是存储下一个结点的位置，实现两个结点的连接。一个一个的结点就组成了下图。

注意，箭头不是真实存在的，每一个结点也不是这么排列的，这只是我们想象出来的逻辑结构。

四、链表的实现

        1.结构体的建立

typedef int DataType;//将int类型重命名 便于以后修改数据类型
 
typedef struct SLNode {
	DataType value;//存储数据
	SLNode* next;//指针 存储下一个结点的地址
}Node;

        2.各个功能模块

void printNode(Node* phead);//打印链表
void pushBack(Node** phead, DataType x); //尾插
void pushFront(Node** head, DataType x); //头插
void PopBack(Node** head); //尾删
void PopFront(Node** head); // 头删
SLNode* SLTFind(SLNode* head, DataType x);//查找
void SLTInsert(SLNode** pphead, SLNode* pos, DataType x);//在pos位置之后插入x
void SLTErase(SLNode** pphead, SLNode* pos);//删除pos位置
void SLTEraseAfter(SLNode* pos);//删除pos位置之后的值
void DestoryNode(Node** head);//销毁链表

        3.创建结点

Node* CreateNode(DataType x)
{
	Node* newNode = (Node*)malloc(sizeof(Node));//动态开辟Node类型的结点
 
	if (newNode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//将结点初始化
	newNode->next = NULL;
	newNode->value = x;//将x赋给Node的数据域
 
	return newNode;
}

4.打印链表

这里为什么传Node* phead,是因为打印链表只是对数据进行遍历，对原有的链表并没有做出修改。

void printNode(Node* phead)
{
	Node* p = phead;
 
	while (p != NULL)//当p不为空
	{
		printf("%d->", p->value);
		p = p->next;//每打印一次，指向下一个结点
	}
	printf("NULL\n");
}

运行截图

5.尾插

这里为什么要传Node** phead？

我们可以想一想我们写过的交换两个数的值的自定义函数Swap

void Swap(int* a, int* b)

{

        int temp = *a;

        *a = *b;

        *b = temp;

}

由于形参是实参的拷贝，如果我们只是传原参而不是传地址，则在Swap函数运行完后，对原有的值并未做出修改。通过传递指针，我们可以直接访问和修改参数所指向的内存地址上的值。**phead同理，我们想要对Node结点中的*next做出修改，则需要指针的指针，也就是二级指针。

void pushBack(Node** phead, DataType x)
{
	Node* newNode = CreateNode(x);//先创建一个结点
 
	if (*phead == NULL)//判断目前是否存在结点
	{
		*phead = newNode;
	}
	else
	{
		Node* p = *phead;
 
		while (p->next != NULL)//循环到p->next = NULL时 
		{
			p = p->next;
		}
		p->next = newNode;//将newNode下一个结点
	}
 
}

6.头插

void pushFront(Node** head, DataType x)
{
	Node* newNode = CreateNode(x);
 
	newNode->next = *head;//直接将newNode->next 指向头结点
	*head = newNode;//将头结点转为newNode
}

7.尾删

void PopBack(Node** head)
{
 
	assert(*head);
 
	if ((*head)->next == NULL)//如果只有一个结点的情况
	{
		free(*head);
		*head = NULL;
	}
	else
	{
		Node* p = *head;
 
		while (p->next->next != NULL)//找到尾结点的上一个结点
		{
			p = p->next;
		}
		free(p->next);
		p->next = NULL;
	}
}

9.头删

void PopFront(Node** head)
{
	assert(*head);
 
	Node* p = *head;
	*head = (*head)->next;
 
	free(p);
}

10.找到数据为X的结点

SLNode* SLTFind(SLNode* head, DataType x)
{
	SLNode* cur = head;
 
	while (cur)
	{
		if (cur->value == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
 
	return NULL;
}

11.在pos后面插入X

void SLTInsert(SLNode** pphead, SLNode* pos, DataType x)
{
	// 严格限定pos一定是链表里面的一个有效节点
	assert(pphead);
	assert(pos);
	assert(*pphead);
 
	if (*pphead == pos)
	{
		// 头插
		pushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

12.删除pos位置

void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		// 头删
		PopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
 
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

13.删除pos后面的元素

void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
 
	SLNode* tmp = pos->next;
	pos->next = pos->next->next;
 
	free(tmp);
	tmp = NULL;
}

14.销毁链表

void DestoryNode(Node** head)
{
	Node* p = *head;
	while (p != NULL)
	{
		Node* tem = p;
		p = p->next;
		free(tem);
	}
	*head = NULL;
}

五、总结

        链表是对我们综合实力的考量，集合了指针，结构体等综合知识，需要我们基础技能过关，四个字，熟能生巧。