数据结构与算法分析：（五）循环链表

矫情吗；* 2023-07-09 09:30 1阅读 0赞

## 一、前言 ##

相信小伙伴们在前面两篇文章的详细介绍已经对单向链表、双向链表有一个很清晰的认识了。

[数据结构与算法分析：（三）单向链表][Link 1]

[数据结构与算法分析：（四）双向链表][Link 2]

接下来我们来介绍循环链表，你把单向链表、双向链表搞清楚了的话，循环链表自然也不难了。

循环链表可分为：单向循环链表、双向循环链表。

**1、单向循环链表：**  
![在这里插入图片描述][20200228163219498.png]  
单向循环链表跟单向链表唯一的区别就在`尾结点`。我们知道，单向链表的尾结点指针指向空地址，表示这就是最后的结点了。而单向循环链表的尾结点指针是指向链表的头结点。从我画的单向循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“单向循环”链表。

和单向链表相比，单向循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用单向循环链表。比如著名的`约瑟夫问题`。尽管用单向链表也可以实现，但是用单向循环链表实现的话，代码就会简洁很多。

**2、双向循环链表：**  
![在这里插入图片描述][20200228163231954.png]  
双向循环链表想必也不用我多说了吧。

## 二、循环链表实战 ##

假设有这么一个小游戏：

100个人围成圆圈，从1开始报数，喊到3人的时候退出，重复，直到剩下最后一个人。

看到围成圆圈，立马想到了`循环链表`这个数据结构。

**1、我们先来定义循环链表的接口**

public interface CircularLinkedList<E> { 
    
        /** * 向链表插入一个元素，默认在尾部 * @param item */
        void add(E item);
    
        /** * 在链表的指定位置插入一个元素 * @param index * @param item */
        void add(int index, E item);
    
        /** * 向链表插入一个元素，默认在尾部 * @param item */
        void addLast(E item);
    
        /** * 向链表头部插入一个元素 * @param item */
        void addFirst(E item);
    
        /** * 删除链表指针的当前位置的元素 * @return */
        E remove();
    
        /** * 删除链表中的item元素 * @param item */
        void remove(E item);
    
        /** * 删除链表中index位置的元素 * @param index * @return */
        E remove(int index);
    
        /** * 删除链表头部元素 * @return */
        E removeFirst();
    
        /** * 删除链表尾部元素 * @return */
        E removeLast();
    
        /** * 移动链表当前位置指针到下一个位置 */
        void next();
    
        /** * 返回链表的当前位置 * @return */
        int currentIndex();
    
        /** * 返回链表当前位置元素 * @return */
        E current();
    
        /** * 返回链表的头部元素 * @return */
        E first();
    
        /** * 返回链表的尾部元素 * @return */
        E last();
    
        /** * 获取链表index位置的元素 * @param index * @return */
        E get(int index);
    
        /** * 清空链表 */
        void clear();
    
        /** * 返回链表的长度 * @return */
        int size();
    
        /** * 当前指针是否在头部 * @return */
        boolean isFirst();
    
        /** * 当前指针是否在尾部 * @return */
        boolean isLast();
    
        /** * 判断链表是否为空 * @return */
        boolean isEmpty();
    
    }

**2、循环链表的实现类**

public class ConcurrentCircularLinkedList<E> implements CircularLinkedList<E> { 
    
        static class Node<E> { 
            E item;
            Node<E> next;
            Node(E item) { 
                this.item = item;
            }
        }
    
        final ReentrantLock lock = new ReentrantLock();
    
        private Node<E> first;
    
        private Node<E> last;
    
        private Node<E> current;
    
        private int currentIndex;
    
        private int count = 0;
    
        private int capacity;
    
        public ConcurrentCircularLinkedList() { 
            this(Integer.MAX_VALUE);
        }
    
        public ConcurrentCircularLinkedList(int capacity) { 
            this.capacity = capacity;
            current = first = last = new Node<E>(null);
            currentIndex = -1;
        }
    
