基本数据结构底层原理和总结

作者: Raral | 来源:发表于2021-12-21 15:28 被阅读0次

基本数据结构底层原理和总结
Lucene学习图解
2022年iOS面试题2
iOS底层原理总结 - 关联对象实现原理
iOS底层原理总结 - Category的本质
HashMap的技术细节
iOS底层原理总结 - 探寻block的本质（一）
建立你自己的iOS开发知识体系
探寻block的本质
Runtime 机制

基本数据结构解析

逻辑结构分为：集合，线性，树，图。存储结构分为：线性存储，链式存储，索引存储，has存储。

数组(线性)

概述

数组是最常见的一种数据结构，它是相同类型的用一个标识符封装到一起的基本类型数据序列或者对象序列。数组使用一个统一的数组名和不同的下标来唯一确定数组中的元素。实质上，数组是一个简单的线性序列，因此访问速度很快。

场景：频繁查询，对存储空间要求不大，很少增加和删除的情况。

在计算机语言中数组是非常重要的集合类型，大部分计算机语言中数组具有如下三个基本特性：

一致性：数组只能保存相同数据类型元素，元素的数据类型可以是任何相同的数据类型。
有序性：数组中的元素是有序的，通过下标访问。
不可变性：数组一旦初始化，则长度（数组中元素的个数）不可变。

优点：

1：可以表示一组数据。

2：数组根据下标访问元素的效率非常快（数组元素连续分配内存的）。

缺点：

1：数组中的元素的类型必须一致。

2：数组是定长的，不能自动扩容。

3：数组的元素因为必须要连续分配，那么对连续的内存要求更严苛一点点。

4：数组根据内容查找元素效率比较低。需要逐个比较。

5：插入元素和删除元素的效率比较低，因为可能要移动大量的元素。

6：数组没有封装。数组只有一个长度的属性，没有提供操作元素的方法。所有对元素的操作都必须自己写方法实现。

实现数组底层

[图片上传失败...(image-737b-1640071641204)]


public class MyArray {
    private int[] data;//存放数据的容器
    private int size;//有数据的长度

    public MyArray() {
        this(10);
    }

    //capacity容量，相当于几个连续的空桶
    public MyArray(int capacity) {
        data = new int[capacity];
        size = 0;//因为都是空桶
    }

    //获取有水的桶连续个数
    public int getSize() {
        return size;
    }

    //获取连续空桶的个数
    public int getCapacity() {
        return data.length;
    }

//    add,remove,set,get


    //1. 由于数组要求存放的内存位置需要连续，我们要把i插入到i-1的位置，i以后的每个元素都要后移一个单位。
    //index: 索引     e:元素
    public void add(int index, int e) {
        //校验数组的容量是否满
        if(size == data.length) {
            throw new IllegalArgumentException("add failed cause by array is fulled");
        }
        //校验数组越界
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("add failed cause by array out of bounds");
        }
        //核心操作：1. 先把i后面每个元素后移一个桶。 2 把空出来的桶装满e 3. 装满水的桶个数加一
        for(int i = size - 1; i >= index; i -- ) {
              data[i + 1] = data[i];//把原理元素 赋值到 后面桶子里
        }

        data[index] = e; //把中间空出来的桶装满
        size ++; //装满水的桶个数加一
    }

    //如果没有传入 索引，默认依次插入
    public void add(int e) {
        //校验数组的容量是否满
        if(size == data.length) {
            throw new IllegalArgumentException("add failed cause by array is fulled");
        }
        data[size] = e;
        size ++;
    }



    //2.根据索引删除当前元素，返回删除的元素
    //原理和add操作流程刚好相反，把删除的桶的后面的每个有水的桶前移一个单位。
    //index 索引
    public int remove(int index) {
        //校验数组越界
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("remove failed cause by array out of bounds");
        }
        int ret = data[index];
        for(int i = index + 1; i < size; i ++) {
            data[i - 1] = data[i];
        }
        size --;
        return ret;
    }



    //3. 获取对应索引的桶的元素
    public int get(int index) {
        //校验数组越界
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("get failed cause by array out of bounds");
        }
        return data[index];
    }

    //4. 设置对应索引的桶的元素
    public void set(int index, int e) {
        //校验数组越界
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("set failed cause by array out of bounds");
        }

        data[index] = e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size=%d , capacity=%d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1) {
                res.append(",");
            }
        }
        res.append(']');
        return res.toString();
    }

}




public class Test {

