iOS - 链表

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

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

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

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

单向链表

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

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

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

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

单向列表程序的实现

1. 链表节点的数据结构定义

class ListNode {
    //数据域
    var val: Int
    //指针域
    var next:ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

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

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

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

1. 定义链表的数据结构
2. 创建一个空表
3. 利用malloc函数向系统申请分配一个节点
4. 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头。若是非空表，将新节点接到表尾
5. 判断一下是否有后续节点要接入链表，若有，转到3.,否则结束

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

1. 找到表头
2. 若是非空表，输出节点的值成员，若是空表则退出
3. 跟踪链表的增长，即找到下一个节点的地址
4. 转到2

4. 完整代码

创建一个存放正整数单链表，输入0或小于0的数，结束创建链表，并打印链表中的

//
//  ListNode.c
//  AlgorithmDemo
//
//  Created by Ternence on 2021/5/7.
//

#include "ListNode.h"
#include <stdlib.h> // 含有malloc()的头文件
#include <stdio.h>

// 链表数据结构
struct Node {
    int num;
    struct Node *next;
};

main() {
    void print();
    struct Node *head;
    // 建一个空表
    head = NULL;
    // 创建单链表
    //head = create(head);
    print(head);
}

struct Node *create(struct Node *head) {
    struct Node *p1, *p2;

    //利用malloc函数向系统申请分配一个节点
    p1 = p2 = (struct Node *)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.否则结束
        if (p1 -> num <= 0) {
            p1 = NULL;
            p2 -> next = NULL;
            break;
        }
    }

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

// 打印出以head为头的各节点的值
void print(struct Node *head) {
    struct Node *temp;
    //取得链表的头指针
    temp = head;

    while (temp != NULL) {
        //输出链表各节点的值
        printf("%d \n ", temp->num);
        temp = temp -> next;
    }
}

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

双向链表

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

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

struct Node {
    int data;
    struct Node *llink, *rlink; //llink是左链域指针 rlink是右链域指针
};

当然，也可以把一个双向链表构成一个双向循环链表。
双向列表与单向链表一样，也有三种基本运算：查找、插入和删除

循环链表

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

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

1. 在建立一个循环链表时，必须使其最后一个节点的指针指向头节点，而不是像单链表那样置为NULL，此种情况还使用于在最后一个节点后插入一个新的节点
2. 在判断是否到表尾时，是判断该节点链域的值是否是表头节点，当链域值等于表头指针时，说明已到表尾，而非像单链表那样判断链域值是否为NULL

块状链表

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

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

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

• 插入操作处理顺序：中间节点的逻辑，后节点的逻辑，前节点的逻辑
• 删除操作的处理顺序: 前节点的逻辑，后节点的逻辑，中间节点逻辑

参考:ios -链表的简单认识