List实现类

List实现类：

　　ArrayList;

数组结构实现，查询快，增删慢
JDK1.2版本，运行效率快，线程不安全

　　Vector:

数组结构实现，查询快，增删慢
JDK1.0版本，运行效率慢，线程安全

　　LinkedList:

链表结构实现，增删快，查询慢
是一个双向链表

ArrayList：

使用

package com.java.leetcode.collection;

import java.util.ArrayList;

import java.util.Iterator;

/*

ArrayList的使用

 */

public class AList01 {

    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();

        //添加

        FruitBean apple = new FruitBean("苹果","红色");

        FruitBean yellowPeach = new FruitBean("黄桃","黄色");

        FruitBean pitaya = new FruitBean("火龙果","红色");

        FruitBean snowPear = new FruitBean("雪梨","黄色");

        FruitBean plum = new FruitBean("李子","青色");

        arrayList.add(apple);

        arrayList.add(yellowPeach);

        arrayList.add(pitaya);

        arrayList.add(snowPear);

        arrayList.add(plum);

        System.out.println("元素个数："+arrayList.size());

        System.out.println("元素内容："+arrayList);

        //删除

        //arrayList.remove(apple);

        //遍历

        System.out.println();

        System.out.print("***用迭代器遍历ArrayList***");

        Iterator it = arrayList.iterator();

        while (it.hasNext()){

            FruitBean fruit = (FruitBean)it.next();

            System.out.print(fruit);

        }

        //判断

        System.out.println();

        System.out.println();

        System.out.println("苹果在arrayList中吗？"+arrayList.contains(new FruitBean("苹果","红色")));

        /*

        上面为false，因为是new了一个新的对象，contains方法的实现是用equals.而equals()的默认行为是比较引用。

        如果想要判断的是两个对象的值是否相等，需要覆写下该对象类型的equals方法。

        在FruitBean类中重写equals方法.重写后，为true

         */

        //查找

        System.out.println("李子的位置："+arrayList.indexOf(new FruitBean("李子","青色")));

    }

}

运行结果：

ArrayList源码分析：

默认容量：DEFAULT_CAPACITY = 10

　　注意：即如果没有向集合中添加任何元素时，容量为0

存放元素的数组：elementData

实际元素个数：size

无参构造器：

    public ArrayList() {

        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

    }

ArrayList arrayList = new ArrayList();===》此时容量为0，size为0

add方法：

　　arrayList.add(apple);=====》添加第一个元素.

    public boolean add(E e) {   //0+1

        ensureCapacityInternal(size + 1);  // Increments modCount!!增长容量

        elementData[size++] = e;  //赋值

        return true;

    }

  　　　　　　　　　　　　　　　　　　　　　　　　//1
  private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//10,1 ==>此处取10

        }

　　　　　　　　　　　　　　　　　　　　　　//10

        ensureExplicitCapacity(minCapacity);

    }

 　　　　　　　　　　　　　　　　　　　　　　　　　　　//10
   private void ensureExplicitCapacity(int minCapacity) {

        modCount++;

        // overflow-conscious code

        if (minCapacity - elementData.length > 0)   //10-0>0

            grow(minCapacity);

    }

数组扩容的核心代码：

　　　　　　　　　　　　　　　　//10
    private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length; //0

        int newCapacity = oldCapacity + (oldCapacity >> 1);/0+0

        if (newCapacity - minCapacity < 0)  //0 - 10 <0

            newCapacity = minCapacity;     //10

        if (newCapacity - MAX_ARRAY_SIZE > 0)   //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 是一个非常大的数

            newCapacity = hugeCapacity(minCapacity);

        // minCapacity is usually close to size, so this is a win:

        elementData = Arrays.copyOf(elementData, newCapacity); 
　　　　　　　　　　　　　　　　　　　　　　　　//null       10 ==>elementData 10

    }

所以，添加第一个元素后，容量为10.

每次扩容大小是原来的1.5倍

Vector:

package com.java.leetcode.collection;

import java.util.Enumeration;

import java.util.Vector;

/*

Vector的使用

 */

public class VList02 {

    public static void main(String[] args) {

        Vector vector = new Vector();

        FruitBean apple = new FruitBean("苹果","红色");

        FruitBean yellowPeach = new FruitBean("黄桃","黄色");

        FruitBean pitaya = new FruitBean("火龙果","红色");

        FruitBean snowPear = new FruitBean("雪梨","黄色");

        FruitBean plum = new FruitBean("李子","青色");

        vector.add(apple);

        vector.add(yellowPeach);

        vector.add(pitaya);

        vector.add(snowPear);

        vector.add(plum);

        System.out.println("元素内容："+vector);

        vector.remove(0);

        vector.remove(new FruitBean("火龙果","红色"));

        System.out.println("删除之后："+vector);

        /*

        遍历

        使用枚举器，也可用for，迭代器等，这里演示枚举器

         */

        System.out.println();

        System.out.println("******使用枚举器遍历******");

        Enumeration en = vector.elements();

        while (en.hasMoreElements()){

            System.out.println(en.nextElement());

        }

        System.out.println();

        System.out.println("第一个元素："+vector.firstElement());

        System.out.println();

        System.out.println("最后一个元素："+vector.lastElement());

    }

}

运行结构：

LinkedList:

package com.java.leetcode.collection;

import java.util.LinkedList;

/*

LinkedList的使用

存储结构：双向链表

 */

public class LList03 {

    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();

        FruitBean apple = new FruitBean("苹果","红色");

        FruitBean yellowPeach = new FruitBean("黄桃","黄色");

        FruitBean pitaya = new FruitBean("火龙果","红色");

        FruitBean snowPear = new FruitBean("雪梨","黄色");

        FruitBean plum = new FruitBean("李子","青色");

        linkedList.add(apple);

        linkedList.add(yellowPeach);

        linkedList.add(pitaya);

        linkedList.add(snowPear);

        linkedList.add(plum);

        System.out.println(linkedList);

        //删除，遍历等都与前面一样。这里不写了。

    }

}

源码分析：

LinkedList linkedList = new LinkedList();//刚创建时，链表为空。
add方法；

    public boolean add(E e) {

        linkLast(e);

        return true;

    }

    void linkLast(E e) {

        final Node<E> l = last; //添加第一个元素时，last为null

        final Node<E> newNode = new Node<>(l, e, null); //null,e,null

        last = newNode;

        if (l == null)

            first = newNode;

        else

            l.next = newNode;

        size++;

        modCount++;

    }

    private static class Node<E> {  //结点

        E item;  //实际数据

        Node<E> next;  //指向下一个结点

        Node<E> prev;  //指向上一个结点

        Node(Node<E> prev, E element, Node<E> next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

        }

    }

ArrayList 和 LinkedList的区别：

ArrayList必须开辟连续空间，查询快，增删慢
LinkedList无需开辟连续空间，查询慢，增删快

巴特西

List实现类

最新文章

热门文章