链表的基本概念

在程序的设计过程之中，除了基础语法功能之外，还应该改掌握数据结果，这是一个作为程序员的基本功。在国内很可悲的一点在于：所有的数据结构的课程内容中几乎都是讲解的纯理论。

在Java内部实际上有大量的数据结构提供的支持类型，实际上有些编程开发，只要理解了基本概念，那么程序本身的支持的实现原理学习是非常快捷的。

在学习数据结构开发之前，首先要清楚为什么需要有这样的数据结构的形式出现，难道原始程序的语法不能解决这些问题吗？

如果说现在要想实现多个数据或者是对象信息的存储，首先可以想到的一个实现方案：数组，但是数组本身也存在非常严重的设计问题：长度限制，这一点是它的致命伤，因为如果保存的数据很多，那么数组就需要开辟的很大，但是如果说一旦突然发现数据保存少了，则数组开辟的空间是无法直接回收的，所以就会造成大量的垃圾空间出现。并且数组的数据本身是无法区分出先后顺序的，任何的数据都只是单独的数据，而无法有任何的其他功能。

所以这个时候就必须考虑使用一种专门的形式来进行这种数据的存储，于是在这样的情况下就可以采用引用数据类型的特点来完成。

image.png

分析上图的特点可以发现，在当前的程序里面除了本身的数据之外，就需要进行一个载体的设计了，而这种载体的设计最佳的处理形式就是基于类的方式完成定义，如果想要写成类，按照习惯性的做法，每一个数据的载体（包含有数据）都可以将其称为一个节点（Node），Node要完成两件工作：数据的保存、节点的关联。

链表结构.png

链表基本结构

既然要进行链表的开发，那么首先就需要知道链表的实现原理，在整个的实现原理过程之中，实际上最为重要的部分就是Node类的定义和使用了，因为Node类是作为链表中数据节点的存储使用。

于是这个时候如果是直接进行Node类的定义，那么首先需要确定的因素就是链表的节点需要保存那些数据呢？

按照正常的设计来讲，链表一定要保存所有Java中的支持的数据类型，Java中存在有基本数据类型和引用数据类型，于是这个时候就有人会立刻提出，保存Object，而如果现在的设计真的存放的是Object，那么整个的程序设计就非常的糟糕了。

这个时候最大的问题就是来源于Object了，因为其存储的范围太广了，在正常情况下，要想是使用链表基本上都会遵循一个原则：链表里面所保存的数据类型一定要统一，但是这样的统一的操作，一定不是由程序的开发人员强制性规定，必须上升到语法层次。应该由编译器在编译的时候就帮助我们查询出来相应的错误信息。如果使用Object，那么这样编译器的语法结构控制就失效了，应为即便你存放了不同样的数据类型，也不会出现语法错误。所以这个时候最佳的做法是使用范型来解决。

范例：

package demo;

class Node<T>{  //定义描述节点的结构类

    private T data;     //保存所有数据
    private Node next;  //描述下一个节点

    public Node(T data){    //保存数据信息
        this.data = data;
    }

    public void setNext(Node next) {    //设置下一个节点
        this.next = next;
    }

    public Node getNext() {
        return this.next;
    }
    
    public T getData() {
        return this.data;
    }

}

 class Test {
    public static void main(String [] args ) {

        Node<String> nodeA = new Node<>("this is NodeA");
        Node<String> nodeB = new Node<>("this is NodeB");
        Node<String> nodeC = new Node<>("this is NodeC");

        //设置节点关联
        nodeA.setNext(nodeB);
        nodeB.setNext(nodeC);
        
        print(nodeA);   //节点输出
        
    }
    
    public static void print(Node node) {   //获取数据
        
        if(node == null) {  //结束条件
            return;     //结束方法调用
        }
        
        System.out.println(node.getData());
        print(node.getNext());      //继续输出下一个节点
    }
    
}

虽然这个时候已经成功的实现了所有的节点信息配置和内容输出，但是对于当前的结构实现存在如下的问题：

• 用户在进行开发的过程之中应该关注的仅仅是数据本身，而不是应该关注的是Node数据载体；
• 用户在使用的过程之中，没有必要关注Node彼此之间的关联。

这个时候最关键性的问题就是在于如何把Node类之中的这些节点的引用结构操作进行有效的隐藏，所以这个时候最佳的做法是有另外一个专门负责节点处理的程序类来完成会比较合适，但是由于要考虑不同形式的链表的存储方案，所以这个时候最佳的做法就是通过接口来定义相关的实现标准。

链表结构设置

image.png

范例：基本程序结构

package demo;

interface ILink<T>{ //链表的实现标准
}

