美文网首页
02_动态数组

02_动态数组

作者: 伶俐ll | 来源:发表于2020-09-14 09:47 被阅读0次
    什么是数据结构？

    数据结构是计算机存储、组织数据的方式


    Snip20200914_5.png

    数组

    数组是一种顺序存储的线性表，所有元素的内存地址是连续的

    数组的接口设计

    • int size(){} // 元素的数量
    • boolean isEmpty(){} // 是否为空
    • void add(E element){} // 添加元素到最后面
    • void set(int index,E element){} // 设置index位置的元素
    • void add(int index,E element){} // 在index位置插入一个元素
    • void remove(int index){} // 删除index位置的元素
    • boolean contains(E element){} // 是否包含某个元素
    • E get(int index){} // 获取index位置的元素
    • int indexOf(E element){} // 查看元素的索引
    • void clear(){} // 清除所有元素

    动态数组的缩容

    • 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
    • 比如剩余空间占总容量一半时，就进行缩容
    • 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡
      比如，扩容倍数设置为原来容量的2倍，而缩容时机设置为当元素个数小于等于原容量1/2时
    • 注意点：扩容倍数 和 缩容时机 不要相乘等于1

    代码实现

    • 普通的动态数组
    package ListArray;

public class LZArrayList <E>{

    /**
     * 元素的数量
     */
    private  int size;

    /**
     * 所有的元素
     */
    private  E[] elements;

    /**
     * 数组的初始容量
     */
    private  static final int DEFAULT_CAPACITY = 10;

    /**
     * 元素找不到
     */
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 构造函数
     */
    public LZArrayList(int capaticy){
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
        elements = (E[]) new Object[capaticy];
    }

    /**
     * 构造函数
     */
    public LZArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[i] = null;
        }
        size = 0;
    }

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

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }


    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        elements[index] = element;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //扩容
        ensureCapacity();

        //插入数据
        for (int i = size;i>index;i--){
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);
        for (int i = index+1;i<size;i++){
            elements[i-1] = elements[i];
        }
        elements[--size] = null;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        if (element == null){
            for (int i = 0;i<size;i++){
                if (elements[i] == null) return i;
            }
        }
        for (int i = 0;i<size;i++){
            if (element.equals(elements[i])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 动态扩容
     * 当数组的容量小于size + 1 时，扩容到原来容量的 1.5 倍
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        if (elements.length >= size + 1) return;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i<size;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}
    • 环形动态数组 - 自动缩容
    package ListArray;

public class LZCircleArrayList <E>{

    /**
     * 元素的数量
     */
    private  int size;

    /**
     * 所有的元素
     */
    private  E[] elements;

    /**
     * 第一个元素的下标
     */
    private int front;

    private  static final int DEFAULT_CAPACITY = 10;
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 构造函数
     */
    public LZCircleArrayList(int capaticy){
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
        elements = (E[]) new Object[capaticy];
    }

    /**
     * 构造函数
     */
    public LZCircleArrayList(){
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[realIndex(i)] = null;
        }
        front = 0;
        size = 0;
        shrinkageCapacity();
    }

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

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }


    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return elements[realIndex(index)];
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        elements[realIndex(index)] = element;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //扩容
        ensureCapacity();

        //插入数据
        if (index>=(size>>1)){ //插入位置更接近数组尾部
            for (int i = size;i>index;i--){
                elements[realIndex(i)] = elements[realIndex(i - 1)];
            }
            elements[realIndex(index)] = element;
        }else { //插入位置更接近数组头部
            for (int i = -1;i<index;i++){
                elements[realIndex(i)] = elements[realIndex(i + 1)];
            }
            elements[realIndex(index)] = element;
            front = realIndex(-1);
        }
        size++;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);

        //删除数据
        if (index>=(size>>1)){ //删除位置更接近数组尾部
            for (int i = index+1;i<size;i++){
                elements[realIndex(i-1)] = elements[realIndex(i)];
            }
            elements[realIndex(size-1)] = null;
        }else { //删除位置更接近数组头部
            for (int i = index;i>0;i--){
                elements[realIndex(i)] = elements[realIndex(i - 1)];
            }
            elements[realIndex(0)] = null;
            front = realIndex(1);
        }
        size--;
        //缩容
        shrinkageCapacity();
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        if (element == null){
            for (int i = 0;i<size;i++){
                if (elements[realIndex(i)] == null) return i;
            }
        }
        for (int i = 0;i<size;i++){
            if (element.equals(elements[realIndex(i)])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据index求出真实索引
     * @param index
     * @return
     */
    private int realIndex(int index){
        index += front;
        if (index<0){
            return index + elements.length;
        }
        return index - (index>= elements.length?elements.length:0);
//        return (front + index) % elements.length;
    }

    /**
     * 动态扩容
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        //不需要扩容
        if (elements.length >= size + 1) return;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[realIndex(i)];
        }
        elements = newElements;
        front = 0;
    }

    /**
     * 动态缩容
     * 当元素个数小于数组容量的一半，并且大于默认初始容量时，进行缩容
     * 如果数组中没有元素或者数组容量小于初始容量的2倍，缩容为初始容量，否则缩容为容量的1/2
     */
    private void shrinkageCapacity(){
        int oldCapacity = elements.length;

        //不需要缩容
        if (size>=(oldCapacity>>1) || oldCapacity<=DEFAULT_CAPACITY) return;

        int newCapacity = (oldCapacity < DEFAULT_CAPACITY + DEFAULT_CAPACITY || size == 0)?DEFAULT_CAPACITY:(oldCapacity>>1);

        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[realIndex(i)];
        }
        elements = newElements;
        front = 0;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("front = ").append(front).append("\n");
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i<elements.length;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

}

    时间复杂度分析

    • 添加
      最好：O(1) 最坏：O(n) 平均：O(n)
    • 添加元素到结尾
      最好：O(1) 最坏：O(1) 平均：O(1) 均摊：O(1)
    • 删除
      最好：O(1) 最坏：O(n) 平均：O(n)
    • 设置index位置的值
      最好：O(1) 最坏：O(1) 平均：O(1)
    • 获取inde位置的值
      最好：O(1) 最坏：O(1) 平均：O(1)

    相关文章

      网友评论

          本文标题：02_动态数组

          本文链接：https://www.haomeiwen.com/subject/gmpaektx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|02_动态数组|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！