        public ConcurrentCircularLinkedList(Collection<? extends E> c) { 
            this(Integer.MAX_VALUE);
            for (E item : c) { 
                addLast(item);
            }
        }
    
        private Node<E> getNode(int index) { 
            if(index < 0 || index > size()) { 
                throw new ArrayIndexOutOfBoundsException();
            }
            Node<E> node = first;
            for (int i = 0; i < index; i++) { 
                node = node.next;
            }
            return node;
        }
    
        @Override
        public void add(E item) { 
            addLast(item);
        }
    
        @Override
        public void add(int index, E item) { 
            lock.lock();
            if (index < 0 || index > size()) { 
                throw new ArrayIndexOutOfBoundsException();
            }
            if (count >= capacity) { 
                throw new IllegalArgumentException();
            }
            try { 
                Node<E> node = new Node<E>(item);
                // 链表为null时,first,last,current都指向第一个元素
                if (this.isEmpty()) { 
                    first = node;
                    last = node;
                    current = first;
                    last.next = first;
                    currentIndex = 0;
                } else { 
                    // 头部插入的时候
                    if (index == 0) { 
                        node.next = first;
                        first = node;
                        last.next = node;
                    } else if (index == size()) {  // 尾部插入
                        last.next = node;
                        last = node;
                        node.next = first;
                    } else { 
                        Node<E> n = this.first;
                        for (int i = 0; i < index; i++) { 
                            n = n.next;
                        }
                        node.next = n.next;
                        n.next = node;
                    }
                    if (index <= this.currentIndex) { 
                        this.currentIndex ++;
                    }
                }
                count++;
            } finally { 
                lock.unlock();
            }
    
        }
    
        @Override
        public void addLast(E item) { 
            if (count == 0) { 
                add(0, item);
            } else { 
                add(count, item);
            }
        }
    
        @Override
        public void addFirst(E item) { 
            add(0, item);
        }
    
        @Override
        public E remove() { 
            return remove(currentIndex);
        }
    
        @Override
        public void remove(E item) { 
            lock.lock();
            try { 
                Node<E> n = this.first;
                for (int i = 0; i < size(); i++) { 
                    if (n.item.equals(item)) { 
                        remove(i);
                        break;
                    }
                }
            } finally { 
                lock.unlock();
            }
        }
    
        @Override
        public E remove(int index) { 
            E item = null;
            lock.lock();
            try { 
                if(index < 0 || index > size()){ 
                    throw new ArrayIndexOutOfBoundsException();
                }
                if(count == 0){ 
                    throw new IllegalArgumentException();
                }
                // 链表里面只剩下一个元素了
                if (first.next == first) { 
                    current = first = last = new Node<E>(null);
                    currentIndex = -1;
                } else { 
                    // 删除头部
                    if (index == 0) { 
                        item = first.item;
                        if (current == first) { 
                            current = first.next;
                        }
                        Node<E> node = first;
                        first = first.next;
                        last.next = first;
                        node.next = null;
                    } else if (index == (size() - 1)) { // 删除尾部
                        item = last.item;
                        Node<E> pre = getNode(index - 1);
                        if (current == last) { 
                            current = pre;
                            currentIndex--;
                        }
                        pre.next = first;
                        last.next = null;
                        last = pre;
                    } else { 
                        Node<E> pre = getNode(index - 1);
                        Node<E> node = pre.next;
                        item = node.item;
                        if (node == current) { 
                            current = node.next;
                        }
                        pre.next = node.next;
                        node.next = null;
                        if (index <= currentIndex) { 
                            currentIndex--;
                        }
                    }
                }
                count--;
            } finally { 
                lock.unlock();
            }
            return item;
        }
    
        @Override
        public E removeFirst() { 
            return remove(0);
        }
    
        @Override
        public E removeLast() { 
            return remove(size() - 1);
        }
    
        @Override
        public void next() { 
            lock.lock();
            try { 
                current = current.next;
                currentIndex++;
                if (current == first) { 
                    currentIndex = 0;
                }
            } finally { 
                lock.unlock();
            }
        }
    
