五种List集合的简单实现

news/2024/6/19 6:07:22 标签: list, 数据结构

五种List集合的简单实现

    • 一、数组形式
    • 二、单向链表形式
    • 三、含哨兵节点的单向链表形式
    • 四、含哨兵节点的双向链表形式
    • 五、含哨兵节点的环形链表形式

本文是对不同形式List集合的增删改查实现，仅是对学习过程进行记录

一、数组形式

关键点：

  1. 有三个成员变量：集合对象array、元素个数size、数组长度capacity
  2. 在扩容时，将旧array中的数据拷贝到新array对象中
  3. 新增先处理add(int index, int data)方法，考虑扩容、后移元素、赋值三个步骤
public class SelfArrayList {
    /**
     * 真实的数据
     */
    private int[] array = {};
    /**
     * 集合真实大小
     */
    private int size = 0;
    /**
     * 集合容量
     */
    private int capacity = 8;

    public void add(int data) {
        initAndGroup();
        add(size, data);
    }

    public void add(int index, int data) {
        initAndGroup();
        // 仅支持将元素添加到当前集合最后位置
        if (index <= size) {
            for (int i = size; i > index; i--) {
                array[i] = array[i - 1];
            }
            array[index] = data;
            size++;
        }
    }

    public int delete() {
        return array[--size];
    }

    public void update(int index, int data) {
        if (index > 0 && index < size) {
            array[index] = data;
        }
    }

    public int get(int index) {
        return array[index];
    }

    public void forEach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }

    private void initAndGroup() {
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }
}

二、单向链表形式

关键点：

  1. 成员变量就一个Node head节点
  2. 主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)，三个方法里面findNode(int index)又是关键
public class SelfLinkList {

    private Node head = null;

    public void addHead(int value) {
        head = new Node(value, head);
    }

    public void addTail(int value) {
        Node tail = findTail();
        // 加入的节点为第一个节点
        if (tail == null) {
            addHead(value);
        } else {
            tail.next = new Node(value, null);
        }
    }

    /**
     * 核心方法 1 of 3
     */
    public void add(int index, int value) {
        if (index <= 0) {
            addHead(value);
            return;
        }
        // 找到对应索引的上一个节点
        Node pre = findNode(index - 1);
        if (pre == null) {
            return;
        }
        pre.next = new Node(value, pre.next);
    }

    public Node deleteFirst() {
        Node deleteNode = head;
        head = head.next;
        return deleteNode;
    }

    /**
     * 核心方法 2 of 3
     */
    public Node delete(int index) {
        Node pre = findNode(index - 1);
        // 删除头节点数据
        if (pre == null) {
            return deleteFirst();
        }
        Node cur = pre.next;
        // 删除末尾不存在数据
        if (cur == null) {
            return null;
        }
        pre.next = cur.next;
        return cur;
    }

    /**
     * 核心方法 3 of 3
     * index 小于0或者大于链表长度 返回null
     */
    public Node findNode(int index) {
        Node temp = head;
        int nodeSize = 0;
        // 循环遍历 找到对应的节点
        while (temp != null) {
            if (index == nodeSize) {
                return temp;
            }
            temp = temp.next;
            nodeSize++;
        }
        return null;
    }

    public void forEach(Consumer<Integer> consumer) {
        Node temp = head;
        while (temp != null) {
            consumer.accept(temp.value);
            temp = temp.next;
        }
    }

    private Node findTail() {
        if (head == null) {
            return head;
        }
        Node tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        return tail;
    }

    @AllArgsConstructor
    public static class Node {
        public int value;
        public Node next;
    }
}

三、含哨兵节点的单向链表形式

关键点：

  1. 自带一个head节点，其目的是为了简化后续的操作流程，避免出现null的场景
  2. 主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)，三个方法里面findNode(int index)又是关键，特别注意哨兵节点和普通参数节点返回下标的差异
public class SelfSentinelLinkList {

    private final SelfSentinelLinkList.Node head = new SelfSentinelLinkList.Node(0, null);

    public void addHead(int value) {
        add(0, value);
    }

    public void addTail(int value) {
        SelfSentinelLinkList.Node tail = findTail();
        tail.next = new SelfSentinelLinkList.Node(value, null);
    }

    /**
     * 核心方法 1 of 3
     */
    public void add(int index, int value) {
        SelfSentinelLinkList.Node pre = findNode(index - 1);
        // 添加元素超过链表长度
        if (pre == null) {
            return;
        }
        pre.next = new SelfSentinelLinkList.Node(value, pre.next);
    }

