小码哥《恋上数据结构与算法》笔记（四）：循环链表

叁歲伎倆 2023-07-20 13:53 28阅读 0赞

> 具体代码在 [LinkedList][] , 欢迎 `star`

## 目录 ##

*  一、单向循环链表（Simple LinkedList）
 *  二、单向循环链表接口设计
 *  三、单向循环链表的实现
    
     *  1、插入结点(`重点`)
     *  2、删除结点
 *  四、双向循环链表
 *  五、双向循环链表接口设计
 *  六、双向循环链表接的实现
    
     *  1、插入结点
     *  2、删除节点

附录: 单向循环链表  
附录: 双向循环链表

--------------------

# 一、单向循环链表 #

跳转到目录

*  尾结点的`next`，指向头结点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

# 二、单向循环链表接口设计 #

*  相对于**单链表**，`单向循环链表`需要重写`插入结点`、`删除结点`两个方法。

# 三、单向循环链表的实现 #

### 1、插入结点 ###

跳转到目录

*  **插入结点，需要特别关注`插入头结点`的情况。此时需要拿到`尾结点`，然后将其`next`指向新结点, 中间的结点操作和单链表的操作一样。**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

public void add(int index, E element) { 
        rangeCheckForAdd(index);
    
        // 当index传0的时候,就会报异常,此时要特殊处理 (上图的情况)
        // 往0位置,插入元素
        if (index == 0) { 
            Node<E> newFirst = new Node<>(element, first);
    
            // 拿到最后一个结点; 判断只有一个结点的情况
            Node<E> last = (size == 0) ? newFirst : node(size - 1);
            // 最后一个结点的next指向头结点
            last.next = newFirst;
            first = newFirst;
    
        } else { 
            // 在index处插入元素,首先要找到它前面的结点
            Node<E> preNode = node(index - 1);
            // 让前面的结点的next指向新创建的结点,新创建的结点指向index处的结点即可
            // 此时index处的结点,就是它前面的结点的next,就是指向index处的结点
            Node<E> newNode = new Node<>(element, preNode.next);
            // 前面的结点的next再指向新的结点
            preNode.next = newNode;
        }
        size++;
    }

### 2、删除结点 ###

跳转到目录

*  如果删除的是`头结点`，删除后需让`last`指向新的头结点。
 *  当只有一个结点并删除时, `first`指向`null`。

/** * 返回的是被删除元素的element */
    public E remove(int i ndex) { 
        // 假如被删除的结点为第一个结点
        Node<E> node = first;
        if (index == 0) { 
            if (size == 1) {  // 链表中只有一个元素的时候
                first = null;
            } else { 
                Node<E> last = node(size - 1);
                // first已经指向了第一个结点,如果要删除第一个结点,此时要将first指向第一个结点的next结点
                first = first.next;
                last.next = first; // 最后一个结点指向新的第一个结点
            }
        } else { 
            Node<E> preNode = node(index - 1);
            node = preNode.next; // 这个node就是当前被删除的结点
            //preNode.next = preNode.next.next;
            preNode.next = node.next;
        }
        size--;
        return node.element;
    }

# 四、双向循环链表 #

跳转到目录

*  头节点的`prev`指向尾节点。
 *  尾节点的`next`指向头节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

# 五、双向循环链表接口设计 #

*  相较于`双向链表`，双向循环链表需要重写`插入节点`、`删除节点`两个方法。

# 六、双向循环链表接的实现 #

*  特殊情况  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]

### 1、插入结点 ###

跳转到目录

*  需特殊处理`添加第一个元素`和`添加到尾节点`两种特殊情况。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]