        @Override
        public int currentIndex() { 
            return this.currentIndex;
        }
    
        @Override
        public E current() { 
            return get(currentIndex);
        }
    
        @Override
        public E first() { 
            return first.item;
        }
    
        @Override
        public E last() { 
            return last.item;
        }
    
        @Override
        public E get(int index) { 
            return null;
        }
    
        @Override
        public void clear() { 
    
        }
    
        @Override
        public int size() { 
            return count;
        }
    
        @Override
        public boolean isFirst() { 
            return this.currentIndex == 0;
        }
    
        @Override
        public boolean isLast() { 
            return this.currentIndex == (size() - 1);
        }
    
        @Override
        public boolean isEmpty() { 
            return count == 0;
        }
    
        public String toString() { 
            if (isEmpty()) { 
                return "[]";
            }
            StringBuffer buffer = new StringBuffer();
            buffer.append("[");
            Node<E> node = first;
            while (true) { 
                buffer.append(node.item);
                node = node.next;
                if (node.next == first) { 
                    if (node != first) { 
                        buffer.append(node.item);
                        buffer.append(",");
                    }
                    buffer.append("");
                    break;
                }
            }
            buffer.append("]");
            return buffer.toString();
        }
    
    }

**3、测试类**

public class CircularLinkedListTest { 
    
        @Test
        public void test() { 
            CircularLinkedList<String> list = new ConcurrentCircularLinkedList<String>();
            for (int i = 1; i < 101; i++) { 
                list.add("" + i);
            }
            int count = 1;
            while (list.size() > 1) { 
                list.next();
                count++;
                if (count % 3 == 0) { 
                    System.out.println(list.remove() + " break!");
                    count++;
                }
            }
            System.out.println(list.toString());
        }
    
    }

**4、运行结果**

3 break!
    5 break!
    7 break!
    9 break!
    11 break!
    13 break!
    15 break!
    17 break!
    19 break!
    21 break!
    23 break!
    25 break!
    27 break!
    29 break!
    31 break!
    33 break!
    35 break!
    37 break!
    39 break!
    41 break!
    43 break!
    45 break!
    47 break!
    49 break!
    51 break!
    53 break!
    55 break!
    57 break!
    59 break!
    61 break!
    63 break!
    65 break!
    67 break!
    69 break!
    71 break!
    73 break!
    75 break!
    77 break!
    79 break!
    81 break!
    83 break!
    85 break!
    87 break!
    89 break!
    91 break!
    93 break!
    95 break!
    97 break!
    99 break!
    2 break!
    6 break!
    10 break!
    14 break!
    18 break!
    22 break!
    26 break!
    30 break!
    34 break!
    38 break!
    42 break!
    46 break!
    50 break!
    54 break!
    58 break!
    62 break!
    66 break!
    70 break!
    74 break!
    78 break!
    82 break!
    86 break!
    90 break!
    94 break!
    98 break!
    4 break!
    12 break!
    20 break!
    28 break!
    36 break!
    44 break!
    52 break!
    60 break!
    68 break!
    76 break!
    84 break!
    92 break!
    1 break!
    24 break!
    40 break!
    56 break!
    72 break!
    88 break!
    8 break!
    48 break!
    80 break!
    16 break!
    96 break!
    64 break!
    100 break!
    [32]

## 三、注意事项 ##

1、警惕指针丢失和内存泄漏  
2、利用哨兵简化实现难度  
3、重点留意边界条件处理

软件开发中，代码在一些边界或者异常情况下，最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

我经常用来检查链表代码是否正确的边界条件有这样几个：

*  如果链表为空时，代码是否能正常工作？
 *  如果链表只包含一个结点时，代码是否能正常工作？
 *  如果链表只包含两个结点时，代码是否能正常工作？
 *  代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