    public SelfSentinelLinkList.Node deleteFirst() {
        return delete(0);
    }

    /**
     * 核心方法 2 of 3
     */
    public SelfSentinelLinkList.Node delete(int index) {
        SelfSentinelLinkList.Node pre = findNode(Math.max(-1, index - 1));
        // 删除索引下标超过链表长度
        if (pre == null) {
            return null;
        }
        SelfSentinelLinkList.Node deleted = pre.next;
        // 删除索引下标超过链表长度
        if (deleted == null) {
            return null;
        }
        pre.next = deleted.next;
        return deleted;
    }

    /**
     * 核心方法 3 of 3
     * 哨兵节点 index=-1
     * 数据节点 index>=0
     */
    public SelfSentinelLinkList.Node findNode(int index) {
        SelfSentinelLinkList.Node temp = head;
        int nodeSize = -1;
        while (temp != null) {
            if (index == nodeSize) {
                return temp;
            }
            temp = temp.next;
            nodeSize++;
        }
        return null;
    }

    public void forEach(Consumer<Integer> consumer) {
        SelfSentinelLinkList.Node temp = head.next;
        while (temp != null) {
            consumer.accept(temp.value);
            temp = temp.next;
        }
    }

    private SelfSentinelLinkList.Node findTail() {
        SelfSentinelLinkList.Node tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        return tail;
    }

    @AllArgsConstructor
    public static class Node {
        public int value;
        public SelfSentinelLinkList.Node next;
    }
}

四、含哨兵节点的双向链表形式

关键点：

  1. 默认初始化两个节点head、tail，每增加一个数据就new一个Node，并且同时维护前后4条关系链（new Node的时候已经维护了两条），删除同理
  2. 主要是三个关键方法add(int index, int value)、delete(int index)、findNode(int index)，三个方法里面findNode(int index)又是关键
public class SelfSentinelDoublyLinkedList {
    /**
     * 头哨兵
     */
    private final Node head = new Node(null, 0, null);
    /**
     * 尾哨兵
     */
    private final Node tail = new Node(null, 0, null);

    public SelfSentinelDoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    public void addFirst(int value) {
        add(0, value);
    }

    /**
     * 双向链表的特色地方 就是在操作last的时候
     */
    public void addLast(int value) {
        Node last = tail.prev;
        Node added = new Node(last, value, tail);
        last.next = added;
        tail.prev = added;
    }

    /**
     * 新增数据 核心方法 1 of 3
     */
    public void add(int index, int value) {
      	// 找到要插入数据的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            return;
        }
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    public void deleteFirst() {
        delete(0);
    }

