数据结构学习之链表学习：单链表

在之前顺序表的学习过程中，我们知道顺序表中头插和中插的复杂度是O（N）。那我们可不可以将其降低为O（1）呢？可不可以不增容想用就用想扔就扔而不会浪费一点空间呢？那就是我们今天的内容：链表

继我们学习了顺序表之后，接下来我们就来学习顺序表的下一个内容：链表。

链表

单链表

单链表的组成

创建单链表的新节点

单链表的尾插

单链表的头插

单链表的尾删

单链表的头删

单链表的查找

单链表插入数据

指定位置之前

指定位置之后

单链表删除数据

指定结点

指定节点之后

单链表的结点数据修改

单链表的销毁

链表

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

那么链表是如何实现的呢？

以火车为例，火车的车头和车厢并不是粘连在一起的，而是通过连接起来的，可以增减车厢的个数。每个车厢是独立存在的，增减某一元素对原有数据不影响

再单链表中“车厢”就是结点，而单链表就是由结点构成的。

而由于上图可知，结点是由数据元素及保存下一个结点地址的指针组成的。

接下来我们来学习单链表的实现。

单链表

我们需要三个文件来准备

SList.h——声明结构体的组成、声明函数方法

SList.c——实现函数

test.c——单链表测试

单链表的组成

typedef int SListDataType;
//定义链表结构——节点
typedef struct SListNode
{SListDataType data;//保存的数据struct SListNode* next;//指向下一个节点的指针
}SLN;

单链表的打印函数

SList.h

//链表的打印
void SLN_print(SLN* next);

SList.c

//链表的打印
void SLN_print(SLN* phead)
{SLN* p = phead;while(p!= NULL)//可以简写为while(p){printf("%d ->", p->data);p = p->next;}printf("NULL\n");
}

创建单链表的新节点

//根据x创建节点
SLN* SLN_buy_node(SListDataType x)
{//根据x创建结点SLN* new_node = (SLN*)malloc(sizeof(SLN));if (new_node == NULL){perror("malloc error");return  1;}new_node->data = x;new_node->next = NULL;return new_node;
}

单链表的尾插

前面我们知道链表是依赖于指针连接起来的，所以我们创建一个空链表是这样的

//创建一个空链表
SLN* slist =NULL;

因此，我们进行尾插的时候分为两种情况：链表为空和链表不为空

链表为空时，直接将新结点赋值给首结点；不为空时，从前往后走，当指针不为空时向后走，当指针为空的时候跳出循环，插入结点，尾部节点指针为NULL。

代码为：

//链表的尾插
void SLN_back_push(SLN** pphead, SListDataType x)
{SLN* new_node = SLN_buy_node(x);//链表为空if (*pphead == NULL){*pphead = new_node;}else{//找尾结点SLN* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//找到尾结点ptail->next = new_node;}
}

单链表的头插

头插思路：

//链表的头插
void SLN_head_push(SLN** pphead, SListDataType x)
{assert(pphead!=NULL);SLN* new_node = SLN_buy_node(x);new_node->next = *pphead;*pphead = new_node;
}

单链表的尾删

//链表的尾删
void SLN_back_pop(SLN** pphead)
{assert(pphead!= NULL&&*pphead!= NULL);//找prev和ptailSLN*prev = NULL;SLN*ptail = *pphead;//找尾结点while (ptail->next != NULL){prev = ptail;ptail=ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}

但是这段代码当链表只有一个结点的时候就会出错，

单链表的头删

void SLN_head_pop(SLN** pphead)
{assert(pphead != NULL && *pphead != NULL);SLN*next=(*pphead)->next;free(*pphead);*pphead=next;
}

单链表的查找

//链表的查找
SLN* SLN_find(SLN* pphead, SListDataType x)
{SLN*p=pphead;while (p != NULL){if (p->data == x){printf("find %d\n", x);return p;}p = p->next;}return NULL;
}

单链表插入数据

指定位置之前

思路图：

prev的指针指向newcode的数值，newcode的next指针指向pos

代码：

//指定位置之前插入
void SLN_Before_insert(SLN** pphead, SLN* pos, SListDataType x) 
{assert(pphead != NULL && pos != NULL);// pos 是头节点，执行头插if (pos == *pphead) {SLN_head_push(pphead, x);}else {SLN* newnode = SLN_buy_node(x);// 找pos的前一个结点SLN * prev = *pphead;while (prev->next != pos){prev = prev->next;}	//prev--> newnode--> pos prev->next = newnode;prev->next = newnode;newnode->next = pos;}
}

指定位置之后

思路图：

只需要将pos的next指针指向newcode，将nextcode的next指针指向下一个数据，即以下这种情况：

newcode->next=pos->next;
pos->next=newcode;

代码：

//指定位置之后插入
void SLN_After_insert( SLN* pos, SListDataType x)
{assert(pos);SLN* newnode = SLN_buy_node(x);newnode->next = pos->next;pos->next = newnode;	
}