数据结构——单链表详解

目录

前言

一.什么是链表

1.概念

​编辑

2.分类

二.单链表的实现(不带头单向不循环链表)

2.1初始化

2.2打印

2.3创建新节点

2.4头插、尾插

2.5头删、尾删

2.6查找

2.7在指定位置之前插入

2.8在指定位置之后插入

2.9删除pos位置

2.10删除pos之后的

2.11销毁链表

---

前言

通过前面所学的顺序表，我们发现存在着几个问题,顺序表的中间/头部的插入需要挪动数据、扩容存在着性能的消耗、或多或少有空间的浪费，由此我们引入链表这一概念.

一.什么是链表

1.概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

2.分类

结构多样，根据是否带头，单向/双向，循环/不循环分为8种

其中使用较多的是单链表（不带头单向不循环链表）和双向链表(带头双向循环链表),这节讲解单链表的实现

二.单链表的实现(不带头单向不循环链表)

2.1初始化

结构的声明和定义

typedef int SLTDataType;
//该链表由节点组成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//这里不能写成SLTNode,这时还未重命名
}SLTNode;//typedef struct SListNode SLTNode;

2.2打印

这里有pcur去接收phead,然后依次遍历，当pcur指向NULL时跳出循环，最后再打印NULL

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2.3创建新节点

与顺序表的扩容不同，这里需要新节点即开辟，不会造成浪费

如果开辟失败，则会报错

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//新节点if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

2.4头插、尾插

头插相较于尾插较容易，这里面传递的是二级指针

//链表的头插、尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPushFront(SLTNode** phead, SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//为空，跳出循环，此时ptail就是尾节点ptail->next = newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}

2.5头删、尾删

//链表的头删、尾删
void SLTPopBack(SLTNode** phead);
void SLTPopFront(SLTNode** phead);//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点,有多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next)//prev ptail ptail->next{prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾节点free(ptail);ptail = NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头节点释放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

2.6查找

通过遍历链表，查找是否与x相等,若有则返回pcur;若未找到,则返回NULL

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

2.7在指定位置之前插入

与头插类似

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//要加上链表不为空,若是空链表，那么前面将断言assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头节点if (pos == *pphead){//头插SLTPushFront(pphead,x);return;}//pos不是头节点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev->newnode->posprev->next = newnode;newnode->next = pos;
}

2.8在指定位置之后插入

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;
}

2.9删除pos位置

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头节点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;
}

2.10删除pos之后的

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//删除链表之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos->next不能为空assert(pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;free(del);del = NULL;
}

2.11销毁链表

//销毁链表
void SListDesTroy(SLTNode** pphead); //销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

---

如果上述内容对您有帮助，希望给个三连谢谢