public void add(int index, E element) { 
    	    rangeCheckForAdd(index);
    	    
    	    if (index == size) {     // 往最后添加元素
    	        Node<E> oldLast = last; // 之前的最后一个结点
    	        last = new Node<E>(oldLast, element, first);
    	        if (oldLast == null) {   // 这是链表添加的第一个元素
    	            // 此时链表的first,last都指向新结点
    	            first = last;
    	            first.next = first; // 新节点的next指向的是自己
    	            first.prev = first; // 新节点的prev指向的是自己
    	        } else { 
    	            // 再将原来的last指向现在的last
    	            oldLast.next = last;
    	            first.prev = last; // 链表第一个节点的prev指向新添加的最后一个节点last
    	        }
    	    } else { 
    	        // 获取当前要插入位置的结点
    	        Node<E> next = node(index);
    	        // 其上一个结点
    	        Node<E> prev = next.prev;
    	        // 创建一个新的结点(这个新结点的指向已经初始化好了)
    	        Node<E> node = new Node<>(prev, element, next);
    	        next.prev = node;
    	        prev.next = node;
    	
    	        if (index == 0) {  // next == first;
    	            // 也就是插入到第一个结点的位置
    	            first = node;
    	        }
    	    }
    	    size++;
    }

### 2、删除节点 ###

跳转到目录

*  删除节点，就是在环上去掉某一个节点，然后根据删除的节点是首节点或者尾节点来处理`first`和`last`。
 *  需要特殊处理只有一个节点的删除操作。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]

/** * 返回的是被删除元素的element */
    public E remove(int index) { 
        rangeCheck(index);
    
        Node<E> node = first;
        if (size == 1) {  // 链表只有一个元素
            first = null;
            last = null;
        } else { 
            node = node(index);
            Node<E> prev = node.prev;
            Node<E> next = node.next;
            prev.next = next;
            next.prev = prev;
    		// 删除的是第一个结点
            if (index == 0) {  // node == first;
                first = next;
            }
            // 删除的是最后一个结点
            if (index == size - 1) { // node == last
                last = prev;
            }
    
        }
    
        size--;
        return node.element;
    }

--------------------

### 附录: 单向循环链表  ###

**注意: List接口, AbstractList抽象类 参考单向链表那一篇博客**

