数据结构1-动态数组实现

1.1 动态数组的实现

1.基本属性与方法

private int size;         //元素数量
private E[] elements;     //所有元素
private static final int DEFAULE_CAPATICY = 10;  //默认空间 
private static final int ELEMENT_NOT_FOUND = -1; //元素未找到

public MyArrayList()
public MyArrayList(int capaticy)//有参构造方法

public void clear()//清除所有元素
public int size()//获取元素数量
public boolean isEmpty()//是否为空
public E get(int index)//获取某个位置元素
public E set(int index, E element)//设置index位置的元素 返回原来的元素
public void add(int index, E element)//在index位置插入一个元素
public void add(E element)//添加元素到尾部
public boolean contains(E element)//是否包含某个元素

//类的创建
public class MyArrayList<E>{

}

---

2.构造方法

// 有参构造方法 参数小于默认，就以默认大小为准
public MyArrayList(int capaticy){
    capaticy = (capaticy < DEFAULE_CAPATICY) ? DEFAULE_CAPATICY : capaticy;
    elements = (E[]) new Object[capaticy]; //Object是所有类的父类
}

//无参构造方法，调用有参构造方法
public MyArrayList(){
    this(DEFAULE_CAPATICY);  //注意写法
}

---

3.获取元素数量

public int size(){
    return size;
}

---

4.判断是否为空 size为0 即空

public boolean isEmpty(){
    return size == 0;
}

---

5.清除所有元素

//由于数组还要用所以不能 elements = null;
public void clear(){
    for(int i = 0; i < size; i++) {
        elements[i] = null; //。
    }
    size = 0; //size归零
}

---

6.判断索引是否合法（越界等）

private void rangeChack(int index){
    if(index < 0 || index >= size){
        throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
    }
}

private void rangeCheckForAdd(int index){
    if(index < 0 || index > size){
        throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
    }
}

---

8.数组容量检查

//保证要有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; //指针指向新数组
}

---

9.get 与 set

//获取某个位置元素
public E get(int index){
    rangeCheck(index);      //检查传入的下标是否合法
    return elements[index];
}

//设置index位置的元素 返回原来的元素
public E set(int index, E element){
    rangeCheck(index);
    E old = elements[index];
    elements[index] = element;
    return old;
}

---

10.添加元素

//在index位置插入一个元素(index及其后面的元素往后挪一位)
public void add(int index, E element){
    
    rangeCheckForAdd(index);
    
    //若当前size为4，再加一元素，要保证数组空间至少为5
    //这里判断当前容量够不够用，不够就扩容
    ensureCapacity(size + 1);
    
    //一定是先挪动最后一个元素
    for(int i = size - 1; i >= index; i--){
        elements[i + 1] = elements[i];
    }
    
    elements[index] = element;
    size++;
}

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

---

11.删除元素

//删除index上的元素(把index后面的元素均往前挪一位)
public void remove(int index){
    rangeCheck(index);
    
    for(int i = index + 1; i < size; i++){
        elements[i - 1] = elements[i];
    }
    
    size--; //原数组元素6个，现在只有5个
    
    elements[size] = null; //清除下表为5的 对象的内存
}

---

12.查看元素索引

/* 
 * 不用elements[i] == element（比较的是地址）
 * 不用elements[i].equals(element)，
 * 因为此数组允许null存在，会出现null.equals(element)
 */
public int indexOf(E element){
    if(element == null) {    //要判断参数是否为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;
}

---

13.是否包含某个元素

// 该元素存在下标，则包含
public boolean contains(E element){
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

---

14.重写 toString()

public String toString(){
    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]);
    }
    
    string.append("]");
    return string.toString();
}

---

15.调用举例

public static void main(String[] args) {
		
    MyArrayList<Integer> ints = new MyArrayList<>();
    ints.add(10);
    ints.add(20);
    ints.add(30);
    
    System.out.println(ints.toString());

}

赏

失败是成功之母

支付宝

微信