表 | Eric笔记 | Eric笔记

1.数组

特点：

在内存中，数组是一块连续的区域。

数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。

插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。

随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。

并且不利于扩展，数组定义的空间不够时要重新定义数组。

优点：

随机访问性强
查找速度快

缺点：

插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展

2.链表

特点：

在内存中可以存在任何地方，不要求连续。

每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。

增加数据和删除数据很容易。再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。

查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起。

不指定大小，扩展方便。链表大小不用定义，数据随意增删。

优点：

插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。

缺点：

不能随机查找，必须从第一个开始遍历，查找效率低

Java Collections 表

Collections实现了Iterator（迭代器）接口，并且提供了remove、next、hasNext方法。

Interator的remove方法可以删除由next最新返回的项，相比较Collections中的remove方法，Iterator中的remove有很多的优点。但是有一点，当我们对正在被迭代的集合进行结构上的改变时(add、remove、clear)等操作，那么迭代器就不再合法（此后我们再使用该迭代器将会有ConcurrentModificationException异常）。

List接口继承了Collection接口，并且有两种实现方式

ArrayList：提供了List ADT 的一种可增长数组的实现。它的优缺点同上面的数组。

LinkedList：提供了List ADT双链表的实现（每一个节点除了持有指向后继节点的链，还有一个指向前驱节点的链），它的优缺点同以上的了链表。

以下是自定义类似ArrayList的实现：

public class MyArrayList<AnyType> implements Iterable<AnyType> {

    public static final int default_size = 10;

    private int theSize;
    private AnyType[] theItems;

    public MyArrayList() {
        doClear();
    }

    public void clear() {
        doClear();
    }


    public int size() {
        return theSize;
    }

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


    public void trimToSize() {
        ensureCapacity(size());
    }

    public AnyType get(int idx) {
        if (idx < 0 || idx >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return theItems[idx];
    }

    public AnyType set(int idx, AnyType newVal) {
        if (idx < 0 || idx >= size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    public void add(int idx, AnyType x) {
        //扩展数组
        if (theItems.length == size()) {
            ensureCapacity(size() * 2 + 1);
        }
        //插入时整体移动
        for (int i = theSize; i > idx; i--) {
            theItems[i] = theItems[i - 1];
        }
        theItems[idx] = x;
    }

    public AnyType remove(int idx) {
        AnyType removedItem = theItems[idx];
        for (int i = idx; i < size() - 1; i++) {
            theItems[i] = theItems[i + 1];
        }
        theSize--;
        return removedItem;
    }

    private void doClear() {
        theSize = 0;
        ensureCapacity(default_size);
    }

    public void ensureCapacity(int newCapacity) {
        if (newCapacity < theSize) {
            return;
        }
        AnyType[] old = theItems;
        theItems = (AnyType[]) new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            theItems[i] = old[i];
        }
    }

    public Iterator<AnyType> iterator() {
        return new ArrayListIterator<AnyType>(this);
    }


    private static class ArrayListIterator<AnyType> implements Iterator<AnyType> {
        private int current = 0;
        private MyArrayList<AnyType> theList;

        public ArrayListIterator(MyArrayList<AnyType> list) {
            theList = list;
        }

        @Override
        public boolean hasNext() {
            return current < theList.size();
        }

        @Override
        public AnyType next() {
            return theList.theItems[current++];
        }
    }

}

赏

本文地址： http://www.yppcat.top/2019/03/25/表/

@Eric笔记

表

2019-03-25

谢谢老板~