ios -链表的简单认识

作为一个资深的新手程序员😂,链表这些既基础又深奥的东西是日常工作中并不常见,但是却非常重要,所以就总结一下链表的简单认识!

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。

我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

链表(Linkedlist）是一种常见的基础数据结构，是一种线性表，是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的，但是并不会按线性的顺序存储数据，链表通常由一连串节点组成，每个节点包含任意的实例数据（datafields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记。另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点。

优势：可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接），同时，链表允许插入和移除表上任意位置上的节点。

劣势：链表由于增加了结点的指针域，空间开销比较大；另外，链表失去了数组随机读取的优点，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。

单向链表

链表中最简单的一种是单向链表，

一个单向链表的节点被分成两个部分。它包含两个域，一个信息域和一个指针域。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址，而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。

单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。

单向链表

上图还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。

单向链表程序的实现

（1），链表节点的数据结构定义

struct node

{

int num;

struct node *p;

} ;

在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。

在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。

（2），链表的创建、输出步骤

单链表的创建过程有以下几步：

1 ) 定义链表的数据结构;

2 ) 创建一个空表;

3 ) 利用malloc ( )函数向系统申请分配一个节点;

4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新

节点接到表尾;

5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

单链表的输出过程有以下几步

1) 找到表头;

2) 若是非空表，输出节点的值成员，是空表则退出;

3 ) 跟踪链表的增长，即找到下一个节点的地址;

4) 转到2 ).

（3），程序代码例子：

创建一个存放正整数单链表，输入0或小于0的数，结束创建链表，并打印出链表中的值，程序如下：

#include  <stdlib.h>/*含ma l l o c ( ) 的头文件*/

#include <stdio.h>

struct node//①定义链表数据结构

{

int num;

struct node *next;

};

main( )

{

struct node *creat();

void print();

struct node *head;

head=NULL;//②建一个空表

head=creat(head);/*创建单链表*/

print(head);/*打印单链表*/

}

/******************************************/

struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/

{

struct node*p1,*p2;

//③利用malloc ( )函数向系统申请分配一个节点

p1=p2=(structnode*)malloc(sizeof(struct node));/*新节点*/

printf("p1= %d\n",p1);

scanf("%d",&p1->num);/*输入节点的值*/

p1->next=NULL;/*将新节点的指针置为空*/

while(p1->num>0)/*输入节点的数值大于0*/

{

//④将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新

//节点接到表尾;

if(head==NULL)

head=p1;/*空表，接入表头*/

else

p2->next=p1;/*非空表，接到表尾*/

p2=p1;

p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/

printf("p2= %d\n",p2);

scanf("%d",&p1->num);/*输入节点的值*/

//⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

}

printf("p2->next=%d\n",p2->next);

return head;/*返回链表的头指针*/

}

/*******************************************/

void print(struct node*head)/*出以head为头的链表各节点的值*/

{

struct node *temp;

temp=head;/*取得链表的头指针*/

while(temp!=NULL)/*只要是非空表*/

{

printf("%6d",temp->num);/*输出链表节点的值*/

temp=temp->next;/*跟踪链表增长*/

}

}

编译后执行：

p1= 140660744  //链表头

1

p2= 140660760

45

p2= 140660776

6

p2= 140660792

77

p2= 140660808

88

p2= 140660824

0                               //输入0结束增加链表

p2->next=0       //链表结尾

1       45    6    77    88          //输出链表的值。

在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。

程序执行流程：

程序执行流程

双向链表

双向链表其实是单链表的改进，当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域（当此“连接”为最后一个“连接”时，指向空值或者空列表）；一个存储直接前驱结点地址，一般称之为左链域（当此“连接”为第一个“连接”时，指向空值或者空列表）。

typedef struct node

{

int data; /*数据域*/

struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/

}JD;

当然，也可以把一个双向链表构建成一个双向循环链表。

双向链表与单向链表一样，也有三种基本运算：查找、插入和删除,  后续我会写出来分享给大家!

循环链表

循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

块状链表

块状链表本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个块。

块状链表另一个特点是相对于普通链表来说节省内存，因为不用保存指向每一个数据节点的指针。

链表的提出主要在于：顺序存储中的插入和删除的时间复杂度是线性时间的，而链表的操作则可以是常数时间的复杂度。

链表的插入与删除操作顺序：

插入操作处理顺序：中间节点的逻辑，后节点逻辑，前节点逻辑。

删除操作的处理顺序：前节点逻辑，后节点逻辑，中间节点逻辑。