AI 助理
备案控制台
开发者社区 云计算 文章 正文

《恋上数据结构第1季》单向循环链表、双向循环链表以及约瑟夫环问题

2022-05-25 93
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《恋上数据结构第1季》单向循环链表、双向循环链表以及约瑟夫环问题

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

链表的接口设计

在这里插入图片描述
由于链表的大部分接口和动态数组一致，我们抽取出一个共同的 List 接口；

package com.mj;

public interface List<E> {
    static final int ELEMENT_NOT_FOUND = -1;
    /**
     * 清除所有元素
     */
    void clear();

    /**
     * 元素的数量
     * @return
     */
    int size();

    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    boolean contains(E element);

    /**
     * 添加元素到尾部
     * @param element
     */
    void add(E element);

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    E get(int index);

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素ֵ
     */
    E set(int index, E element);

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    void add(int index, E element);

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    E remove(int index);

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    int indexOf(E element);
}

再将一些通用的字段与方法放到一个抽象类中，无论是动态数组还是链表都只需要继承这个抽象类即可。

package com.mj;

public abstract class AbstractList<E> implements List<E>{
    
    protected int size;
    
    // 下标越界抛出的异常
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    // 检查下标越界(不可访问或删除size位置)
    protected void rangeCheck(int index){
        if(index < 0 || index >= size){
            outOfBounds(index);
        }
    }
    // 检查add()的下标越界(可以在size位置添加元素)
    protected void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @Override
    public boolean contains(E element) {
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    @Override
    public void add(E element) {
        add(size, element);
    }

}

单向循环链表

在这里插入图片描述
单向循环链表 - 只有1个节点的情况：
在这里插入图片描述

单向循环链表完整源码

package com.mj.circle;

import com.mj.AbstractList;

/**
 * 单向循环链表
 * 
 * @author yusael
 */
public class SingleCircleLinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    private 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) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if (index == 0) {
            Node<E> newFirst = new Node<>(element, first);
            // 拿到最后一个节点, 上面先不要直接改first, 否则下面找节点会出现问题
            Node<E> last = (size == 0) ? newFirst : node(size - 1);
            last.next = newFirst;
            first = newFirst;
        } else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = first;
        if (index == 0) {
            if (size == 1) {
                first = null;
            } else {
                Node<E> last = node(size - 1);
                first = first.next;
                last.next = first;
            }
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == element) return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据索引找到节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("[size=").append(size).append(", ");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node.element);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}

双向循环链表

在这里插入图片描述
双向循环链表 - 只有1个节点的情况：
在这里插入图片描述

双向循环链表完整源码

package com.mj.circle;

import com.mj.AbstractList;

/**
 * 双向循环链表
 * @author yusael
 */
public class CircleLinkedList<E> extends AbstractList<E> {

    private Node<E> first;
    private Node<E> last;
    private Node<E> current; // 指针访问当前节点

    private static class Node<E> {
        E element;
        Node<E> prev;
        Node<E> next;

        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);
            } else {
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }

            return sb.toString();
        }
    }

    public void reset() {
        current = first;
    }

    public E next() {
        if (current == null) return null;
        current = current.next;
        return current.element;
    }

    /**
     * 删除 current 节点
     */
    public E remove() {
        if (current == null) return null;
        Node<E> next = current.next;
        E element = remove(current);
        if(size == 0){
            current = null;
        }else{
            current = next;
        }
        return element;
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        E old = node(index).element;
        node(index).element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if (index == size) { // 往最后面添加元素
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, first);
            if (oldLast == null) { // 这是链表添加的第一个元素
                first = last;
                first.next = first;
                first.prev = first;
            } else {
                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 (next == first) { // index==0
                first = node;
            }
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        return remove(node(index));
    }

    public E remove(Node<E> node) {
        if (size == 1) {
            first = null;
            last = null;
        } else {
            Node<E> prev = node.prev;
            Node<E> next = node.next;
            prev.next = next;
            next.prev = prev;

            if (node == first) { // index == 0
                first = next;
            }

            if (node == last) { // index == size - 1
                last = prev;
            }
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == element)
                    return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element))
                    return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据索引找到节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);

        if (index < (size >> 1)) { // 索引小于一半从前往后找
            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() {
        StringBuilder string = new StringBuilder();
        string.append("[size=").append(size).append(", ");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}

双向循环链表解决约瑟夫环问题

在这里插入图片描述

public class Main {
    public static void josephus(){
        CircleLinkedList<Integer> list = new CircleLinkedList<>();
        for(int i = 1; i <= 8; i++){
            list.add(i);
        }
        list.reset(); // current->1
        while(!list.isEmpty()){
            list.next();
            list.next();
            System.out.println(list.remove());
        }
    }
    
    public static void main(String[] args) {
        josephus();
    }
}

如何发挥循环链表的最大威力？

可以考虑增设1个成员变量、3个方法：

  • current ：用于指向某个节点
  • void reset() ：让 current 指向头结点 first
  • E next()：让 current 往后走一步，也就是 current = current.next
  • E remove() ：删除 current 指向的节点，删除成功后让 current 指向下一个节点

在这里插入图片描述

静态链表

前面所学习的链表，是依赖于指针（引用）实现的，有些编程语言是没有指针的，比如早期的 BASIC、FORTRAN 语言，没有指针的情况下，如何实现链表？

  • 可以通过数组来模拟链表，称为静态链表
  • 数组的每个元素存放 2 个数据：值、下个元素的索引
  • 数组 0 位置存放的是头结点信息

在这里插入图片描述

思考：如果数组的每个元素只能存放 1 个数据呢？

  • 那就使用 2 个数组，1 个数组存放索引关系，1 个数组存放值
文章标签：
索引
关键词：
数据结构链表
数据结构循环链表
数据结构双向循环链表
数据结构单向约瑟夫环
链表约瑟夫环
萌宅鹿同学
目录
相关文章
ephemerals__
|
21天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
49 4
肾透侧视攻城狮
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
20 2
肾透侧视攻城狮
|
22天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
26 2
ephemerals__
|
21天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
39 0
起飞的风筝
|
6月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
起飞的风筝
53 0
数据分析螺丝钉
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
数据分析螺丝钉
44 0
数据分析螺丝钉
|
5月前
|
存储 SQL 算法
LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
数据分析螺丝钉
46 2
进朱者赤
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
进朱者赤
56 2
Sessy
|
6月前
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点.
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点
Sessy
53 1
阿旭算法与机器学习
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
阿旭算法与机器学习
29 0