大家好，今天给大家分享链表有什么用，一起来看看吧。

r = p;

}

r->next = ;

return L;

}

遍历单链表如打印、修改

从链表的头开始，逐步向后进行每一个元素的访问，称为遍历。

对于遍历*作，我们可以衍生出很多常用的数据*作，比如查询元素，修改元素，获取元素个数，打印整个链表数据等等。

进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可，代码如下：

//便利输出单链表

void printList(LinkedList L){

Node *p=L->next;

int i=0;

while(p){

printf("第%d个元素的值为:%dn", i,p->data);

p=p->next;

}

}

对于元素修改*作，以下是代码实现：

//链表内容的修改，在链表中修改值为x的元素变为为k。

LinkedList LinkedListReplace(LinkedList L,int x,int k) {

Node *p=L->next;

int i=0;

while(p){

if(p->data==x){

p->data=k;

}

p=p->next;

}

return L;

}

简单的遍历设计的函数只需要void无参即可，而当涉及到元素*作时，可以设计一个LinkedList类型的函数，使其返回一个*作后的新链表。

插入*作

链表的插入*作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i 1个位置的结点。

其*作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。

如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：

从原来的链表状态：

到新的链表状态：

代码实现如下：

//单链表的插入，在链表的第i个位置插入x的元素

LinkedList LinkedListInsert(LinkedList L,int i,int x) {

Node *pre; //pre为前驱结点

pre = L;

int tempi = 0;

for (tempi = 1; tempi < i; tempi ) {

pre = pre->next; //查找第i个位置的前驱结点

}

Node *p; //插入的结点为p

p = (Node *)malloc(sizeof(Node));

p->data = x;

p->next = pre->next;

pre->next = p;

return L;

}

删除*作

删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。如图所示：

代码如下：

//单链表的删除，在链表中删除值为x的元素

LinkedList LinkedListDelete(LinkedList L,int x) {

Node *p,*pre; //pre为前驱结点，p为查找的结点。

p = L->next;

while(p->data != x) { //查找值为x的元素

pre = p;

p = p->next;

}

pre->next = p->next; //删除*作，将其前驱next指向其后继。

free(p);

return L;

}

双向链表

双向链表的简介以及概念

单链表是指结点中只有一个指向其后继的指针，具有单向性，但是有时需要搜索大量数据的时候，就需要多次进行从头开始的遍历，这样的搜索就不是很高效了。

在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表，就产生了双向链表的概念了。

双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表示意图

一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。

双向链表的结点设计

对于每一个结点而言，有：

其中，DATA表示数据，其可以是简单的类型也可以是复杂的结构体；

pre代表的是前驱指针，它总是指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；

next代表的是后继指针，它总是指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空

其代码设计如下：

typedef struct line{

int data; //data

struct line *pre; //pre node

struct line *next; //next node

}line,*a;

//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)

双链表的创建

创建双向链表需要先创建头结点，然后逐步的进行添加双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的。

对于逐步添加数据，先开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。

其代码可以设计为：

//创建双链表

line* initLine(line * head){

int number,pos=1,input_data;

//三个变量分别代表结点数量，当前位置，输入的数据

printf("请输入创建结点的大小n");

scanf("%d",&number);

if(number<1){return ;} //输入非法直接结束

//////头结点创建///////

head=(line*)malloc(sizeof(line));

head->pre=;

head->next=;

printf("输入第%d个数据n",pos );

scanf("%d",&input_data);

head->data=input_data;

line * list=head;

while (pos<=number) {

line * body=(line*)malloc(sizeof(line));

body->pre=;

body->next=;

printf("输入第%d个数据n",pos );

scanf("%d",&input_data);

body->data=input_data;

list->next=body;

body->pre=list;

list=list->next;

}

return head;

}

双向链表创建的过程可以分为：创建头结点->创建一个新的结点->将头结点和新结点相互链接->再度创建新结点，这样会有助于理解。

双向链表的插入*作

如图所示：

对于每一次的双向链表的插入*作，首先需要创建一个独立的结点，并通过malloc*作开辟相应的空间；

