【数据结构与算法】单链表的增删查改（代码+图解）顺序表和链表的特点：分析：尾删完整代码：

96 阅读 0 评论 64 点赞

我是靠谱客的博主称心小懒猪，最近开发中收集的这篇文章主要介绍【数据结构与算法】单链表的增删查改（代码+图解）顺序表和链表的特点：分析：尾删完整代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序表和链表的特点：

时间复杂度：

分析：

单链表结构体和数据类型：

开辟一个节点和存储数据：

打印

尾插

尾删

头插

头删：

查找单链表中的元素

在pos后插入x

在pos前插入x

删除pos后的一个元素:

删除pos位置的元素：

摧毁单链表：

完整代码：

顺序表和链表的特点：

顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素.

链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取.

单向链表增加删除节点简单。遍历时候不会死循环；

时间复杂度：

链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；

而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n);

链表存储数据一次只开辟存储一个节点的物理空间，如果后期不够还可以再申请。

分析：

单链表结构体和数据类型：

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

开辟一个节点和存储数据：

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

malloc函数开辟一个大小为sizeof(SLTNode)字节即一个结构体大小的空间，原本malloc返回值是void类型的指针，但是代码里面的（SLTNode*）将malloc的返回值强制类型转换为SLTNode类型，这样方便了后面数据的存储；

打印


void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}

调用SLTPrint()函数使，用*phead接收传进来的参数

尾插

void SLTPushBack(SLTNode** phead,SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SLTNode* ptail = *phead;
		while (ptail->next)     //找尾
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

图解：

首先用ptail记住链表头部的位置，再ptail=ptail->next寻找最后一个节点

尾删

void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	//只有一个指针
	if ((*phead)->next==NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* pre = NULL;                //记录倒数第二个指针，
		SLTNode* ptail = *phead;
		while (ptail->next)
		{
			pre = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		pre->next = NULL;                     //将被释放的那个指针置空，避免出现野指针

	}
}

assert(*phead)实现对*phead判空；这里解释一下为什么传参要用双指针，因为改变的是指针，而不是指针的值；

例如：

//单指针传参交换指针指向的值
void Swap1(int *p1,int *p2)
{
    int tmp= *p1;   //这里p1解引用之后就是p1指针指向的值
    *P1 = *p2;
    *p2= tmp;
}

//双指针传参交换指针
void Swap2(int ** pp1,int **pp2)
{
    int *tmp=*pp1;
    *pp1 = *pp2;
    *pp2 = tmp;
}

int main()
{
    int a=0,b=1;
    Swap1(&a,&b);
    
    int *ptr1  = &a,ptr2 = &b;
    Swap2(&ptr1,&ptr2); 
}

Swap2(&ptr1,&ptr2)通过交换a、b的地址来交换值，而Swap1通过改变指针指向的值来交换值；

总结：1、改变int,传递int *给形参，*形参进行交换改变

2、改变int*,传递int**给形参，*形参进行交换改变

头插

void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *phead;                      //
	*phead = newnode;                           //换头
}

先将newnode->next指向phead(头节点)，再phead=newnode;

头删：

void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newnode = NULL;
	newnode = (*phead)->next;          //存储第二个指针
	free(*phead);                            //释放第一个指针空间
	*phead = newnode;                        //换头
}