乐趣区

关于数据结构与算法:Java数据结构与算法分析-链表单链表双链表环形链表

jiezi

GitHub 源码分享

我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/linkedlist

1. 前言

通过前篇文章《数组》理解到数组的存储构造是一块间断的内存，插入和删除元素时其每个局部都有可能整体挪动。为了防止这样的线性开销，咱们须要保证数据能够不间断存储。本篇介绍另一种数据结构：链表。

2. 链表（Linked List）

链表是一种线性的数据结构，其物理存储构造是零散的，数据元素通过指针实现链表的逻辑程序。链表由一系列结点（链表中每一个元素称为节点）组成，节点能够在内存中动静生成。

链表的个性：

  • 链表是以节点（Node）的形式来存储，所以又叫链式存储。
  • 节点能够间断存储，也能够不间断存储。
  • 节点的逻辑程序与物理程序能够不统一
  • 表能够裁减（不像数组那样还得重新分配内存空间）

链表分为单链表、双链表和环形链表，上面通过实例一一介绍。

3. 单链表（Singly Linked List）

单链表又叫单向链表，其节点由两局部形成：

  • data域：数据域，用来存储元素数据
  • next域：用于指向下一节点

单链表的构造如下图：

3.1 单链表的操作

单链表的所有操作都是从 head 开始，head自身不存储元素，其 next 指向第一个节点，而后顺着 next 链进行一步步操作。其尾部节点的 next 指向为空，这也是判断尾部节点的根据。

这里次要介绍插入和删除节点的操作。

3.1.1 插入节点

向单链表中插入一个新节点，能够通过调整两次 next 指向来实现。如下图所示，X 为新节点，将其 next 指向为 A2，再将 A1 的 next 指向为 X 即可。

若是从尾部节点插入，间接将尾部节点的 next 指向新节点即可。

3.1.2 删除节点

从单链表中删除一个节点，能够通过批改 next 指向来实现，如下图所示，将 A1 的 next 指向为 A3，这样便删除 A2，A2 的内存空间会主动被垃圾回收。

若是删除尾部节点，间接将上一节点的 next 指向为空即可。

3.2 代码实现

咱们应用 Java 代码来实现一个单链表。其中 Node 类存储单链表的一个节点，SinglyLinkedList类实现了单链表的所有操作方法。
SinglyLinkedList类应用带头节点的形式实现，即 head 节点，该节点不存储数据，只是标记单链表的开始。

public class SinglyLinkedListDemo {public static void main(String[] args) {Node node1 = new Node(1, "张三");
        Node node2 = new Node(3, "李四");
        Node node3 = new Node(7, "王五");
        Node node4 = new Node(5, "赵六");

        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        System.out.println("----------- 增加节点（尾部）");
        singlyLinkedList.add(node1);
        singlyLinkedList.add(node2);
        singlyLinkedList.add(node3);
        singlyLinkedList.add(node4);
        singlyLinkedList.print();

        System.out.println("----------- 获取某个节点");
        Node node = singlyLinkedList.get(3);
        System.out.println(node);

        singlyLinkedList.remove(node3);
        System.out.println("----------- 移除节点");
        singlyLinkedList.print();

        System.out.println("----------- 批改节点");
        singlyLinkedList.update(new Node(5, "赵六 2"));
        singlyLinkedList.print();

        System.out.println("----------- 按程序增加节点");
        Node node5 = new Node(4, "王朝");
        singlyLinkedList.addOfOrder(node5);
        singlyLinkedList.print();}


    private static class SinglyLinkedList {

        // head 节点是单链表的开始，不用来存储数据
        private Node head = new Node(0, null);