    public static void main(String[] args) {
//        int[] ints = new int[11];

        MyArray myArray = new MyArray();
        myArray.add(99);
        myArray.add(98);
        myArray.add(0, 97);
        System.out.println(myArray);

        myArray.remove(0);
        System.out.println(myArray);

        int i = myArray.get(0);
        System.out.println(i);

        myArray.set(1, 10000);
        System.out.println(myArray);

        /**
         * 打印：
         *       Array: size=3 , capacity=10
                 [97,99,98]
                 Array: size=2 , capacity=10
                 [99,98]
                 99
                 Array: size=2 , capacity=10
                 [99,10000]
         *
         * */

    }
}

栈 stack（线性，底层数组）

栈的特点

先进后出（FILO）或者后进先出（LIFO）
增删元素皆是在栈顶操作
一次只能删除一个数据项：当前栈顶元素
只允许访问一个数据项：当前栈顶元素

所需元素

因为底层用数组实现，所以需要一个数组 stackArray
需要一个指向栈顶的指针top
需要指定数组的大小maxSize

场景：栈常应用于实现递归功能方面的场景，例如斐波那契数列

分析实现

需要在创建自定义栈类的时候，就确定好一些初始化操作，例如确定数组的大小并初始化数组；
确定栈具有的功能：入栈push()、出栈pop()、查看栈顶元素getTop()、判空isEmpty()、判满isFull()、判长length()、清空clear()

[图片上传失败...(image-362210-1640071641204)]

/**
 * 需要在创建自定义栈类的时候，就确定好一些初始化操作，例如确定数组的大小并初始化数组；
 确定栈具有的功能：入栈push()、出栈pop()、查看栈顶元素getTop()、判空isEmpty()、判满isFull()、判长length()、清空clear()
 * */
public class MyStack {
    private int top;//指针
    private int capacity;//栈容量
    private Object[] stackArr;//栈 数组

    public MyStack(int capacity) {
        this.capacity = capacity;
        stackArr = new Object[capacity];
        top = -1;

        System.out.println("初始化：capacity:" + capacity + "\t top:" + top);
    }

//    public MyStack() {//默认容量10
//        this(5);
//    }

    //入栈：把进入的元素压进到栈地（索引0）；将指针移动到top = 0;
    public void push(Object o) {
        //校验栈容量是否已满
        if(top == this.capacity) {
            throw new IllegalArgumentException("push failed cause by stack is fulled");
        }
        stackArr[++ top] = o;//先执行，再加加
    }

    //出栈：把栈顶最外层元素，弹出并且返回；
    public Object pop() {
        Object o = stackArr[--top];//先执行，再减减
        return o;
    }

    //查看栈顶元素：
    public Object getTop(){
        return stackArr[top];
    }

    //查看当前栈的长度
    public int length() {
        return top + 1;
    }

    //清空栈元素：
    public void clear() {
        while (top != -1) {
            pop();
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size=%d , capacity=%d\n", top + 1, stackArr.length));
        res.append('[');
        for (int i = 0; i <  top + 1; i++) {
            res.append(stackArr[i]);
            if (i != top + 1 - 1) {
                res.append(",");
            }
        }
        res.append(']');
        return res.toString();
    }

}


public class Test {
    public static void main(String[] args) {
//        MyStack myStack = new MyStack();
//        int i = 5;
//        tes(++ i );
//        System.out.println(i);
        MyStack myStack = new MyStack(5);
        myStack.push(new Object());
        myStack.push(new Object());
        System.out.println(myStack);

        myStack.pop();
        System.out.println(myStack);


        /**
         * 打印：
         *      初始化：capacity:5   top:-1
                Array: size=2 , capacity=5
                [java.lang.Object@63947c6b,java.lang.Object@2b193f2d]
                Array: size=1 , capacity=5
                [java.lang.Object@63947c6b]
         * */
    }

    public static void   tes(int i) {
        System.out.println(i);
    }
}

队列 queue(线性，底层数组)

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：

代码实现

package com.kuang.demo12_data_structure.data03_queue;

/**
 * @description:
 * @author: li
 */
public class MyQueue {
    private int[] data;//队列存放的数据
    private int capacity;//队列容量
    private int front;//队列头部的指针
    private int rear;//队列尾部的指针

    //构造函数
    public MyQueue(int capacity) {
        data = new int[capacity];
        this.capacity = capacity;
        front = -1;
        rear = -1;
    }

