数据结构之单链表网站首页 技术交流

数据结构之单链表

万众☆倾倒 2023-06-02 04:00:02

简介数据结构之单链表

1.什么是链表。

对于顺序表我们发现，在此基础上仍存在了些许不足：

1.中间或头部的插入时间复杂度为O(n)，有点浪费时间。

2.增容需要申请空间，拷贝数据，释放空间，会有不小的消耗。

3.增容一般是呈2倍增容的，势必会造成空间浪费。

如何解决以上问题，我们又了解到了一种新的数据结构-“链表”

1.什么是链表。

链表顾名思义，由一条链子连接表中各成员。实则链表是由每一块独立的空间组成，每一个空间里存放着数据和一个指针，每一个指针指向下一块空间的地址，依次指向，我们可以想象成为用链条串联起类，故叫链表，链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链次序实现的。

就像火车一样

我们一般将这一块空间称为一个节点，链表的末尾节点的指针是空指针。

2.链表的优点

相较于顺序表：

1.因为链表是由一块块空间构成，所以链表不存在容量不够要扩容的问题

2.根据需求申请释放空间

3.较好地解决了在头部或中间插入删除挪动数据的问题

3.单链表的实现

这里还是以存放整形数据为例：

1.单链表的结构体

如何来实现这样的结构呢？

typedef int SLdatatype;
typedef struct seqlist
{
	SLdatatype data;
	struct seqlist* next;
}SLnode;

可以看到这里的结构体里存放了本结构体的指针，每一个结构体里都有一个自身的指针，而这个自身的指针就代表下一个结构体的首地址，依次下去，直至到末尾next尾空。

用单链表的话来说，就是每一个节点存放着指向下一个节点地址的指针，故此我们可以创建所需的节点个数存放数据，用指针连接起来。

2.节点的创建

SLnode* SLcreatnode(SLdatatype x)
{
	SLnode* newnode = (SLnode*)malloc(sizeof(SLnode));
	if (newnode == NULL)
	{
		perror("开辟错误
");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

每创建一个节点，就是在堆区申请一块空间用来存放数据，利用malloc开辟该结构体大小的空间，之后返回该节点，也就是这片空间。

3.参数的调用

这里强调下参数，因为我们需要改变链表，定义链表变量的时候是指针，函数的参数应设计为二级指针。

对于一个函数我们在其中定义的变量生命周期只在该作用域中，出了作用域就会被销毁，而有的函数需要去改变实参，只是简单的改变形参，是不会影响实参的，但若为实参的地址，我们可通过解引用形参来改变实参，比如：

int swap(int* x, int* y)
{

	int tmp = *x;
	*x = *y;
	*y = tmp;
}
int main()
{
	int x = 10;
	int y = 20;
	swap(&x, &y);
	printf("%d %d", x, y);
	return 0;
}

因此，这里要想通过形参改变实参，参数设计为二级指针：这里以头插为例

4.头插

void SLpushfront(SLnode** p, SLdatatype x)//传参用二级指针
{
	SLnode* newnode = SLcreatnode(x);
	newnode->next = *p;
	*p = newnode;
}

可以看到头插是先malloc一个节点赋值给newnode,之后在将该newnode 存放到目前的头节点的next中，然后赋值给头节点，即实现头部插入。

5.尾插

void SLpushback(SLnode** p, SLdatatype x)//尾插
{
	SLnode* newnode = SLcreatnode(x);
	//链表为空的话
	if (*p == NULL)
	{
		*p = newnode;
		(*p)->data = x;
	}
	else
	{
//找尾巴(前提：链表不为空)
	SLnode* tail = *p;
	while (tail ->next!= NULL)
	{
		tail = tail -> next;
	}
	tail->next = newnode;
	(*p)->data = x;
	}
}

尾插需要我们找到最后一个节点，之后先改变末尾的next，（因为保证是连接的）然后再插入。

7.头删

void SLpopfront(SLnode** p)//头删
{
	assert(*p);
	if ((*p) ->next== NULL)
	{
		free(p);
		*p = NULL;
	}
	else
	{
    SLnode* top = *p;
	*p = (*p) -> next;//指向下一个
	free(top);
	top = NULL;
	}
	
}

头删需要分情况

8.尾删

void SLpopback1(SLnode** p)//尾删
{
	SLnode* pre = NULL;
	SLnode* tail = *p;
	while (tail->next != NULL)
	{
	pre = tail;//找到尾节点前一个
	tail = tail->next;
	}
	free(tail);//释放最后的空间
	pre->next = NULL;//同时前一个的next为空
}

或者

void SLpopback2(SLnode** p)
{
	SLnode* tail = *p;
	while(tail->next->next)//找倒数第二个节点
	{
		tail = tail->next;
	}
	free(tail->next);//释放
	tail->next = NULL;//倒数第二个next置空
}

主要找到最后一个节点或者最后一个的前一个节点（这里的两种方法），在释放掉最后一个同时，前一个节点next为NULL。可以看到第二种直接释放掉前一个的next空间，即指向最后一个结点的空间，在置空。

8.在pos节点前插入x

void SLinsert(SLnode** p, SLnode* pos, SLdatatype x)//插在pos位置前
{
	SLnode* newnode = SLcreatnode(x);
	if (pos == *p)
	{
		SLpushfront(p, x);
	}
	SLnode* prev=*p;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
	
}

在这里需要注意在遍历找到pos位置前的一个节点时，我们都是prev->next==pos这样去寻找，但忽略了当头节点就是pos位置时的节点，故在开始我们还需要判断是否头节点等于pos节点，如何果实就直接调用头插

9.删除pos位置节点

void SLerase(SLnode** p, SLnode* pos)//删除pos位置的节点
{
	SLnode* prev = *p;
	if (*p == pos)
	{
		SLpopfront(p);
		
	}
	else
	{
      while (prev->next != pos)
	   {
		prev = prev->next;
	   }
	prev->next = pos->next;
	free(pos);
	}
	

}