【数据结构】认识链表和模拟实现单链表（1）

1.链表

1.1 链表的概念

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

链表的特点：①空间上，按需给空间  ②不要求物理空间连续，头部和中间的插入删除，不需要挪动数据

1.2 链表的逻辑结构图和物理结构图

1.2.1 链表的逻辑结构图

通过以上的逻辑结构图，我们可以看出链表是由结点组成，每个结点都包括两部分：数据域和指针域，通过指针域指向下一个结点来完成结点与结点之间的相连

数据域：用来存储数据

指针域：用来指向下一个结点

1.2.2 链表的物理结构图

通过以上的物理结构图，我们可以看到除了最后一个结点的指针指向null，其余的指针域都存储下一个结点的地址，所以指针域是用来存储下一个结点的地址来完成链接的

1.3链表结构的分类

1.3.1 链表通过什么进行结构的分类

链表通过以下表格中的六种情况组合起来进行结构的分类：

可以分为以下八种结构：

1.3.2 不同链表结构的逻辑图

①单向

单向：只要一个指针域存储下一个结点的地址

②双向

双向：有两个指针域，前指针域是用来存储前一个结点的地址，后指针域是用来存储后一个结点地址

③带头

带头：有一个哨兵位结点（head），数据域一般给一个无效值，当做头结点

④不带头

不带头：没有哨兵位结点

⑤循环

循环：最后一个结点没有指向空而是指向了第一个结点

⑥非循环

非循环：最后一个结点直接指向了空

2.模拟实现一个单向链表

现在我们知道了什么是链表，以及链表的分类，那么接下来我们就来模拟实现一个存放整型数据的单向不带头非循环链表

我们首先需要创建一个类来实现这样一个链表：

public class MyLinkedList {
}

接下来我们就需要将这个实现链表的过程全部放在 MyLinkedList 这个类中

2.1 MyLinkedList类的内部类

我们知道链表是用结点来存储数据的，并且还是用结点来实现结点与结点之间的链接

那我们现在就需要在 MyLinkedList类 中创建一个内部类当做结点类

private class Node {
    private int data;//数据域
    private Node next;//链接域
    private Node(int data) {
        this.data = data;
    }
}

data：用来存放数据

next：用来存储下一个结点的地址，从而达到结点与结点之间的链接

构造方法：每实例化一个结点类时，都需要调用构造方法，来把数据放入数据域

2.2 MyLinkedList类的成员属性

我们需要给第一个结点设置为头结点，这样用户才知道链表应该从哪里开始，这样单链表才不会因为没有被指向而被回收

private Node head;//记录第一个结点

注：只要第一个结点没有被回收，其他结点也不会被回收，因为前一个结点的 next 存储着后一个结点的地址，这样前一个结点的指针域就指向了后一个结点