[数据结构与算法]JAVA的集合框架03——List的实现类ArrayList、Vector、LinkedList

ArrayList:

• 数组结构实现，查询快。增删慢
• jdk1.2、运行效率快，线程不安全

Vector:(使用较少）

• 数组结构实现，查询快。增删慢
• jdk1.0、运行效率慢，线程安全

LinkedList:

• 链表结构实现，增删快，查询慢

源码分析

ArrayList:

• ? ? ? ? ? ? ? （添加元素之后默认容量DEFAUL_CAPACITY = 10，没添加之前默认是0）
• ????????????????elementData：存放元素的数组
• ????????????????size:实际的元素个数
• ????????????????add(）添加元素
• ? ? ? ? ????????扩容每次都是原来的1.5倍，源码中是+ old>>1位运算

ArrayList和LinkedList区别

• ArraryList:数组结构实现，必须开辟连续的空间，查询快，增删慢，
• LinkesList:链表结构实现，无需开辟连续的空间，查询慢，增删快

public class TestArrayList {
    public static void main(String[] args) {
        //数组存储，有序，由下标，查找快，增删慢
        ArrayList arrayList = new ArrayList();
        //添加
        Student s1 = new Student("aaa", 19);
        Student s2 = new Student("bbb", 20);
        Student s3 = new Student("ccc", 21);
        arrayList.add(s1);
        arrayList.add(s1);
        arrayList.add(s2);
        arrayList.add(s3);
        System.out.println(arrayList.toString());
        //删除
        arrayList.remove(new Student("aaa", 19)); //通过重写equals实现
        System.out.println(arrayList.toString());
        //遍历
        //1.增强for
        //2.interator
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //3.listIterator
        ListIterator listIterator = arrayList.listIterator();
        while (listIterator.hasNext()){
            System.out.println(listIterator.next());
        }
        while (listIterator.hasPrevious()){
            System.out.println(listIterator.previous());
        }
        //判断
        System.out.println(arrayList.contains(s1));
        //查找
        System.out.println(arrayList.indexOf(s2));
    }
}

public class TestVector {
    public static void main(String[] args) {
        Vector vector = new Vector();
        vector.add("aaa");
        vector.add("aaa");
        vector.add("bbb");
        vector.add("ccc");
        System.out.println(vector.size());
        System.out.println(vector.toString());
        vector.remove(0);
        for (Object o:
             vector) {
            System.out.println(o);
        }
        //使用枚举器
        Enumeration elements = vector.elements();
        while (elements.hasMoreElements()){
            System.out.println(elements.nextElement());
        }
        System.out.println(vector.contains("aaa"));
        System.out.println(vector.isEmpty());

        System.out.println(vector.firstElement());  //第一个元素
        System.out.println(vector.lastElement());   //最后一个元素
    }
}

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<Object> objects = new LinkedList<>();
        Student s1 = new Student("aaa", 20);
        Student s2 = new Student("bbb", 21);
        Student s3 = new Student("ccc", 22);
        objects.add(s1);
        objects.add(s2);
        objects.add(s3);
        objects.add(s3);
        System.out.println(objects.toString());
        //删除
        objects.remove(new Student("ccc", 22));  //重写了equals
        System.out.println(objects.toString());
        //遍历
        //1.for
        for (int i = 0; i < objects.size(); i++) {
            System.out.println(objects.get(i));
        }
        //2.foreach
        for (Object obj :
                objects) {
            System.out.println(obj);
        }
        //Iterator
        Iterator<Object> iterator = objects.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //listIterator列表迭代器
        ListIterator<Object> objectListIterator = objects.listIterator();
        //正序
        while (objectListIterator.hasNext()){
            System.out.println(objectListIterator.next());
        }
        //倒序
        while (objectListIterator.hasPrevious()){
            System.out.println(objectListIterator.previous());
        }
    }
}