课时133：链表实现简介

课时133：链表实现简介

摘要：链表的本质是一种动态的对象数组，它可以存储任意数量的对象。简而言之，我们可以将其视为一种对象数组。

1. 链表简介

2. 链表的实现原理

3. 代码实现中的问题与解决方案

01. 链表简介

在实际开发中，对象数组是一项非常实用的技术，可用其描述“多”的概念。例如，如果一个人有多本书，那么需要在“人”的类中提供一个对象数组来保存书的信息。但是传统的对象数组依赖于数组的概念，而数组最大的缺点是长度固定。

因此，在实际开发中传统的数组的应用非常有限。 这里的“有限制”并非指完全不用，而是指它通常只用于数组的接收和循环处理等简单场景。

如果要想进行灵活的数据保存，就必须自己来实现结构。例如，如果程序需要对对象数组进行操作，通常需要使用索引（角标）进行控制。 如果数组需要不断增长，索引的控制还算简单。

但是，如果数组中的数据已经填满，突然需要删除一个或多个数据，那么索引的控制就会变得非常复杂。而传统的对象数组无法承担过于复杂的操作，只能进行简单的操作。在实际应用中，常常会出现需要随时修改数据结构的需求。

注：图表

传统的对象数组开发操作依赖于角标（索引）的控制。如果要实现内容的动态维护，难度会非常高，复杂度也会迅速攀升。所以，对于一成不动的数据可以使用对象数组来实现。但是对于可能随时变化的数据，就必须实现一个可以动态扩充的对象数组。链表的作用就在于此。

链表的本质是利用引用的逻辑关系来实现类似于数组的数据操作。 它以一种保存“多“方数据的形式，实现类似于数组的功能，但它本身并不是数组。

比如说现在假设在超市买了五个特别重要的东西，但是后来发现还要再买一个东西，在这样的情况下，传统的对象数组设计是有缺陷的。我们最好能够找到一个动态对象数组的形式。

这个就是我们链表的作用。所以链表的本质是利用引用的逻辑关系来实现我们数组，类似于数组的数据操作。我们以一种保存多方数据的形式，实现数组类似的功能，它不是一个数组，但是它能够实现一个跟数组类似的功能

02. 链表的实现原理

那么，链表是如何实现的呢？ 我们可以将链表与火车进行类比。 理论上，火车可以无限增加车厢。

在一个正常的火车车厢内，火车的前后都有一个“钩子”。 这个钩子的主要作用是连接车厢。 钩子本身不承担数据的保存操作，但它非常重要，因为如果没有钩子，就无法实现车厢的正常连接。 通过前后这两个钩子，就可以连接无数个车厢。

车厢里面存放的是数据信息。如果一个车厢只坐一个人，如果要坐更多的人，则需要在前后为每个人绑定一个操作项，用于数据的连接的控制。 这样，每个车厢都知道它的下一个车厢是谁。数据本身不具备连接功能。为了实现链表处理，需要一个公共的结构，该结构可以实现数据的保存以及指向下一个连接的指针。也就是说，数据是结构中的一部分。

除了数据结构本身，通常还有一个用于连接的指针。 利用这个指针，可以指向可能要保存的数据。如果是最后一节车厢，则其指针应该指向空。

为了描述这样的逻辑，可以将每一个存储单元理解为一个节点（Node）。 Node 可以保存各种数据类型的数据。 如果要实现一个通用的 Node，其保存的数据类型应该是什么呢？ 如果使用 Object，虽然可以保存所有的数据，但也意味着可能会出现数据类型推诿的问题。

除了数据之外，还需要保存逻辑关系，即指向下一个节点的指针。 因此，Node 需要保存数据以及指向下一个 Node 的指针。 为了避免向下转型，Node 最好使用泛型。

03. 代码实现中的问题与解决方案

虽然我们已经知道数据要用 Node 来封装，但还需要进一步思考。 毕竟，这里面涉及到节点引用的处理关系。 那么，由谁来负责处理这个引用关系呢？ 由使用者控制吗？ 由使用者创建无数个 Node，然后自己来处理引用关系，这显然是不合理的。所有应该有一个专门的类来进行节点的引用关系的配置。

范例1：直接操作Node，很麻烦

class Node<E>{
    private E data;
    private Node next;
    public Node(E data){
        this.data = data;
    }
    public E getData() {
        return this.data;
    }
    public void setNext(Node<E> next) {
        this.next = next;
    }
    public Node getNext() {
        return this.next;
    }
}
public class LinkDemo {
    public static void main(String[] args) {
        Node<String>n1=new Node<String>("火车头");
        Node<String>n2=new Node<String>("车厢一");
        Node<String>n3=new Node<String>("车厢二");
        Node<String>n4=new Node<String>("车厢三");
        Node<String>n5=new Node<String>("车厢四");
        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);
        n4.setNext(n5);
        print(n1);
    }
    public static void main(Node<?>node) {
        if (node != null) {//有节点
           System.out.println(node.getData());
           print(node.getNext());//递归调用
        }
    }
}

运行结果如下

应该有一个专门的类来进行节点的引用关系的配置。 客户端不应该直接操作 Node。 真实的使用者关心的只是数据的存储与获取。 就像发快递或收快递一样，只需要关注数据的存储与获取，而不需要关注中间经过的步骤和环节。

因此，应该准备出一个专门的链表操作类（Link）。 Link 类负责处理所有的 Node 细节。 通过 Link 类，可以直接进行数据的操作，而所有复杂的引用逻辑都由 Link 类进行处理。

如果 Node 类负责数据的保存，那么外部应该看不到这个 Node 类。 因此，Node 类应该作为 Link 类的内部类出现。为了使链表操作更加清晰，应该先定义一个操作的标准（接口），然后再实现这个标准。 这样，客户端就可以通过接口来了解链表的操作方式。

例如，可以定义一个名为 ILink 的接口，并在该接口上定义泛型。 然后，创建一个名为 LinkImpl 的类来实现 ILink 接口。 这样，客户端就可以通过 ILink 接口来了解链表的操作方式。

总而言之，链表玩的就是一个引用数据的处理过程，这是其基本的设计思想。