数据结构——链表

继上一章的数组后，介绍第二个线性结构链表，链表相对于数组来说，优于增删，数组优于查。下面就来看看这个链表的链在何处?

链式结构（链表），数组不好的地方在于它需要先申请一个固定大小的空间，没有动态性，在Java的数据结构中ArrayList实现了可变长的数组，实际上就是当长度不够的时候重新申请一块原空间1.5倍大小的新空间，再把当前的元素全部拷贝过去。链式结构在这里进行了改进，它不需要元素是在一块连续的空间内的，它只需要一个指向下一个元素的位置的地址，Java中指向下一个元素的位置的方法是使用引用，链式结构虽然解决了动态性，但是对于查找来说却不太友好，降低了随机访问的效率，因为要在链表中查找一个元素，就必须从头开始遍历，直到找到那个元素。后面的一些非线性的数据结构比如树、队列、栈都用到了链表，当然也可以使用数组来实现，就看在什么应用场景下针对不同的需求来完成了，链表有单向、双向、循环，下面就来实现一个单向链表：

package top.devonte.structure.linear;

public class LinkedStructure {

    /**
     * 单向链表，创建一个1/2/3/4的单向链表，并输出
     */
    public static void singleLinkedList() {
        Node head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + "\t");
            cur = cur.next;
        }
    }

    /**
     * 双向链表，链表能够访问前一个元素，也能访问后一个元素。（用最垃圾的代码演示）
     */
    public static void channelLinkedList() {
        ChannelNode four = new ChannelNode(4, null);
        ChannelNode three = new ChannelNode(3, four);
        four.pre = three;
        ChannelNode two = new ChannelNode(2, three);
        three.pre = two;
        ChannelNode head = new ChannelNode(1, two);
        two.pre = head;
        ChannelNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + "\t");
            cur = (ChannelNode) cur.next;
        }
        System.out.println();
        cur = four;
        while (cur != null) {
            System.out.print(cur.val + "\t");
            cur = cur.pre;
        }
    }

    public static void main(String[] args) {
        channelLinkedList();
    }

    static class ChannelNode extends Node {
        ChannelNode pre;
        public ChannelNode(int val, Node next) {
            super(val, next);
        }
    }

    static class Node {
        int val;
        Node next;
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

}

结语

链表就是一个线性结构的补充，与数组互补，这个结构使用起来特别灵活，在一些算法里面如果不熟悉链表的话，很容易将引用指向错误的地方导致死循环，并且树结构就是使用链表的方式实现的，后面会对树进行一个详细的解释，因此学好链式结构有益于后面学习树。到这里两个基本的线性结构就已经讲完了，剩下的栈和队列都是对链表和数组的运用，使用了一种特殊限制来达到栈和队列的作用。下一章将对栈进行总结。