【数据结构】之双向链表、双端(双向)链表、循环(双向)链表

秒速五厘米 2022-01-29 11:21 342阅读 0赞

### 双向链表、双端(双向)链表、循环(双向)链表示意(简)图： ###

**声明：**下面各图中，箭头指向的是整个节点，而不是指向节点中的prior或next。

**双向链表：**只有一个指针指向最开始的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70][]

**双端(双向)链表：**有两个指针分别指向两端的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1][]

**循环(双向)链表：**指向形成一个闭环。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 2][]

### 双端(双向)链表的Java实现(简单示例)： ###

注：双向链表、双端(双向)链表、循环(双向)链表的实现思路几乎一样，这里以实现双端(双向)链表示例。

/**
     * 双端(双向)链表的(简单)实现
     *
     * @author JustryDeng
     * @date 2019/5/21 20:51
     */
    public class DoublesidedLinkedlistImpl<T>  {
    
        /** 节点的个数 */
        private int size;
    
        /**
         * 尾节点
         * 注:本人新增节点时，从尾巴上新增
         * 注:也可以从头上进行新增节点
         */
        private Node rear;
    
        /**
         * 当前节点
         * 即:链表中最前面的节点，可理解为 队列中的头结点
         */
        private Node head;
    
        /**
         * 成员内部类， 节点
         */
        private class Node {
    
            /** 内部类的元素,Object类型 */
            private T data;
    
            /** 上一个节点(即:前驱节点)的地址 */
            private Node prior;
    
            /** 下一个节点(即:后继节点)的地址 */
            private Node next;
    
            private Node(T data) {
                this.data = data;
            }
    
            public T getData() {
                return data;
            }
    
            public void setData(T data) {
                this.data = data;
            }
    
            public Node getPrior() {
                return prior;
            }
    
            public void setPrior(Node prior) {
                this.prior = prior;
            }
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
        }
    
        /**
         * 新增节点
         *
         * @param obj
         *         添加的元素
         * @return  添加的元素对应的节点
         * @date 2019/5/20 20:48
         */
        public Node addNode(T obj) {
            // obj不能为null
            notNullCheck(obj);
            // 每次增加的元素，都作为新的尾节点
            Node newRear = new Node(obj);
            if (size == 0) {
                head = newRear;
                rear = newRear;
            } else {
                newRear.prior = rear;
                rear.next = newRear;
                // 更新尾节点
                rear = rear.next;
            }
            size++;
            return newRear;
        }
    
        /**
         * 删除当前(头)节点
         *
         * @return  被删除了的(头)节点
         * @date 2019/5/20 20:50
         */
        public Node deleteHead() {
            if(isEmpty()) {
                return null;
            }
            // targetObj存放原来的头节点数据
            Node targetNode = head;
            if (head.next != null) {
                // 断开后继节点对要删除的节点的引用
                head.next.prior = null;
            }
            // 更新头节点
            head = head.next;
            size--;
            return targetNode;
        }
    
        /**
         * 删除指定元素对应的第一个节点
         *
         * @return  删除成功与否(若元素不存在，则返回false)
         * @date 2019/5/20 20:50
         */
        public boolean deleteFirstNode(T obj) {
            // obj不能为null
            notNullCheck(obj);
            // 当head未null时，说明，当前为空链表
            if (size == 0) {
                return false;
            }
            // 当前节点
            Node current = head;
            // 前驱节点
            Node previous = head;
            // 判断条件，如果当前节点的值和待删除的值不一致，则继续
            while (!obj.equals(current.data)) {
                // 如果下一个节点不存在(即:当前节点是尾节点)
                // 则说明，不存在 元素值为obj的节点，直接返回false
                if (current.next == null) {
                    return false;
                } else {
                    // 更新前驱节点、当前节点
                    previous = current;
                    current = current.next;
                }
            }
            // 如果要删除的节点是第一个节点；
            if (head.equals(current)) {
                if (head.next != null) {
                    // 断开后继节点对要删除的节点的引用
                    head.next.prior = null;
                }
                // 更新头结点
                head = current.next;
            // 如果要删除的节点是尾节点
            } else if ((rear.equals(current))) {
                // 前驱节点断开对要删除的节点的应用
                previous.next = null;
            // 如果要删除的节点不是头结点(是中间的某个节点或尾节点)
            } else {
                // 将当前节点“抠除”，并将“两端”接上
                previous.next = current.next;
                current.prior = previous;
            }
            size--;
            return true;
        }
    
        /**
         * 删除指定元素对应的所有节点
         * 注:此方法性能较低，少用或不用
         *
         *
         * @return  删除了的节点数
         * @date 2019/5/20 20:50
         */
        public int deleteAllNode(T obj) {
            int count = 0;
            while(deleteFirstNode(obj)){
                count++;
            }
            return count;
        }
    
        /**
         * 查找元素的(第一个)节点
         *
         * @param obj
         *         待查找的元素对象
         * @return 元素的(第一个)节点, 无则返回null
         */
        public Node find(T obj) {
            // obj不能为null
            notNullCheck(obj);
            Node currNode = head;
            // 临时大小为size
            int tempSize = size;
            while (tempSize > 0) {
                if (obj.equals(currNode.data)) {
                    return currNode;
                } else {
                    currNode = currNode.next;
                }
                tempSize--;
            }
            return null;
        }
    
        /**
         * 非空检验
         *
         * @param obj
         *            被验证的对象
         * @throws NullPointerException 空指针异常(运行时异常)
         * @date 2019/5/20 21:00
         */
        private void notNullCheck(T obj){
            if(obj == null) {
                throw new NullPointerException("data must not be null!");
            }
        }
    
        /**
         * 判断链表是否为空
         *
         * @return  链表是否为空
         * @date 2019/5/20 20:49
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "[]";
            }
    
            StringBuilder sb = new StringBuilder(16);
            sb.append("[");
            Node currentNode = head;
            for (int i = 0; i < size; i++) {
                sb.append(currentNode.data);
                sb.append(", ");
                currentNode = currentNode.next;
            }
            int length = sb.length();
            sb.delete(length - 2, length).append("]");
            return sb.toString();
        }
    
        public static void main(String[] args) {
            DoublesidedLinkedlistImpl<String> uli = new DoublesidedLinkedlistImpl<>();
            // 增
            uli.addNode("A");
            uli.addNode("B");
            uli.addNode("C");
            uli.addNode("C");
            uli.addNode("D");
            uli.addNode("C");
            uli.addNode("E");
            uli.addNode("E");
            uli.addNode("F");
            uli.addNode("E");
            // toString
            System.out.println("增加节点后的初始化链表:\t" + uli);
            // 找到C元素对应的第一个节点
            System.out.println("找到C元素对应的第一个节点:" + uli.find("C")
                    + ",该节点的下下个节点的数据内容为:"
                    + uli.find("C").getNext().getNext().getData());
            // 删除头结点
            uli.deleteHead();
            // toString
            System.out.println("删除头结点后:\t" + uli);
            // 删除C元素对应的第一个节点
            uli.deleteFirstNode("C");
            // toString
            System.out.println("删除C元素对应的第一个节点后:\t" +uli);
            // 删除E元素对应的所有节点
            uli.deleteAllNode("E");
            // toString
            System.out.println("删除E元素对应的所有节点后:\t" +uli);
    
        }
    }

### 测试一下： ###

运行(写在实现类里面的)主方法，控制台输出：

![20190521214651555.png][]

**由此可见：简单的双端(双向)链表实现完毕！**

### ^\_^ 如有不当之处，欢迎指正 ###

### ^\_^ 学习视频                  51CTO学院《数据结构与算法》，讲师张晨光 ###

### ^\_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70]: /images/20220129/75cd01d056614ffbb37d95443fe6e625.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 1]: /images/20220129/720dca41562e4e31a78a5dd2fe20e1f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p1c3RyeV9kZW5n_size_16_color_FFFFFF_t_70 2]: /images/20220129/3683c9f04ed34e06b5ed128deb6e4fd5.png
[20190521214651555.png]: /images/20220129/48862dc3edb24e6ca9dca3452607d0c4.png