class LinkImpl<T> implements ILink<T>{
    // 使用内部类的结构表示该类的所属范围，同时使用private标注其只能够被内部使用
    private class Node<T>{
        private T data;
        private Node next;
        public Node(T data) {
            this.data = data;
        }
    }
    // ============================= 链表实现的相关的处理操作
    private Node root;      //根节点
}

 class Test {
    public static void main(String [] args ) {
        ILink<String> link = new LinkImpl<>();   
    }
}

既然已经确定好了所有的基本结构，随后的工作就是将这个结构的代码进行完善，将与链表有关的核心的处理方法全部实现。

链表数据增加

所有在链表之中所保存的数据全部都是由LinkImpl类来负责处理的，但是如果想要进行链表数据的保存，那么就需要首先确定好链表的根节点，只要根节点存在就可以找到后续的全部子节点。

image.png

范例：实现基础的追加

package demo;

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加
    
}

class LinkImpl<T> implements ILink<T>{
    // 使用内部类的结构表示该类的所属范围，同时使用private标注其只能够被内部使用
    private class Node<T>{
        private T data;
        private Node next;
        public Node(T data) {
            this.data = data;
        }
        //当调用此方法的时候实际上已经在LinkImpl类里面判断完成了根节点是否存在
        //第一次调用：是由LinkImpl.root实例发出的调用(this = LinkImpl.root)
        //第二次调用：是由Node类发出的(this = LinkImol.root.next)
        public void addNode(Node newNode) { //进行节点的追加
            if(this.next == null) { //当前节点的后续节点为空
                this.next = newNode;    //存储节点
            }else { //已经有了后续节点
                addNode(newNode);   //继续向后进行判断与添加
            }
        }
    }
    // ============================= 链表实现的相关的处理操作
    private Node root;      //根节点
    public void add(T data) {   //接口中进行方法复写
        if(data == null) {
            return;     //结束方法调用
        }
        //1、传进行的是一个数据，数据本身是无法进行所谓的顺序定义的，所以需要将其封装
        Node<T> newNode = new Node<>(data); //创建一个新的数据节点
        //2、需要确认保存的节点位置，第一个节点应该是根节点
        if(this.root == null) {//没有根节点
            root = newNode; //保存节点引用
        }else { //如果不是根节点
            this.root.addNode(newNode); //追加节点
        }
    }
    
    
}

 class Test {
    public static void main(String [] args ) {
        ILink<String> link = new LinkImpl<>();   
        link.add("Node01");
        link.add("Node02");
        link.add("Node03");
    }
}

这个时候的数据的确是进行了数据的追加，而且也可以成功的实现了数据的追加，但是此时会存在非常严重的性能问题。

对于此时的数据追加的逻辑为：每一个新增加的节点都要递归N次（N为元素的保存个数）后才能进行准确的数据存储。

image.png

所以在实际的开发过程之中，针对这种链表的数据存储的最佳做法一定不是使用递归的形式完成，因为这种边判断边保存位置的处理形式存在非常严重的性能问题，那么最佳的做法是每一次保留有最后一个节点。

数据增加优化

package demo;

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加    
}

class LinkImpl<T> implements ILink<T>{
    // 使用内部类的结构表示该类的所属范围，同时使用private标注其只能够被内部使用
    private class Node<T>{
        private T data;
        private Node next;
        public Node(T data) {
            this.data = data;
        }
    }
    // ============================= 链表实现的相关的处理操作
    private Node root;      //根节点
    //在LinkImpl类里面追加一个新的属性，进行性能的提升
    private Node lastNode;  //保存最后一个节点
    public void add(T data) {   //接口中进行方法复写
        if(data == null) {
            return;     //结束方法调用
        }
        //1、传进行的是一个数据，数据本身是无法进行所谓的顺序定义的，所以需要将其封装
        Node<T> newNode = new Node<>(data); //创建一个新的数据节点
        //2、需要确认保存的节点位置，第一个节点应该是根节点
        if(this.root == null) {//没有根节点
            this.root = newNode;    //保存节点引用
            this.lastNode = newNode;    //保存最后一个节点
        }else { //如果不是根节
            this.lastNode.next = newNode;   //保存新节点
            this.lastNode = newNode;        //改变节点
        }
    }
}

 class Test {
    public static void main(String [] args ) {
        ILink<String> link = new LinkImpl<>();   
        link.add("Node01");
        link.add("Node02");
        link.add("Node03");
    }
}

image.png

此时的程序的实现结构不仅要比递归的方式简化，同时也可以得到最佳的性能提生，避免不必要的循环才是最好的程序设计。

获取链表元素个数

