美文网首页
2-数据结构&动态数组

2-数据结构&动态数组

作者: buding_ | 来源:发表于2024-03-18 09:24 被阅读0次
数据结构是计算机存储、组织数据的方式:

线性结构:线性表(数组、链表、栈、队列、哈希表)
树形结构:二叉树(AVL树、红黑树、B树、堆、Tire、哈夫曼树、并查集)
图形结构:临接矩阵、临接表

数组是一种顺序存储的线性表,所有元素的内存地址是连续的
public class ArrayList<E> {
    /**
     * 元素的数量
     */
    private int size;
    /**
     * 所有的元素
     */
    private E[] elements;
    
    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;
    
    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = (E[]) new Object[capaticy];
    }
    
    public ArrayList() {
        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
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加元素到尾部
     * @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
     * @return 原来的元素ֵ
     */
    public E set(int index, E element) {
        rangeCheck(index);
        
        E old = elements[index];
        elements[index] = element;
        return old;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        ensureCapacity(size + 1);
        
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size++;
    }

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

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    /**
     * 保证要有capacity的容量
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        
        System.out.println(oldCapacity + "扩容为" + newCapacity);
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

相关文章

  • ArrayList和LinkList的区别

    ArrayList:是Array的数据结构,Array是动态数组,是对List接口的实现,他是数组队列,相当于动态...

  • 8.LinkedList

    ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。LinkedList不支...

  • 2020-07-16

    1、看完谷粒商城31 2、恋上数据结构之动态数组

  • 浅谈动态数组&数据结构(object-C)

    什么是数据结构? 接下来我们手写一个动态数组 首先动态数组的接口设计如下: 实现代码如下: #import ...

  • Redis源码

    一、Redis数据结构: SDS SDS(动态字符串)包含字符数组buf[],字符数组现有长度len,字符数组分配...

  • 数据结构与算法二(动态数组)

    目录一、什么是数据结构?二、线性表2.1 数组(Array)2.2 动态数组(Dynamic Array)接口设计...

  • ArrayList and LinkedList

    ArrayList and LinkedList ArrayList是实现了基于动态数组的数据结构,LinkedL...

  • ARTS-第二周

    Algorithm 从基础开始手写动态数组 git代码地址 数组定义:数组(Array)是一种线性表数据结构。它用...

  • 链表

    数组和链表的对比 前面提到的动态数组,栈和队列,底层依托的都是静态的数组这节涉及到的链表才是真正的动态数据结构 数...

  • 数据结构-链表

    前面创建的动态数组, 栈和队列底层都是依托于静态数组的,靠resize来解决容量问题.而链表是真正的动态数据结构....

网友评论

      本文标题:2-数据结构&动态数组

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