    public void deleteLast() {
        Node removed = tail.prev;
        if (removed == head) {
            return;
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    /**
     * 删除数据 核心方法 2 of 3
     */
    public void delete(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            return;
        }
        Node removed = prev.next;
        if (removed == tail) {
            return;
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }

    /**
     * 根据索引查找数据 核心方法 3 of 3
     */
    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void forEach(Consumer<Integer> consumer) {
        Node p = head.next;
        while (p != tail) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    static class Node {
        /**
         * 上一个节点指针
         */
        private Node prev;
        /**
         * 下一个节点指针
         */
        private Node next;
        /**
         * 具体数据
         */
        private final int value;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

五、含哨兵节点的环形链表形式

关键点：

  1. 默认只初始化一个节点sentinel，由于是一个环，所以该节点既可以是头哨兵，也可以是尾哨兵。增加一个数据就new一个Node，并且同时维护前后4条关系链（new Node的时候已经维护了两条）
  2. 在初始化SelfRingLinkedListSentinel这个链表的时候，构建好环的关联关系
  3. 新增、删除数据时，都需要维护好四条关系链
public class SelfRingLinkedListSentinel {
    /**
     * 哨兵节点
     */
    private final Node sentinel = new Node(null, 0, null);

    public SelfRingLinkedListSentinel() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    /**
     * 添加到第一个
     */
    public void addFirst(int value) {
        Node next = sentinel.next;
        Node prev = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }

    /**
     * 添加到最后一个
     */
    public void addLast(int value) {
        Node prev = sentinel.prev;
        Node next = sentinel;
        Node added = new Node(prev, value, next);
        prev.next = added;
        next.prev = added;
    }

    /**
     * 删除第一个
     */
    public void removeFirst() {
        Node removed = sentinel.next;
        if (removed == sentinel) {
            return;
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinel.prev;
        if (removed == sentinel) {
            return;
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值删除节点
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed != null) {
            Node prev = removed.prev;
            Node next = removed.next;
            prev.next = next;
            next.prev = prev;
        }
    }

    /**
     * 遍历找到对应的元素
     */
    private Node findNodeByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public void forEach(Consumer<Integer> consumer) {
        Node p = sentinel.next;
        while (p != sentinel) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    static class Node {
        int value;
        Node prev;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

http://www.niftyadmin.cn/n/5338742.html

相关文章

11 - PXC集群｜MySQL存储引擎

11 - PXC集群｜MySQL存储引擎

PXC集群&#xff5c;MySQL存储引擎 数据库系列文章PXC集群配置集群测试集群 MySQL存储引擎存储引擎介绍mysql服务体系结构mysql服务的工作过程处理查询访问的工作过程处理存储insert访问的工作过程 什么是搜索引擎 存储引擎管理查看存储引擎修改存储引擎 存储引擎特点myisam存储…
阅读更多...
使用Element中的input组件如何实现文字和输入框在一行显示

使用Element中的input组件如何实现文字和输入框在一行显示

利用 <el-form-item label"商品名称&#xff1a;">标签包裹即可&#xff0c;label写提示文字 <el-form ref"form" label-width"100px"><el-form-item label"商品名称&#xff1a;"><el-input v-model"na…
阅读更多...
计量属性和会计报表

计量属性和会计报表

目录 历史成本计价基础的优点重置成本计价可变现净值计价现值公允价值会计报表 \quad \quad 会计要素的计量属性简单的来说就是用什么样的方法来进行计量。 \quad \quad 历史成本计价基础的优点 (比如用发票) 1、数据客观 2、随时可以查证 3、防止随意更改 4、核算手续简化 历…
阅读更多...
vxe-table 单元格数字的精度切换、单元格内容宽度自适应（根据内容撑开）

vxe-table 单元格数字的精度切换、单元格内容宽度自适应（根据内容撑开）

数字的精度切换、单元格内容宽度自适应 1、支持切换数字的精度2、单元格内容自适应&#xff0c;根据内容撑开 1、支持切换数字的精度 // 1.表格绑定myAmount 格式化函数 <vxe-button size"mini" content"精度" icon"vxe-icon--warning" clas…
阅读更多...
Chat2DB：AI赋能的多数据库客户端工具，开源领航未来数据库管理

Chat2DB：AI赋能的多数据库客户端工具，开源领航未来数据库管理

Chat2DB&#xff1a;开源多数据库客户端的AI革新 Chat2DB使用教程:Chat2DB使用教程_哔哩哔哩_bilibili 引言&#xff1a; 随着企业数据的快速膨胀&#xff0c;数据库管理的复杂性也在增加。此时&#xff0c;一个能够跨越数据库边界、并且集成先进的AI功能的工具&#xff0c;不…
阅读更多...
UI测试脚本录制器已上线，RunnerGo ：UI自动化测试平台

UI测试脚本录制器已上线，RunnerGo ：UI自动化测试平台

想快速配置可视化UI自动化测试脚本&#xff1f;RunnerGo近期上线脚本录制器&#xff0c;根据你的测试操作直接生成UI自动化测试脚本&#xff0c;下面是使用方法 Step1:下载录制器 点击RunnerGo上方插件按钮下载录制器 Step2:录制器使用 将插件文件拖入浏览器扩展程序 点击打…
阅读更多...
Android学习之路(22) 从模块化到组件化

Android学习之路(22) 从模块化到组件化

从模块化到组件化 一、从模块化到组件化 Android 应用项目 , 都存在一个应用模块 ( Application Module ) , 在 build.gradle 构建脚本中 , 第一个插件配置 com.android.application , 表明 该 Module 编译打包后的输出是 APK 安装包 ; 该项目可以直接运行 ; plugins {id co…
阅读更多...
【数据结构】非递归实现快速排序与归并排序

【数据结构】非递归实现快速排序与归并排序

递归是可以向非递归进行变化的&#xff1a; 比如很经典的斐波那契数列可以用递归实现也可以用循环实现 但是有些复杂的递归仅仅依靠循环是很难控制的&#xff0c; 所以我们需要借助数据结构中的栈与队列帮助我们用非递归模拟递归&#xff0c; 故有的时候我们说非递归不是递归却…
阅读更多...
最新文章

Copyright @ 2022~2023