玩转数据结构（一）封装自己的动态数组

- 日理万妓 2022-05-20 20:44 209阅读 0赞

数组这个数据结构对我们来说都不陌生，所谓数组就是内存中一段连续的存储空间，可以用来存放同一种数据类型。数组可以通过索引快速进行查找，根据索引查找的时间复杂度是O（1）；但是进行删除某一项时，往往要伴随着大量数据的移动操作，因此时间复杂度是O（n）,但是在删除尾部元素时，就不用移动数据，时间复杂度为0（1）。由此可见，数组比较适合做查询。

这节将封装一个自己的数组，并且实现了在空间不够时进行自动的扩容,在空间过大时进行自动缩容。 为了适     用于各种数据类型，因此实现方式采用了泛型。

废话不多说，直接上代码：

public class Array<E> {
        //存储数据
        private E[] data;
        //当前数据中的元素个数
        private int size;
    
        /**
         * 默认的初始容量为10
         */
        public Array() {
            this(10);
        }
    
        /**
         * 用户指定初始容量
         * @param capacity
         */
        public Array(int capacity) {
            data = (E[]) new Object[capacity];
            size = 0;
        }
    
        public int getSize() {
            return size;
        }
    
        public int getCapacity() {
            return data.length;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public boolean isFull() {
            return size == data.length;
        }
    
        //向数组的最后添加元素
        public void addLast(E e) {
            add(size, e);
        }
    
        //向数组最开始的位置添加元素
        public void addFirst(E e) {
            add(0, e);
        }
    
        //向指定位置插入元素
        public void add(int index, E e) {
            if(index < 0 || index > size) {//下标合法性判断
                throw new IllegalArgumentException("index is illegal!");
            }
    
            if(isFull()) {
                //扩容
                resize(2 * data.length);
            }
    
            for(int i = size-1; i >= index; i--) {
                data[i+1] = data[i];
            }
            data[index] = e;
            size++;
        }
    
        //根据索引index取值
        public E get(int index) {
            if(index < 0 || index > size) {
                throw new IllegalArgumentException("index is illegal!");
            }
    
            return data[index];
        }
    
        //获取数组中尾值
        public E getLast() {
            return get(size - 1);
        }
    
        //获取数组中首值
        public E getFirst() {
            return get(0);
        }
    
        //将指定index处的值设置为新值
        public void set(int index, E e) {
            if(index < 0 || index > size) {
                throw new IllegalArgumentException("index is illegal!");
            }
    
            data[index] = e;
        }
    
        //移除首元素
        public E removeFirst() {
            return remove(0);
        }
    
        //移除尾元素
        public E removeLast() {
            return remove(size-1);
        }
    
        //移除指定位置的元素
        public E remove(int index) {
            if(isEmpty()) {
                throw new IllegalArgumentException("Array is Empty！");
            }
    
            if(index < 0 || index > size) {
                throw new IllegalArgumentException("index is illegal!");
            }
    
            if(size == data.length / 4 && data.length / 2 != 0) {
                //缩容
                resize(data.length / 2);
            }
    
            E res = data[index];
    
            for(int i = index + 1; i < size; i++) {
                data[i-1] = data[i];
            }
            size--;
            data[size] = null;//标记为null，等待垃圾回收机制回收
            return res;
        }
    
        //返回指定元素在数组中的索引，要是数据不存在，索引返回-1
        public int find(E e) {
            for(int i = 0; i < size; i++) {
                if(data[i].equals(e)) {
                    return i;
                }
            }
    
            return -1;
        }
    
        //删除指定元素：删除一个
        public boolean removeElement(E e) {
            int index = find(e);
            if(-1 != index) {
                remove(index);
                return true;
            }
    
            return false;
        }
    
        //删除数组中所有e元素
        public boolean removeAllElement(E e) {
            int index;
           while((index = find(e)) != -1) {
               remove(index);
           }
    
           return true;
        }
    
        //判断Array中是否包含某个元素
        public boolean contains(E e) {
            for(int i = 0; i < size; i++) {
                if(data[i].equals(e)) {
                    return true;
                }
            }
    
            return false;
        }
    
        private void resize(int newCapacity) {
            E[] newArray = (E[])new Object[newCapacity];
            for(int i = 0; i < size; i++) {
                newArray[i] = data[i];
            }
    
            data = newArray;
        }
    
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            str.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));
            str.append("[");
            for(int i = 0; i < size; i++) {
                str.append(data[i]);
                if(i != size-1) {
                    str.append(",");
                }
            }
            str.append("]");
    
            return str.toString();
        }
    }

## 测试 ##

Array<Integer> array = new Array<Integer>();
            for (int i = 0; i < 10; i++) {
                array.addLast(i);
            }
            System.out.println(array);
    
            array.addFirst(-1);
            System.out.println(array);
    
            array.addLast(100);
            System.out.println(array);
    
            array.set(1, 52);
            System.out.println(array);
    
            System.out.println(array.get(10));
    
            array.removeFirst();
            System.out.println(array);
    
            array.removeLast();
            System.out.println(array);
    
            array.remove(5);
            System.out.println(array);
    
            array.removeElement(4);
            System.out.println(array);
    
            array.set(0, 7);
            array.removeAllElement(7);
            System.out.println(array);

### 结果 ###

Array: size=10, capacity=10
    [0,1,2,3,4,5,6,7,8,9]
    Array: size=11, capacity=20
    [-1,0,1,2,3,4,5,6,7,8,9]
    Array: size=12, capacity=20
    [-1,0,1,2,3,4,5,6,7,8,9,100]
    Array: size=12, capacity=20
    [-1,52,1,2,3,4,5,6,7,8,9,100]
    9
    Array: size=11, capacity=20
    [52,1,2,3,4,5,6,7,8,9,100]
    Array: size=10, capacity=20
    [52,1,2,3,4,5,6,7,8,9]
    Array: size=9, capacity=20
    [52,1,2,3,4,6,7,8,9]
    Array: size=8, capacity=20
    [52,1,2,3,6,7,8,9]
    Array: size=6, capacity=20
    [1,2,3,6,8,9]

这次换成自定义类型Student来测试，覆盖Student的equals()方法。

public class Student {
        private String name;
        private int score;
    
        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }
    
        public Student() {
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getScore() {
            return score;
        }
    
        public void setScore(int score) {
            this.score = score;
        }
    
        @Override
        public String toString() {
            return String.format("student(name=%s, score=%d)", name, score);
        }
    
        @Override
        public boolean equals(Object obj) {
            if(this == obj) {
                return true;
            }
    
            if(obj instanceof Student) {
                Student stu = (Student)obj;
                if(stu.name.equals(this.name) && stu.score == this.score) {
                    return true;
                }
            }
    
            return false;
        }
    }

### 测试： ###

Array<Student> studentArray = new Array<Student>();
            studentArray.addFirst(new Student("jack", 100));
            studentArray.addFirst(new Student("mick", 87));
            studentArray.addFirst(new Student("lucy", 61));
            studentArray.set(0, new Student("zhangsan", 99));
    
            System.out.println(studentArray.find(new Student("jack", 100)));
    
            System.out.println(studentArray);

### 结果： ###

2
    Array: size=3, capacity=10
    [student(name=zhangsan, score=99),student(name=mick, score=87),student(name=jack, score=100)]