【数据结构】单链表 | 详细讲解

线性表顺序存储结构的优缺点

顺序表优点

• 无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间；
• 因为以数组形式存储，可以快速地存取表中任一位置的元素。

顺序表缺点

• 插入和删除操作需要移动大量元素，时间复杂度为O(N)；
• 当线性表长度变化较大时，难以确定存储空间的容量；
• 造成存储空间的“碎片”。

顺序存储结构不足的解决办法

其实顺序表最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费极大时间，因为相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3,...,n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

那这样的话，我们反正都要让相邻的元素都留有足够余地，那么干脆所有的元素都不考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道他下一个元素的位置在哪里，这样我们就可以在第一个元素时，就知道第二个元素的位置（内存地址），而找到它；在第二个元素时，就知道第三个元素的位置（内存地址），而找到它。这样所有的元素我们就都可以通过遍历而找到了。

其实这个思路也就是链表存储思路，而本篇文章着重讲述链表中的单链表。

线性表链式存储结构定义

在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

数据域：存储数据元素信息的域称为数据域；

指针域：存储直接后继位置的域称为指针域。

在指针域中存储的信息称为指针或链。数据域与指针域信息组成数据元素的存储映像，称为结点。

单链表：n个结点链结成的链表，此链表中的每个结点中只包含一个指针域。

单链表的代码实现以及分析 

单链表的结构代码

单链表中的结点，是由存放数据元素的数据域和存放后继结点地址的指针域组成的。所以，假设这个数据为val，存放后继结点地址的指针为next。

typedef int SLNDataType;
typedef struct SListNode
{
	struct SListNode* next;
	SLNDataType val;
}SLNode;

单链表中的每一个节点都是一个结构体成员，也就是多个结构体构成了一条链表。这与顺序表不同，顺序表由于数组存储 ，所以就是一个结构体的数组中存储了多个节点。

单链表的遍历打印

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

单链表建立新的头结点 

在创建新的头结点时，需要用到malloc函数，关于malloc的使用方法，这里不做过多阐述，大家有什么不懂的，可以点击链接（单击即可查看）详细学习malloc的使用方法哦。

C库函数中 void *malloc(size_t size) 分配所需的内存空间，并返回一个指向它的指针。

malloc是分配内存空间的函数。

 

SLNode* SLTCreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}

单链表的尾插

那如果这是一个空表的话，那么就直接让这个单链表为指针，指向新创建的节点。

 

void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	SLNode* Newnode = SLTCreateNode(x);
	if (*pphead == NULL)
	{
		*pphead = Newnode;
	}
	else
	{
		SLNode* tail = pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = Newnode;
	}
}

单链表的头插

 

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	SLNode* Newnode = SLTCreateNode(x);
	Newnode->next = *pphead;
	*pphead = Newnode;
}

单链表的尾删

 

void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

单链表的头删

 

 

void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* cur = (*pphead)->next;
	//注意在单链表头删的时候，如果只有一个节点，那也是可以的，就让那个临时的为空
	free(*pphead);
	*pphead = cur;
}

单链表的查找x数据

 

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

单链表在pos位置插入x的数

 

SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(*pphead);
	assert(pphead);
	assert(pos);
	
	if (*pphead==pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* Newnode = SLTCreateNode(x);
		prev->next = Newnode;
		Newnode->next = pos;
	}
}

单链表删除pos位置上的值

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

单链表的销毁

void SLTDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}