美文网首页
动态数组ArrayList

动态数组ArrayList

作者: 曹来东 | 来源:发表于2019-05-09 09:45 被阅读0次

删除数组指定位置元素实现

[1,2,3,4,5,6]
删除index位置的元素的实质:index位置之后的所有元素都向前移动.最终实现为: 遍历数组将要删除位置的元素赋值为后一个元素的值.

/*
删除数组指定位置的元素
size: 当前数组长度
arr: 当前数组
*/public int remove(int index){
    if (index < 0 || index >= arr.length) {
        return "数组越界";
    }
        for (int i = index;i < arr.length ;i++ ) {
            arr[index] = arr[index + 1];
        }
             size--;
}

在数组指定位置添加元素

可能需要数组扩容.
容量够用的情况.

/**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
//检查边界
        rangeCheckForAdd(index);
 //检查容量 是否需要扩容
        ensureCapacity(size + 1);
        
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        size++;
    }

ArrayList类设计

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;
    //capaticy容量
    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; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        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; 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);
        }
    }
    
    @Override
    public String toString() {
        // size=3, [99, 88, 77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            
            string.append(elements[i]);
            
//          if (i != size - 1) {
//              string.append(", ");
//          }
        }
        string.append("]");
        return string.toString();
    }
}

相关文章

  • 关于ArrayList

    ArrayList简介 ArrayList内部是以动态数组存放数据的,所谓动态数组,不是数组本身可以改变长度,而是...

  • ArrayList 与 LinkedList 列表结构分析

    ArrayList ArrayList 内部维护了一个动态的Object 数组,ArrayList 的动态增删就是...

  • ArrayList源码解析

    ArrayList简介 ArrayList底层是数组队列,相当于动态数组。与java中的数组相比,它的长度能动态增...

  • ArrayList学习笔记

    ArrayList--动态数组 ArrayList介绍: 从源码分析: 遍历方式:

  • Java数据结构(2)ArrayList

    ArrayList ArrayList 是一个数组队列,相当于 动态数组,与数组相比,它的容量能动态增长。 和Ve...

  • Java集合——ArrayList

    简介ArrayList实际上是动态数组,它提供动态增删元素的方法,数组大小可以灵活设置,但是ArrayList不是...

  • ArrayList的使用及ConcurrentModificat

    ArrayList是一种动态数组,可以动态的增加或删除元素。ArrayList和Vector都是用数组实现的,但二...

  • Java主要数据结构总结

    数组线性表类ArrayList 和链表类LinkedList ArrayList用数组存储元素,这个数组是动态创建...

  • Java基础day08ArrayList和继承

    ArrayList 类 对象数组 数组长度是固定, 无动态扩容 java.util.ArrayList 集合类,更...

  • java基础—浅析ArrayList源码

    ArrayList简介 ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态...

网友评论

      本文标题:动态数组ArrayList

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