【数据结构与算法】单链表的增删查改（代码+图解）

创始人

2024-04-08 08:38:28

0次

顺序表和链表的特点：

时间复杂度：

分析：

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

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

打印

尾插

尾删

头插

头删：

查找单链表中的元素

在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("NULL\n");
}

调用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;                        //换头
}