其次我们选中这个新创建的独立节点，将其的pre指针指向所需插入位置的前一个结点；

同时，其所需插入的前一个结点的next指针修改指向为该新的结点，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身，这样的一个*作我们称之为双向链表的插入*作。

其代码可以表示为：

//插入数据

line * insertLine(line * head,int data,int add){

//三个参数分别为：进行此*作的双链表，插入的数据，插入的位置

//新建数据域为data的结点

line * temp=(line*)malloc(sizeof(line));

temp->data=data;

temp->pre=;

temp->next=;

//插入到链表头，要特殊考虑

if (add==1) {

temp->next=head;

head->pre=temp;

head=temp;

}else{

line * body=head;

//找到要插入位置的前一个结点

for (int i=1; i<add-1; i ) {

body=body->next;

}

//判断条件为真，说明插入位置为链表尾

if (body->next==) {

body->next=temp;

temp->pre=body;

}else{

body->next->pre=temp;

temp->next=body->next;

body->next=temp;

temp->pre=body;

}

}

return head;

}

双向链表的删除*作

如图：

删除*作的过程是：选择需要删除的结点->选中这个结点的前一个结点->将前一个结点的next指针指向自己的下一个结点->选中该节点的下一个结点->将下一个结点的pre指针修改指向为自己的上一个结点。

在进行遍历的时候直接将这一个结点给跳过了，之后，我们释放删除结点，归还空间给内存，这样的*作我们称之为双链表的删除*作。

其代码可以表示为：

//删除元素

line * deleteLine(line * head,int data){

//输入的参数分别为进行此*作的双链表，需要删除的数据

line * list=head;

//遍历链表

while (list) {

//判断是否与此元素相等

//删除该点方法为将该结点前一结点的next指向该节点后一结点

//同时将该结点的后一结点的pre指向该节点的前一结点

if (list->data==data) {

list->pre->next=list->next;

list->next->pre=list->pre;

free(list);

printf("--删除成功--n");

return head;

}

list=list->next;

}

printf("Error:没有找到该元素，没有产生删除n");

return head;

}

双向链表的遍历

双向链表的遍历利用next指针逐步向后进行索引即可。

注意，在判断这里，我们既可以用while(list)的*作直接判断是否链表为空，也可以使用while(list->next)的*作判断该链表是否为空，其下一节点为空和本结点是否为空的判断条件是一样的效果。

其简单的代码可以表示为：

//遍历双链表,同时打印元素数据

void printLine(line *head){

line *list = head;

int pos=1;

while(list){

printf("第%d个数据是:%dn",pos ,list->data);

list=list->next;

}

}

循环链表循环链表概念

对于单链表以及双向链表，就像一个小巷，无论怎么走终都能从一端走到另一端，顾名思义，循环链表则像一个有传送门的小巷，当你以为你走到结尾的时候，其实这就是开头。

循环链表和非循环链表其实创建的过程唯一不同的是，非循环链表的尾结点指向空，而循环链表的尾指针指向的是链表的开头。

通过将单链表的尾结点指向头结点的链表称之为循环单链表（Circular linkedlist）

一个完整的循环单链表如图：

循环链表结点设计（以单循环链表为例）

对于循环单链表的结点，可以完全参照于单链表的结点设计，如图：

单向循环链表结点

data表示数据；

next表示指针，它总是指向自身的下一个结点，对于只有一个结点的存在，这个next指针则永远指向自身，对于一个链表的尾部结点，next永远指向开头。

其代码如下：

typedef struct list{

int data;

struct list *next;

}list;

//data为存储的数据，next指针为指向下一个结点

循环单链表初始化

先创建一个头结点并且给其开辟内存空间，在开辟内存空间成功之后，将头结点的next指向head自身，创建一个init函数来完成；

为了重复创建和插入，我们可以在init函数重新创建的结点next指向空，而在主函数调用创建之后，将head头结点的next指针指向自身。

这样的*作方式可以方便过后的创建单链表，直接利用多次调用的插入函数即可完成整体创建。

其代码如下：

//初始结点