package com.zy.single;
    
    import com.zy.AbstractList;
    
    /** * Description: 单向循环链表实现 * * @author zygui * @date 2020/3/19 21:22 */
    public class SingleCircleLinkedList<E> extends AbstractList<E> { 
    
        /* 单向循环链表, 相对于单链表; 我们只需要更高 add、remove方法即可! */
    
        /** * 指向第一个结点 */
        protected Node<E> first;
    
    
        /** * 结点类;为链表的内部类 * * @param <E> */
        protected static class Node<E> { 
    
            //存储元素的信息
            E element;
    
            //指向下一个结点
            Node<E> next;
    
            // 结点构造器
            public Node(E element, Node<E> next) { 
                this.element = element;
                this.next = next;
            }
    
            @Override
            public String toString() { 
                StringBuilder sb = new StringBuilder();
                sb.append(element).append("_").append(next.element);
                return sb.toString();
            }
        }
    
        @Override
        public void clear() { 
            size = 0;
            first = null;
        }
    
        @Override
        public E get(int index) { 
            // 通过node方法找到结点,通过结点的element来获取元素
            return node(index).element;
        }
    
        @Override
        public E set(int index, E element) { 
            // 获取index处的结点
            Node<E> node = node(index);
            E oldElement = node.element;
            node.element = element;
            // 返回的是没覆盖之前的结点元素信息
            return oldElement;
        }
    
        @Override
        public void add(int index, E element) { 
            rangeCheckForAdd(index);
    
            // 当index传0的时候,就会报异常,此时要特殊处理
            if (index == 0) { 
                Node<E> newFirst = new Node<>(element, first);
    
                // 拿到最后一个结点; 判断只有一个结点的情况
                Node<E> last = (size == 0) ? newFirst : node(size - 1);
                // 最后一个结点的next指向头结点
                last.next = newFirst;
                first = newFirst;
    
            } else { 
                // 在index处插入元素,首先要找到它前面的结点
                Node<E> preNode = node(index - 1);
                // 让前面的结点的next指向新创建的结点,新创建的结点指向index处的结点即可
                // 此时index处的结点,就是它前面的结点的next,就是指向index处的结点
                Node<E> newNode = new Node<>(element, preNode.next);
                // 前面的结点的next再指向新的结点
                preNode.next = newNode;
            }
            size++;
        }
    
        @Override
        /** * 返回的是被删除元素的element */
        public E remove(int index) { 
            // 假如被删除的结点为第一个结点
            Node<E> node = first;
            if (index == 0) { 
                if (size == 1) {  // 链表中只有一个元素的时候
                    first = null;
                } else { 
                    Node<E> last = node(size - 1);
                    // first已经指向了第一个结点,如果要删除第一个结点,此时要将first指向第一个结点的next结点
                    first = first.next;
                    last.next = first; // 最后一个结点指向新的第一个结点
                }
            } else { 
                Node<E> preNode = node(index - 1);
                node = preNode.next; // 这个node就是当前被删除的结点
                //preNode.next = preNode.next.next;
                preNode.next = node.next;
            }
            size--;
            return node.element;
        }
    
        @Override
        public void remove(E element) { 
            remove(indexOf(element));
        }
    
        @Override
        /** * element是保存在node里的,传入element,返回该结点的索引 */
        public int indexOf(E element) { 
            Node<E> node = first;
            if (element == null) { 
                // 因为element都在node中,所以通过next来遍历node
                for (int i = 0; i < size; i++) { 
                    if (node.element == null) return i;
                    node = node.next;
                }
            } else { 
                for (int i = 0; i < size; i++) { 
                    if (element.equals(node.element)) return i;
                    node = node.next;
                }
            }
            return ELEMENT_NOT_FOUNT;
        }
    
        /** * 传入一个index,返回该index位置的结点对象 * * @param index * @return */
        private Node<E> node(int index) { 
            // 当传入非法index就会报异常
            rangeCheck(index);
            /* 通过first去寻找结点,看需要next几次,找到该结点; 可以发现,next的次数和index有关系,index为几,就需要next几次 */
            Node<E> node = first;
            for (int i = 0; i < index; i++) { 
                node = node.next;
            }
            return node;
        }
    
        @Override
        public String toString() { 
            // 打印格式: size=3, [10, 20, 30]
            // 使用StringBuilder 效率高一些
            StringBuilder string = new StringBuilder();
            string.append("size=").append(size).append(", [");
            Node<E> node = first;
            for (int i = 0; i < size; i++) { 
                string.append(node.toString());
                if (i != size - 1) { 
                    string.append(", ");
                }
                node = node.next;
            }
            string.append("]");
            return string.toString();
        }
    }

--------------------

### 附录: 双向循环链表  ###