    //判断队列数据是否满
    public boolean isFull() {
        return rear == capacity - 1;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    //添加数据队列（头部添加）
    public void add(int n) {
        if(isFull()) {
            throw new IllegalArgumentException("add failed cause by queue is fulled");
        }
        data[++ rear] = n;
    }

    //读取头部数据
    public int getHead() {
        if(isEmpty()) {
            throw new IllegalArgumentException("getHead failed cause by queue is empty");
        }
        return data[front + 1];
    }

    //取出头部数据（删除数组第一个元素）
    public int shift() {
        if(isEmpty()) {
            throw new IllegalArgumentException("getHead failed cause by queue is empty");
        }
        int value = data[++ front];
        data[front] = 0;
        return value;
    }

    //取出尾部数据（删除数组最后一个元素）
//    public int pop() {
//        if(isEmpty()) {
//            throw new IllegalArgumentException("getHead failed cause by queue is empty");
//        }
//        int value = data[rear --];
//        data[rear]
//
//    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size=%d , capacity=%d\n", rear + 1, data.length));
        res.append('[');
        for (int i = 0; i <  rear + 1; i++) {
            res.append(data[i]);
            if (i != rear + 1 - 1) {
                res.append(",");
            }
        }
        res.append(']');
        return res.toString();
    }


    
}

//测试
public class Test {

    public static void main(String[] args) {
//        int a = 1000;
//        for(int i = 0; i <=100; i ++) {
//            System.out.println(i % 3);
//        }
        MyQueue myQueue = new MyQueue(6);
        myQueue.add(20);
        myQueue.add(21);

        int head = myQueue.getHead();
        System.out.println("读取：" + head);

        int pop = myQueue.shift();
        System.out.println("取出：" + pop);

        System.out.println(myQueue);
    }
}

链表linkTable(Node)

概述
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

链表的优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

链表就是一对一的结构，具有一对一的特性的都称之为线性结构。

你后边的疑问根本就是一个错误的问题。

你的疑问是你把逻辑结构与存储结构弄混淆了。

逻辑结构分为：集合，线性，树，图。

存储结构分为：线性存储，链式存储，索引存储，has存储。

逻辑结构与存储结构两个之间的关系是：逻辑结构只是一种定义，并没有在计算机内部实现。存储结构是在计算机内部存入的形式。而且，逻辑结构可以用不同的存储结构在计算机内部进行存储。比如：线性表是一种抽象的定义，没有在计算机内部进行存储。但是我们把线性表存入计算机的时候，可以使用数组实现线性存储，也可以使用链表实现链式存储。

代码实现


public class MyLink<E> {


    //定义一个节点 存储 数据和指针
    private class Node {
        private E e;
        private Node next;
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }


    //链表相关的信息
    private Node head;
    private int size;


    public MyLink() {
        head = new Node();
        size = 0;
    }

    //获取链表的大小
    public int getSize() {
        return size;
    }
    //返回链表是空
    public boolean isEmpty() {
        return size == 0;
    }

    //链表新增：通过索引新增到指定的位置 （递归思想）
    public void add(int index, E e) {
        //校验索引越界
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("add failed cause by data out of rounds");
        }
        Node prev = head;//获取第一个节点的上一个节点
        for(int i = 0; i < index; i ++) {
            prev = prev.next;
        }
        Node curNode = prev.next;//获取当前节点
        prev.next = new Node(e, curNode);//把当前节点的上一个节点 指向 新插入的节点信息
//        prev.next = new Node(e, prev.next);
        size ++;
    }

    //链表查询:从头节点向下依次查找
    public E get(int index) {
        //校验索引越界
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("add failed cause by data out of rounds");
        }
        //先找到第一个（没有存储数据，只有一个指针）
        Node cur = head.next;
        for(int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }
    public Node get2(int index) {
        //校验索引越界
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("add failed cause by data out of rounds");
        }
        //先找到第一个（没有存储数据，只有一个指针）
        Node cur = head.next;
        for(int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //链表删除：
    public E remove(int index) {
        //校验索引越界
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("add failed cause by data out of rounds");
        }
        //获取第一个节点的上一个节点
        Node prev = head;
        for(int i = 0; i < index; i ++) {
            prev = prev.next;
        }

        Node curNode = prev.next;//获取当前索引的节点信息
        prev.next = curNode.next;//把当前上一个节点的next指向 当前下一个节点
        curNode.next = null; //然后把当前节点next null
        size --;

        return curNode.e;
    }


    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LinkTable: size=%d , capacity=%d\n", size, null));
        res.append('[');
        for (int i = 0; i <  size; i++) {
            res.append('{');
//                res.append(data[i]);
//                if (i != rear + 1 - 1) {
//                    res.append(",");
//                }
            res.append('}');
        }
        res.append(']');
        return res.toString();
    }





}