当你写完链表代码之后，除了看下你写的代码在正常的情况下能否工作，还要看下在上面我列举的几个边界条件下，代码仍然能否正确工作。如果这些边界条件下都没有问题，那基本上可以认为没有问题了。

## 四、多写多练 ##

精选了 5 个常见的链表操作，你只要把这几个操作写的很熟练，那么我相信你不会再怕写链表的代码了。

*  单链表反转
 *  链表中环的检测
 *  两个有序的链表合并
 *  删除链表倒数第 n 个结点
 *  求链表的中间结点

**1、单链表反转**

// 方法1:双指针迭代
    public static ListNode reverseList(ListNode head) { 
        ListNode temp = null;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) { 
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    
    // 方法2:递归解法
    public static ListNode reverseList2(ListNode head) { 
        // 递归终止条件是当前为空，或者下一个节点为空
        if (head == null || head.next == null) return head;
        // 这里的cur就是最后一个节点
        ListNode cur = reverseList2(head.next);
        // 如果链表是 1->2->3->4->5，那么此时的cur就是5
        // 而head是4，head的下一个是5，下下一个是空
        // 所以head.next.next 就是5->4
        head.next.next = head;
        // 防止链表循环，需要将head.next设置为空
        head.next = null;
        // 每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

**2、链表中环的检测**

// 快慢指针法 
    public boolean hasCycle(ListNode head) { 
        if (head == null || head.next == null) return false;
        ListNode low = head;
        ListNode fast = head.next;
        while (low != fast) { 
            if (fast == null || fast.next == null) return false;
            low = low.next;
            fast = fast.next.next;
        }
        return true;
    }

**3、两个有序的链表合并**

// 方法1: 递归
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
        if (l1 == null) { 
            return l2;
        } else if (l2 == null) { 
            return l1;
        } else if (l1.data < l2.data) { 
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else { 
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    
    // 方法2: 迭代
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { 
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (l1 != null && l2 != null) { 
            if (l1.data <= l2.data) { 
                prev.next = l1;
                l1 = l1.next;
            } else { 
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return head.next;
    }

**4、删除链表倒数第 n 个结点**

// 自己的想法
    public static ListNode removeNthFromEnd(ListNode head, int n) { 
        int len = 0;
        ListNode cur = head;
        while (cur != null) { 
            len++;
            cur = cur.next;
        }
        if (n < 1 || n > len) { 
            System.out.println("Postition of node to delete is invalid.The valid inputs are 1 to "
                    + len);
            return head;
        }
        if (len == n) { 
            ListNode temp = head.next;
            head = null;
            return temp;
        } else { 
            len = len - n;
            ListNode prev = head;
            int count = 1;
            while (count < len) { 
                prev = prev.next;
                count++;
            }
            ListNode removeNode = prev.next;
            prev.next = removeNode.next;
            removeNode = null;
        }
        return head;
    }
    
    // 双指针
    public static ListNode removeNthFromEnd2(ListNode head, int n) { 
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 1; i <= n + 1 ; i++) { 
            first = first.next;
        }
        while (first != null) { 
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

**5、求链表的中间结点**

// 自己的想法
    public static ListNode middleNode(ListNode head) { 
        int len = 0;
        ListNode cur = head;
        while (cur != null) { 
            cur = cur.next;
            len++;
        }
        int mid = len / 2;
        int count = 1;
        ListNode temp = head;
        while (count <= mid) { 
            temp = temp.next;
            count++;
        }
        return temp;
    }
    
    // 快慢指针法
    public ListNode middleNode2(ListNode head) { 
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { 
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

好了，相信这几篇链表的文章对你有帮助，有不清楚的话可以和我说，有不对的地方也欢迎指出。链表的介绍就先告一段落了。

[Link 1]: https://blog.csdn.net/riemann_/article/details/104444531
[Link 2]: https://blog.csdn.net/riemann_/article/details/104482978
[20200228163219498.png]: https://img-blog.csdnimg.cn/20200228163219498.png
[20200228163231954.png]: https://img-blog.csdnimg.cn/20200228163231954.png