Abstract

  • Along with Vector (thread-safe), vector is a subclass of List
  • LinkedList is a data structure based on a two-way LinkedList
  • ArrayList directly returns data during query. LinkedList traverses linked lists, so ArrayList is efficient in random query
  • ArrayList needs to move the location of elements when adding and deleting, and copy the array. LinkedList needs to find the element inserted according to the location, and then add Pointers. When the data volume is small (less than 10000), the performance is similar, but when the data volume is large, the efficiency of LinkedList is high

1. Vector is a subclass of list, along with vector(thread-safe)

List JDK documentation description

LinkedList is a data structure based on a two-way LinkedList

   // ArrayList
   public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
            initialCapacity);
        }
    }
    //LinkedList
    public boolean addAll(int index, Collection<? extends E> c) {
    	checkPositionIndex(index);
    
    	Object[] a = c.toArray();
    	int numNew = a.length;
    	if (numNew == 0)
    		return false;
    
    	Node<E> pred, succ;
    	if (index == size) {
    		succ = null;
    		pred = last;
    	} else {
    		succ = node(index);
    		pred = succ.prev;
    	}
    
    	for (Object o : a) {
    		@SuppressWarnings("unchecked") E e = (E) o;
    		Node<E> newNode = new Node<>(pred, e, null);
    		if (pred == null)
    			first = newNode;
    		else
    			pred.next = newNode;
    		pred = newNode;
    	}
    
    	if (succ == null) {
    		last = pred;
    	} else {
    		pred.next = succ;
    		succ.prev = pred;
    	}
    
    	size += numNew;
    	modCount++;
    	return true;
    }
Copy the code

3.ArrayList directly returns data during query. LinkedList needs to traverse linked lists, so ArrayList is relatively efficient in random query

    //ArrayList
   public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }
    //LinkedList
     public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            returnx; }}Copy the code

4.ArrayList needs to move the position of elements when adding and deleting, and copy the array. LinkedList needs to find the element at the insertion position according to its position, and then add Pointers. However, LinkedList is more efficient when the data volume is large

    //ArrayList
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    //LinkedList
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        elselinkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { // assert succ ! = null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode;if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
Copy the code

5. Test the program

public class Test1 {
    static List<Integer> arrayData =new ArrayList<Integer>();
    static List<Integer> linkedData =new LinkedList<Integer>();
    public static  int  maxCount = 30000;

    public static void main(String[] args) {

        for(int i=0; i<maxCount; i++){ arrayData.add(i); linkedData.add(i); } System.out.println("maxCount:"+maxCount); System.out.println(system.out.println ("arrayData get time:"+getTime(arrayData));
        System.out.println("linkedData get time:"+getTime(linkedData)); System.out.println(system.out.println ("arrayData insert time:"+insertTime(arrayData));
        System.out.println("linkedData insert time:"+insertTime(linkedData)); Public static long getTime(List<Integer> List){long time= system.currentTimemillis ();for(int i = 0; i < maxCount; i++){
            int getData = list.get(i);
        }
        returnSystem.currentTimeMillis()-time; } public static long insertTime(List<Integer> List){long num = maxCount; int index = 1000; long time=System.currentTimeMillis();for(int i = 1; i < num; i++){
            list.add(index, i);
        }
        returnSystem.currentTimeMillis()-time; }}Copy the code

6. Running result

maxCount:10000
arrayData get time:1
linkedData get time:82
arrayData insert time:24
linkedData insert time:27

maxCount:30000
arrayData get time:2
linkedData get time:658
arrayData insert time:127
linkedData insert time:58
Copy the code