The difference between ArrayList and LinkedList

ArrayList:

characteristic ：

      Based on dynamic array , continuity Memory Storage , The time complexity of random access of arrays through corner markers is O(1),CPU The internal cache structure of caches contiguous memory segments , Can significantly reduce the performance overhead of reading memory . Because the data types stored in the array are the same , So the data occupies the same size （ Offset ）

        Expansion mechanism : Because the array length is fixed , You need to create a new array when you store data beyond the length , Each expansion is of the original array length 1.5 times , Then copy the data of the old array to the new array , If you don't insert data at the end, it also involves the movement of elements ( Make a copy later , Insert new elements ), Using tailing and specifying the initial capacity can greatly improve performance 、 Even more than linkedList ( You need to create a lot of node object )

problem ：ArrayList Is ordered , The sequence of inserting data is consistent with that of traversing data , Why is it so slow to insert data into an array ？

because ： When inserting at the specified position , The following data will move back one by one

    public static void main(String[] args) {

        ArrayList<String> arrayList = new ArrayList<String>();
        arrayList.add("hello1");
        arrayList.add("hello2");
        arrayList.add("hello3");
        arrayList.add(3,"hello4");
        arrayList.add(3,"hello5");
        arrayList.add(3,"caibi");

        Iterator<String> ite=arrayList.iterator();
        while(ite.hasNext())// There is value after judging the next element 
        {
            System.out.println(ite.next());
        }

    }

/*
 result ：
    hello1
    hello2
    hello3
    caibi
    hello5
    hello4

ArrayList The default insertion method is tail interpolation , The reason for the slowness is also when deleting an element in the middle of the array , The following elements will move forward one by one , And the capacity expansion is very slow , This is ArrayList The reason for the slow update .

 

When creating a ArrayList Array time , You can specify the initial array length ：

    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);
        }
    }

If not specified, the default is as follows ：

JDK1.7 The default length of the dynamic array is 10

JDK1.8 The default length of the dynamic array is 0, When the first addition operation is performed, the capacity is expanded to 10（ Lazy loading ）;

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

  about DEFAULTCAPACITY_EMPTY_ELEMENTDATA Source code interpretation ：

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

LinkedList:

characteristic ：

Based on the list , Can be stored in distributed memory , Suitable for data insertion and deletion , The insertion time complexity is almost O(1), Not suitable for query : You need to traverse one by one LinkedList You have to use iterator Out of commission for loop , Because every time for Circulating through the body get() Get a The element needs to be aligned list Do the traversal again , Great performance consumption . Also, don't try to use indexOf Return the element index , And use it to traverse , Use indexIOf Yes list Conduct Traversal , When the result is empty, the whole list will be traversed .

indexOf Source code is as follows ：

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

Why not use for Loop traversal LinkedList Well

give an example ：

public static void main(String[] args) {
	List<Integer> list = new LinkedList<Integer>();
	for (int i = 0; i < 10; i++) {
		Random r = new Random();
		Integer tmp = r.nextInt();
		list.add(tmp);
	}
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
	for (Integer i : list) {
		System.out.println(i);
	}
	Iterator<Integer> iter = list.iterator();
	while (iter.hasNext()) {
		System.out.println(iter.next());
	}
}

because for Need inside get Problem of method ：

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

get Method is called node Method

node Method performs a global traversal each time , Very low performance ：

    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;
            return x;
        }
    }

  There are two reasons for Inside the loop , Take the former as an example ：
1、get(0), Directly to 0 Bit Node0 The address of , Get Node0 The data in it

2、get(1), Directly to 0 Bit Node0 The address of , from 0 Bit Node0 Find the next one in 1 Bit Node1 The address of , find Node1, Get Node1 The data in it

3、get(2), Directly to 0 Bit Node0 The address of , from 0 Bit Node0 Find the next one in 1 Bit Node1 The address of , find Node1, from 1 Bit Node1 Find the next one in 2 Bit Node2 The address of , find Node2, Get Node2 The data in it .

......

So try not to use