list *initlist{

list *head=(list*)malloc(sizeof(list));

if(head==){

printf("创建失败，退出程序");

exit(0);

}else{

head->next=;

return head;

}

}

在主函数重调用可以是这样：

//////////初始化头结点//////////////

list *head=initlist;

head->next=head;

循环链表的创建*作

如图所示：

单向循环链表的创建

通过逐步的插入*作，创建一个新的节点，将原有链表尾结点的next指针修改指向到新的结点，新的结点的next指针再重新指向头部结点，然后逐步进行这样的插入*作，终完成整个单项循环链表的创建。

其代码如下：

//创建——插入数据

int insert_list(list *head){

int data; //插入的数据类型

printf("请输入要插入的元素：");

scanf("%d",&data);

list *node=initlist;

node->data=data;

//初始化一个新的结点，准备进行链接

if(head!=){

list *p=head;

//找到后一个数据

while(p->next!=head){

p=p->next;

}

p->next=node;

node->next=head;

return 1;

}else{

printf("头结点已无元素n");

return 0;

}

}

循环单链表的插入*作

如图，对于插入数据的*作，可以创建一个独立的结点，通过将需要插入的结点的上一个结点的next指针指向该节点，再由需要插入的结点的next指针指向下一个结点的方式完成插入*作。

其代码如下：

//插入元素

list *insert_list(list *head,int pos,int data){

//三个参数分别是链表，位置，参数

list *node=initlist; //新建结点

list *p=head; //p表示新的链表

list *t;

t=p;

node->data=data;

if(head!=){

for(int i=1;i<pos;i ){

t=t->next; //走到需要插入的位置处

}

node->next=t->next;

t->next=node;

return p;

}

return p;

}

循环单链表的删除*作

如下图所示，循环单链表的删除*作是先找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点即可。

需要注意的是尾结点，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空。

其代码如下：

//删除元素

int delete_list(list *head) {

if(head == ) {

printf("链表为空！n");

return 0;

}

//建立临时结点存储头结点信息（目的为了找到退出点）

//如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出

//循环链表当找到后一个元素的时候会自动指向头元素，这是我们不想让他发生的

list *temp = head;

list *ptr = head->next;

int del;

printf("请输入你要删除的元素：");

scanf("%d",&del);

while(ptr != head) {

if(ptr->data == del) {

if(ptr->next == head) {

temp->next = head;

free(ptr);

return 1;

}

temp->next = ptr->next; //核心删除*作代码

free(ptr);

//printf("元素删除成功！n");

return 1;

}

temp = temp->next;

ptr = ptr->next;

}

printf("没有找到要删除的元素n");

return 0;

}

循环单链表的遍历

与普通的单链表和双向链表的遍历不同，循环链表需要进行结点的特殊判断。

先找到尾节点的位置，由于尾节点的next指针是指向头结点的，所以不能使用链表本身是否为空的方法进行简单的循环判断，我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。

此外还有一种计数的方法，即建立一个计数器count=0，每一次next指针指向下一个结点时计数器 1，当count数字与链表的节点数相同的时候即完成循环；

但是这样做会有一个问题，就是获取到链表的节点数同时，也需要完成一次遍历才可以达成目标。

其代码如下：

//遍历元素

int display(list *head) {

if(head != ) {

list *p = head;

//遍历头节点到，后一个数据

while(p->next != head ) {

printf("%d ",p->next->data);

p = p->next;

}

printf("n"); //换行

//把后一个节点赋新的节点过去

return 1;

} else {

printf("头结点为空!n");

return 0;

}

}

进阶概念——双向循环链表

循环单链表也有一个孪生兄弟——双向循环链表，其设计思路与单链表和双向链表的设计思路一样，就是在原有的双向链表的基础上，将尾部结点和头部结点进行互相连接。交给大家了。

关于链表的总结

在顺序表中做插入删除*作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。并且需要预先分配足够大的存储空间，而链表恰恰是其中运用的精华。

基于存储，运算，环境这几方面考虑，可以让我们更好的在项目中使用链表。

今天链表基础就讲到这里，下一期，我们再见！

点分享

以上就是链表有什么用的内容分享，希望对大家有用。