链表的实现是为了动态数组的结构完善，所以在这个时候就需要随时获取链表里面对应元素的保存个数，这个功能就和在实际使用数据之中的“length”属性类似。
1、在ILink接口之中追加有一个新的获取元素个数的方法：

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加    
    public int size();  //获取元素个数
}

2、所有的元素个数是在链表数据保存成功之后进行累加的，直接修改LinkImpl.add()方法即可。

package demo;

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加    
    public int size();  //获取元素个数
}

class LinkImpl<T> implements ILink<T>{
    // 使用内部类的结构表示该类的所属范围，同时使用private标注其只能够被内部使用
    private class Node<T>{
        private T data;
        private Node next;
        public Node(T data) {
            this.data = data;
        }
    }
    // ============================= 链表实现的相关的处理操作
    private Node root;      //根节点
    //在LinkImpl类里面追加一个新的属性，进行性能的提升
    private Node lastNode;  //保存最后一个节点
    private int count;      //统计技术
    @Override
    public void add(T data) {   //接口中进行方法复写
        if(data == null) {
            return;     //结束方法调用
        }
        //1、传进行的是一个数据，数据本身是无法进行所谓的顺序定义的，所以需要将其封装
        Node<T> newNode = new Node<>(data); //创建一个新的数据节点
        //2、需要确认保存的节点位置，第一个节点应该是根节点
        if(this.root == null) {//没有根节点
            this.root = newNode;    //保存节点引用
            this.lastNode = newNode;    //保存最后一个节点
        }else { //如果不是根节
            this.lastNode.next = newNode;   //保存新节点
            this.lastNode = newNode;        //改变节点
        }
        this.count++;
    }
    
    @Override
    public int size() {
        return this.count;      //返回元素的个数
    }
    
}

 class Test {
    public static void main(String [] args ) {
        ILink<String> link = new LinkImpl<>();   
        System.out.println("当前元素个数："+link.size());
        link.add("Node01");
        link.add("Node02");
        link.add("Node03");
        System.out.println("当前元素个数："+link.size());
    }
}

这种链表中的数据个数的记录，在整个的链表结构开发过程之后，都是极为重要的，因为后续的很多功能都息息相关。

空链表判断

空链表的判断实质上就是进行元素个数的判断，因为在整个链表的数据结构里面，“空（不是null）”是属于链表的一种状态，实际上链表也有另外一种状态“满（整型的最大值Integer.MAX_VALUE）”，所以就必须追加一个isEmpty()判断操作。
1、在ILink接口里面增加新的处理方法：

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加    
    public int size();  //获取元素个数
    public boolean isEmpty();   //判断是否为空链表
}

2、在LinkImpl子类里面实现当前的链表结构

@Override
    public boolean isEmpty() {
        return this.count == 0;
    }

如果保存元素的个数为0，那么实际上这里面就是一个空链表。

这个时候对于链表的增加的功能才算全部实现，增加的操作里面已经考虑到了很多的性能处理，同时这种个数和空的判断一定要分开。

返回链表数据

现在链表之中已经可以实现数据内容的存储了，那么随后需要考虑的问题就是如何把这些数据取出来，对于链表里面的数据获取机制来讲，最佳的做法是迭代。但可以考虑通过数组的形式来完成处理，根据已保存元素的个数 开辟一个数组，并且就将元素保存在数组里面最终返回需要的数据。

image.png

1、在ILink增加新的返回数据的方法

范例：返回链表数据信息

interface ILink<T>{ //链表的实现标准
    public void add(T data);    //实现数据增加    
    public int size();  //获取元素个数
    public boolean isEmpty();   //判断是否为空链表
    public T[] toArray();       //链表数据转为对象数组
}

2、在LinkImpl类里面进行方法的复写

@Override
    public Object[] toArray() {
        if(this.count == 0) {
            return null;
        }
        Object [] retuenData = new Object[this.count];  //返回数组信息
        Node node = this.root;
        int foot = 0;
        while(node != null) {   //当前存在
            retuenData[foot++] = node.data; //返回当前数组内容
            node = node.next;
        }
        return retuenData;
    }

在整个链表实现结构里面，内容的存储和输出是两个最为重要的核心功能，也就是说在实际的开发过程里面即使你使用Java中类集开发框架，也都离不开这两个核心功能。

根据索引进行数据获取

链表的实际用途就在于实现了一个动态的对象数组，那么既然是一个数组的展现形式，在这里面就一定会存在有根据索引进行数据访问的需求，在使用数组的时候往往会根据索引的形式来定位数组元素，但是现在如果是自定义数据结构的链表，就需要在链表里面实现一个与之对应的功能，但是所有链表之中的数据都是依据节点引用来实现的控制，于是这里面就牵扯到一个索引定位的问题。

image.png