链式存储结构

1. 注意链式存储结构在内存中并不是连续内存地址，为了解决顺序存储结构带来的问题，链式存储结构采用逻辑性的关联关系，你在内存什么位置不重要我逻辑上a1知道下一个是谁就行。
2. 所以a1不仅有本身的信息，还有一个指针这个指针指向下一个元素的位置。而一个元素加一个指针统称为结点Node。
3. 上述说过 线性表他是有限的，甭管你是什么链式你得有头有尾吧，所以通常把链表第一个结点的存储位置叫做头指针，指向第一个结点。而尾部指针为null继而形成有头有尾的一个单链表链式存储结构。

:::

单链表存储结构

java单链表链式存储结构

  

    // 指向第一个结点的指针
    private static Node head = new Node(null);

    public static void main(String[] args) throws Exception {

        Node node = new Node("第一个结点");
        Node node1 = new Node("第二个结点");
        Node node2 = new Node("第三个结点");
        Node node3 = new Node("第四个结点");

        // 指定第一个结点
        if (head.next == null) {
            head.next = node;
        }

        node.next = node1;
        node1.next = node2;
        node2.next = node3;

        // 获取指定元素
        getNode(node3);

        // 删除指定元素
        deleteNode(node3);

        // 打印所有结点
        listNode();
    }


    /**
     * 结点类
     */
    static class Node {
        // 结点数据域
        String data;
        // 下一个结点
        Node next;

        public Node(String data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }
    }


    /**
     * 获取元素
     *
     * @param node
     */
    public static void getNode(Node node) throws Exception {
        if (empty()) {
            throw new Exception("该单项链表为");
        }
        Node target = node;
        Node nodeFirst = head.next;
        while (nodeFirst != null) {
            if (nodeFirst.getData() == target.getData()) {
                System.out.println("找到了这个元素了:" + nodeFirst.getData());
                break;
            } else {
                nodeFirst = nodeFirst.getNext();
            }
        }
    }

    /**
     * 删除指定元素
     *
     * @param node
     */
    public static void deleteNode(Node node) throws Exception {
        if (empty()) {
            throw new Exception("此链表是空的，怎么删:" + JSON.toJSONString(node));
        }
        Node target = node;
        Node nodeFirst = head.next;
        Node nodeTarget = null;
        while (nodeFirst != null) {
            if (nodeFirst.getData() == target.getData()) {
                if (nodeFirst.getNext() == null) {
                    nodeTarget.next = null;
                    break;
                } else {
                    head.next = nodeFirst.next;
                    break;
                }
            } else {
                nodeTarget = nodeFirst;
                nodeFirst = nodeFirst.getNext();
            }
        }
    }

    /**
     * 判断是不是空链表
     *
     * @return
     */
    public static boolean empty() {
        if (head.next == null) {
            return true;
        }
        return false;
    }


    /**
     * 打印所有结点
     */
    public static void listNode() throws Exception {
        if (empty()) {
            throw new Exception("此链表是一个空链表,打印什么？");
        }
        Node target = head.next;
        while (target != null) {
            System.out.println("结点打印:" + target.getData());
            target = target.next;
        }
    }