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

28次阅读

共计 10326 个字符，预计需要花费 26 分钟才能阅读完成。

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

正文完
数据结构与算法
2020-11-22
 0
关于数据结构与算法:Java数据结构与算法分析-队列
关于数据结构与算法:数据结构与算法腾讯面试官让我模拟快排的执行过程背好的代码竟无用武之地
快速幂算法-及其Python实现
关于数据结构与算法:Linklist经典题目旋转链表双指针应用