//测试类
public class Test {
    public static void main(String[] args) {
        Map<Integer, Boolean> map = new HashMap<>();
        map.put(1,true);
        map.put(1,true);
        map.put(2,true);
//        System.out.println(map);//{1=true, 2=true}
        MyLink<String> linkTable = new MyLink<>();
        linkTable.add(0, "A");
        linkTable.add(1, "B");
        linkTable.add(2, "C");
//        System.out.println(linkTable);
//        String s = linkTable.get(0);
//        System.out.println(s);
        System.out.println("链表插入-----");
        linkTable.add(1,"dddd");
        System.out.println(linkTable);
        System.out.println("链表查询-----");
        System.out.println(linkTable.get(0));
        System.out.println(linkTable.get(1));
        System.out.println(linkTable.get(2));
        System.out.println(linkTable.get(3));
        System.out.println(linkTable.get2(1));

        System.out.println("链表删除-----");
        String remove = linkTable.remove(1);
        System.out.println(remove);
        System.out.println(linkTable);

    }
}

树（Tree ）

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树

[图片上传失败...(image-e01759-1640071641204)]

二叉树是树的特殊一种，具有如下特点：(提取数组和链表的优点)

每个结点最多有两颗子树，结点的度最大为2。
左子树和右子树是有顺序的，次序不能颠倒。
即使某结点只有一个子树，也要区分左右子树。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

扩展：
二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。

代码实现

/**
为什么实用二叉树
         一,在有序数组中插入删除数据太慢
         1插入或者删除一条数据会移动后面的所有数据
         二,在链表中查找数据太慢
         2查找只能从头或者尾部一条一条的找
         用树解决问题
         有没有一种插入和删除像链表那么快，查询可以向有序数组一样查得快那样就好了。
         数实现了这些特点，称为了最有意思的数据结构之一
         树的术语
*/

public class Node {
    int key;
    Object value;
    Node leftChildNode;
    Node rightChildNode;

    public Node(int key, Object value) {
        super();
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", value=" + value +
                ", leftChildNode=" + leftChildNode +
                ", rightChildNode=" + rightChildNode +
                '}';
    }
}





public class MyTree {
    private Node root;

    public MyTree() {
    }

    public MyTree(Node root) {
        this.root = root;
    }

    //查找节点
    public Node find(int key) {
        if(this.root != null) {
            Node currentNode = this.root;
            while (currentNode.key != key) {
                if(key > currentNode.key) {//右边
                    currentNode = currentNode.rightChildNode;
                }else {//左边
                    currentNode = currentNode.leftChildNode;
                }
                if(currentNode == null) {
                    return null;
                }
            }
        }
        return null;
    }

    //插入节点
    public void insert(int key, Object value) {
        Node node = new Node(key, value);
        if(this.root == null) {
            this.root = node;
        }else {
            Node currentNode = this.root;
            while (true) {
                if(key > currentNode.key) {
                    if(currentNode.rightChildNode == null) {
                        currentNode.rightChildNode = node;
                    }else {
                        currentNode = currentNode.rightChildNode;
                    }
                }else {
                    if(currentNode.leftChildNode == null) {
                        currentNode.leftChildNode = node;
                    }else {
                        currentNode = currentNode.leftChildNode;
                    }
                }
            }
        }

    }
}




public class Test {
    public static void main(String[] args) {
        Node root = new Node(50, 24);
        MyTree tree = new MyTree(root);
        tree.insert(20, 530);
        tree.insert(540, 520);
        tree.insert(4, 540);
        tree.insert(0, 550);
        tree.insert(8, 520);
//        System.out.println();
        Node node = tree.find(0);
        System.out.println(node.value);


    }
    /**
     * 为什么实用二叉树
         一,在有序数组中插入删除数据太慢
         1插入或者删除一条数据会移动后面的所有数据
         二,在链表中查找数据太慢
         2查找只能从头或者尾部一条一条的找
         用树解决问题
         有没有一种插入和删除像链表那么快，查询可以向有序数组一样查得快那样就好了。
         数实现了这些特点，称为了最有意思的数据结构之一
         树的术语
     *
     *
     * */
}