package com.zy;
    
    /** * Description: 双向循环链表实现 * * @author zygui * @date 2020/3/19 21:22 */
    public class DoubleCircleLinkedList<E> extends AbstractList<E> { 
    
        /** * 指向第一个结点 */
        private Node<E> first;
    
        /** * 指向最后一个结点 */
        private Node<E> last;
    
    
        /** * 结点类;为链表的内部类 * * @param <E> */
        private static class Node<E> { 
    
            //存储元素的信息
            E element;
    
            //指向下一个结点
            Node<E> next;
    
            // 指向上一个结点
            Node<E> prev;
    
            // 结点构造器
            public Node(Node<E> prev, E element, Node<E> next) { 
                this.prev = prev;
                this.element = element;
                this.next = next;
            }
    
            @Override
            public String toString() { 
                StringBuilder sb = new StringBuilder();
                if (prev != null) { 
                    sb.append(prev.element);
                }
                sb.append("_").append(element).append("_");
                if (next != null) { 
                    sb.append(next.element);
                } else { 
                    sb.append("null");
                }
                return sb.toString();
            }
        }
    
        @Override
        public void clear() { 
            size = 0;
            first = null;
            last = null;
        }
    
        @Override
        public E get(int index) { 
            // 通过node方法找到结点,通过结点的element来获取元素
            return node(index).element;
        }
    
        @Override
        public E set(int index, E element) { 
            // 获取index处的结点
            Node<E> node = node(index);
            E oldElement = node.element;
            node.element = element;
            // 返回的是没覆盖之前的结点元素信息
            return oldElement;
        }
    
        @Override
        public void add(int index, E element) { 
    
            rangeCheckForAdd(index);
    
            if (index == size) {     // 往最后添加元素
                Node<E> oldLast = last; // 之前的最后一个结点
                last = new Node<E>(oldLast, element, first);
                if (oldLast == null) {   // 这是链表添加的第一个元素
                    // 此时链表的first,last都指向新结点
                    first = last;
                    first.next = first;
                    first.prev = first;
                } else { 
                    // 再将原来的last指向现在的last
                    oldLast.next = last;
                    first.prev = last;
                }
            } else { 
                // 获取当前要插入位置的结点
                Node<E> next = node(index);
                // 其上一个结点
                Node<E> prev = next.prev;
                // 创建一个新的结点(这个新结点的指向已经初始化好了)
                Node<E> node = new Node<>(prev, element, next);
                next.prev = node;
                prev.next = node;
    
                if (index == 0) {  // next == first;
                    // 也就是插入到第一个结点的位置
                    first = node;
                }
            }
            size++;
        }
    
        @Override
        /** * 返回的是被删除元素的element */
        public E remove(int index) { 
            rangeCheck(index);
    
            Node<E> node = first;
            if (size == 1) { 
                first = null;
                last = null;
            } else { 
                node = node(index);
                Node<E> prev = node.prev;
                Node<E> next = node.next;
                prev.next = next;
                next.prev = prev;
    
                if (index == 0) {  // node == first;
                    first = next;
                }
                if (index == size - 1) { // node == last
                    last = prev;
                }
    
            }
    
            size--;
            return node.element;
        }
    
        @Override
        public void remove(E element) { 
            remove(indexOf(element));
        }
    
        @Override
        /** * element是保存在node里的,传入element,返回该结点的索引 */
        public int indexOf(E element) { 
            Node<E> node = first;
            if (element == null) { 
                // 因为element都在node中,所以通过next来遍历node
                for (int i = 0; i < size; i++) { 
                    if (node.element == null) return i;
                    node = node.next;
                }
            } else { 
                for (int i = 0; i < size; i++) { 
                    if (element.equals(node.element)) return i;
                    node = node.next;
                }
            }
            return ELEMENT_NOT_FOUNT;
        }
    
        /** * 传入一个index,返回该index位置的结点对象 * * @param index * @return */
        private Node<E> node(int index) { 
            // 当传入非法index就会报异常
            rangeCheck(index);
    
            if (index < (size >> 1)) { 
                /* 通过first去寻找结点,看需要next几次,找到该结点; 可以发现,next的次数和index有关系,index为几,就需要next几次 */
                Node<E> node = first;
                for (int i = 0; i < index; i++) { 
                    node = node.next;
                }
                return node;
            } else { 
                /* 从后往前找, 因为是双向链表; */
                Node<E> node = last;
                for (int i = size - 1; i > index; i--) { 
                    node = node.prev;
                }
                return node;
            }
        }
    
        @Override
        public String toString() { 
            // 打印格式: size=3, [10, 20, 30]
            // 使用StringBuilder 效率高一些
            StringBuilder string = new StringBuilder();
            string.append("size=").append(size).append(", [");
            Node<E> node = first;
            for (int i = 0; i < size; i++) { 
                string.append(node.toString());
                if (i != size - 1) { 
                    string.append(", ");
                }
                node = node.next;
            }
            string.append("]");
            return string.toString();
        }
    }

[LinkedList]: https://github.com/coderZYGui/linked-list
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20230528/58c428b3f4b14ebdbaf2d45deb79f3be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20230528/c6d4c390aca147a0bd3f92a9cee9d4c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20230528/68829aa1cdb2426cb8e76c4e8a3c8229.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: /images/20230528/e8a0eb9fe63c45d0b8022d558b15e182.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]: /images/20230528/32f99ef075144f508fac8b23f6bbe9b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 5]: /images/20230528/f56386a2809c4314aa519ad461f64151.png