        /**
         * 将节点增加到尾部
         *
         * @param node
         */
        public void add(Node node) {
            Node temp = head;
            while (true) {if (temp.next == null) {
                    temp.next = node;
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 按程序增加节点
         *
         * @param node
         */
        public void addOfOrder(Node node) {
            Node temp = head;
            while (true) {if (temp.next == null) {
                    temp.next = node;
                    break;
                } else if(temp.next.key > node.getKey()){
                    node.next = temp.next;
                    temp.next = node;
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 获取某个节点
         *
         * @param key
         * @return
         */
        public Node get(int key) {if (head.next == null) {return null;}
            Node temp = head.next;
            while (temp != null) {if (temp.key == key) {return temp;}
                temp = temp.next;
            }
            return null;
        }

        /**
         * 移除一个节点
         *
         * @param node
         */
        public void remove(Node node) {
            Node temp = head;
            while (true) {if (temp.next == null) {break;}
                if (temp.next.key == node.key) {
                    temp.next = temp.next.next;
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 批改一个节点
         *
         * @param node
         */
        public void update(Node node) {
            Node temp = head.next;
            while (true) {if (temp == null) {break;}
                if (temp.key == node.key) {
                    temp.value = node.value;
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 打印链表
         */
        public void print() {
            Node temp = head.next;
            while (temp != null) {System.out.println(temp.toString());
                temp = temp.next;
            }
        }

    }


    private static class Node {
        private final int key;
        private String value;
        private Node next;

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {return key;}

        public String getValue() {return value;}

        public void setValue(String value) {this.value = value;}

        public Node getNext() {return next;}

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value='" + value + '\'' +
                    '}';
        }
    }
}

输入后果：

----------- 增加节点（尾部）Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 获取某个节点
Node{key=3, value='李四'}
----------- 移除节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=5, value='赵六'}
----------- 批改节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=5, value='赵六 2'}
----------- 按程序增加节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=4, value='王朝'}
Node{key=5, value='赵六 2'}

3.3 单链表的毛病

通过对单链表的剖析，能够看出单链表有如下毛病：
（1）单链表的查找办法只能是一个方向
（2）单链表不能自我删除，须要靠上一节点进行辅助操作。

而这些毛病能够通过双链表来解决，上面来看具体介绍。

4. 双链表（Doubly Linked List）

双链表又叫双向链表，其节点由三局部形成：

  • prev域：用于指向上一节点
  • data域：数据域，用来存储元素数据
  • next域：用于指向下一节点

双链表的构造如下图：

4.1 双链表的操作

双链表的操作能够从两端开始，从第一个节点通过 next 指向能够一步步操作到尾部，从最初一个节点通过 prev 指向能够一步步操作到头部。

这里次要介绍插入和删除节点的操作。

4.1.1 插入节点

向双链表中插入一个新节点，须要通过调整两次 prev 指向和两次 next 指向来实现。如下图所示，X 为新节点，将 A1 的 next 指向 X，将 X 的 next 指向 A2，将 A2 的 prev 指向 X，将 X 的 prev 指向 A1 即可。

4.1.2 删除节点

从双链表中删除一个节点，须要通过调整一次 prev 指向和一次 next 指向来实现。如下图所示，删除 A2 节点，将 A1 的 next 指向 A3，将 A3 的 prev指向 A1 即可。

4.2 代码实现

咱们应用 Java 代码来实现一个双链表。其中 Node类存储双链表的一个节点，DoublyLinkedListDemo类实现双链表的所有操作方法。
DoublyLinkedListDemo类应用不带头节点的形式实现，其中 first 为第一个节点，last为最初一个节点。这两个节点默认都为空，若只有一个元素时，则两个节点指向同一元素。

public class DoublyLinkedListDemo {public static void main(String[] args) {DoublyLinkedList doublyLinkedList = new DoublyLinkedList();

        System.out.println("----------- 从尾部增加节点");
        doublyLinkedList
                .addToTail(new Node(1, "张三"))
                .addToTail(new Node(3, "李四"))
                .addToTail(new Node(7, "王五"))
                .addToTail(new Node(5, "赵六"))
                .print();

        System.out.println("----------- 从头部增加节点");
        doublyLinkedList
                .addToHead(new Node(0, "朱开山"))
                .print();

        System.out.println("----------- 获取某个节点");
        System.out.println(doublyLinkedList.get(3));

        System.out.println("----------- 移除节点");
        doublyLinkedList
                .remove(new Node(3, "李四"))
                .print();

        System.out.println("----------- 批改节点");
        doublyLinkedList
                .update(new Node(5, "赵六 2")).print();

        System.out.println("----------- 按程序增加节点");
        doublyLinkedList
                .addOfOrder(new Node(4, "王朝"))
                .print();}

    private static class DoublyLinkedList {

        private Node first = null; // first 节点是双链表的头部，即第一个节点
        private Node last = null; // tail 节点是双链表的尾部，即最初一个节点

        /**
         * 从尾部增加
         *
         * @param node
         */
        public DoublyLinkedList addToTail(Node node) {if (last == null) {first = node;} else {
                last.next = node;
                node.prev = last;
            }
            last = node;
            return this;
        }

        /**
         * 依照程序增加
         *
         * @param node
         */
        public DoublyLinkedList addOfOrder(Node node) {if (first == null) {
                first = node;
                last = node;
                return this;
            }

            // node 比头节点小，将 node 设为头节点
            if (first.key > node.key) {
                first.prev = node;
                node.next = first;
                first = node;
                return this;
            }

            // node 比尾节点大，将 node 设为尾节点
            if (last.key < node.key) {
                last.next = node;
                node.prev = last;
                last = node;
                return this;
            }

            Node temp = first.next;
            while (true) {if (temp.key > node.key) {
                    node.next = temp;
                    node.prev = temp.prev;
                    temp.prev.next = node;
                    temp.prev = node;
                    break;
                }
                temp = temp.next;
            }
            return this;
        }

        /**
         * 从头部增加
         *
         * @param node
         */
        public DoublyLinkedList addToHead(Node node) {if (first == null) {last = node;} else {
                node.next = first;
                first.prev = node;
            }
            first = node;
            return this;
        }

        /**
         * 获取节点
         *
         * @param key
         * @return
         */
        public Node get(int key) {if (first == null) {return null;}
            Node temp = first;
            while (temp != null) {if (temp.key == key) {return temp;}
                temp = temp.next;
            }
            return null;
        }

        /**
         * 移除节点
         *
         * @param node
         */
        public DoublyLinkedList remove(Node node) {if (first == null) {return this;}
            // 要移除的是头节点
            if (first == node) {
                first.next.prev = null;
                first = first.next;
                return this;
            }
            // 要移除的是尾节点
            if (last == node) {
                last.prev.next = null;
                last = last.prev;
                return this;
            }

            Node temp = first.next;
            while (temp != null) {if (temp.key == node.key) {
                    temp.prev.next = temp.next;
                    temp.next.prev = temp.prev;
                    break;
                }
                temp = temp.next;
            }
            return this;
        }

        /**
         * 批改某个节点
         *
         * @param node
         */
        public DoublyLinkedList update(Node node) {if (first == null) {return this;}

            Node temp = first;
            while (temp != null) {if (temp.key == node.key) {
                    temp.value = node.value;
                    break;
                }
                temp = temp.next;
            }
            return this;
        }

        /**
         * 打印链表
         */
        public void print() {if (first == null) {return;}
            Node temp = first;
            while (temp != null) {System.out.println(temp);
                temp = temp.next;
            }
        }
    }

    private static class Node {
        private final int key;
        private String value;
        private Node prev; // 指向上一节点
        private Node next; // 指向下一节点

        public Node(int key, String value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value='" + value + '\'' +
                    '}';
        }
    }
}

输入后果：

----------- 从尾部增加节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 从头部增加节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 获取某个节点
Node{key=3, value='李四'}
----------- 移除节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 批改节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=7, value='王五'}
Node{key=5, value='赵六 2'}
----------- 按程序增加节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=4, value='王朝'}
Node{key=7, value='王五'}
Node{key=5, value='赵六 2'}

5. 环形链表（Circular Linked List）

环形链表又叫循环链表，本文讲述的是环形单向链表，其与单链表的惟一区别是尾部节点的 next 不再为空，则是指向了头部节点，这样便造成了一个环。

环形链表的构造如下图：

5.1 约瑟夫问题

约瑟夫问题：有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，相似问题又称为约瑟夫环。又称“丢手绢问题”。

引自百度百科：

据说驰名犹太历史学家 Josephus 有过以下的故事：在罗马人霸占乔塔帕特后，39 个犹太人与 Josephus 及他的敌人躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个他杀形式，41 集体排成一个圆圈，由第 1 集体开始报数，每报数到第 3 人该人就必须他杀，而后再由下一个从新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的敌人并不想听从。首先从一个人开始，越过 k - 2 集体（因为第一个人曾经被越过），并杀掉第 k 集体。接着，再越过 k - 1 集体，并杀掉第 k 集体。这个过程沿着圆圈始终进行，直到最终只剩下一个人留下，这个人就能够持续活着。问题是，给定了和，一开始要站在什么中央能力防止被处决。Josephus 要他的敌人先伪装听从，他将敌人与本人安顿在第 16 个与第 31 个地位，于是逃过了这场死亡游戏。

17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15 个教徒和 15 个非教徒在深海上脱险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个方法：30 集体围成一圆圈，从第一个人开始顺次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余 15 集体为止。问怎么排法，能力使每次投入大海的都是非教徒。

问题剖析与算法设计

约瑟夫问题并不难，但求解的办法很多；题目的变动模式也很多。这里给出一种实现办法。

题目中 30 集体围成一圈，因此启发咱们用一个循环的链来示意，能够应用构造数组来形成一个循环链。构造中有两个成员，其一为指向下一个人的指针，以形成环形的链；其二为该人是否被扔下海的标记，为 1 示意还在船上。从第一个人开始对还未扔下海的人进行计数，每数到 9 时，将构造中的标记改为 0，示意该人已被扔下海了。这样循环计数直到有 15 集体被扔下海为止。

5.2 代码实现

咱们应用 Java 代码来实现一个环形链表，并将节点按约瑟夫问题程序出列。

public class CircularLinkedListDemo {public static void main(String[] args) {CircularLinkedList circularLinkedList = new CircularLinkedList();

        System.out.println("----------- 增加 10 个节点");
        for (int i = 1; i <= 10; i++) {circularLinkedList.add(new Node(i));
        }
        circularLinkedList.print();

        System.out.println("----------- 按约瑟夫问题程序出列");
        circularLinkedList.josephusProblem(3);

    }

    private static class CircularLinkedList {
        private Node first = null; // 头部节点，即第一个节点

        /**
         * 增加节点，并将新增加的节点的 next 指向头部，造成一个环形
         *
         * @param node
         * @return
         */
        public void add(Node node) {if (first == null) {
                first = node;
                first.next = first;
                return;
            }

            Node temp = first;
            while (true) {if (temp.next == null || temp.next == first) {
                    temp.next = node;
                    node.next = first;
                    break;
                }
                temp = temp.next;
            }
        }

        /**
         * 按约瑟夫问题程序出列
         * 即从第 1 个元素开始报数，报到 num 时以后元素出列，而后从新从下一个元素开始报数，直至所有元素出列
         *
         * @param num 示意报几次数
         */
        public void josephusProblem(int num) {
            Node currentNode = first;
            // 将以后节点指向最初一个节点
            do {currentNode = currentNode.next;} while (currentNode.next != first);

            // 开始出列
            while (true) {
                // 以后节点要指向待入列节点的前一节点（双向环形队列不须要）for (int i = 0; i < num - 1; i++) {currentNode = currentNode.next;}
                System.out.printf("%s\t", currentNode.next.no);
                if(currentNode.next == currentNode){break;}
                currentNode.next = currentNode.next.next;
            }
        }

        /**
         * 输入节点
         */
        public void print() {if (first == null) {return;}

            Node temp = first;
            while (true) {System.out.printf("%s\t", temp.no);
                if (temp.next == first) {break;}
                temp = temp.next;
            }
            System.out.println();}
    }

    private static class Node {
        private final int no;
        private Node next; // 指向下一节点

        public Node(int no) {this.no = no;}

        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    '}';
        }
    }
}

输入后果：

----------- 增加 10 个节点
1    2    3    4    5    6    7    8    9    10    
----------- 按约瑟夫问题程序出列
3    6    9    2    7    1    8    5    10    4
退出移动版