1. Difference between ArrayList and LinkedList
  • ArrayList and LinkedList by name, they are an Array data structure and a Link data structure, and they are both implementations of the List interface
  • The former is an array queue, which is equivalent to a dynamic array. The latter is a bidirectional linked list structure, which can also be used as a stack, queue, or double-ended queue
  • ArrayList is more efficient than LinkedList when accessing randomly (get, set) because LinkedList is a linear data store that requires moving the pointer backwards
  • When adding and removing data (add and remove operations), LinkedList is more efficient than ArrayList. Because ArrayList is an array, adding and deleting operations in ArrayList will affect the subscript index of all data after the operation point, requiring data movement
  • In terms of utilization efficiency, ArrayList is less free because it requires manual setting of fixed size changes, but it is easier to use. You just create, then add data, and use it by calling subscripts. While LinkedList has high freedom and can dynamically change with the amount of data, but it is not easy to use.
  • The main space overhead of ArrayList is the need to reserve some space in IList list. The main space cost of LinkedList is to store node information and node pointer information
  1. The reason ArrayList randomly accesses faster than LinkedList
  • An ArrayList is essentially an array of data structures, or a chunk of memory. This means that when I get(index), I can directly calculate the location of the index element in memory that I want to access based on the start address of the array + the offset. LinkedList can be simply understood as a LinkedList in data structure. Instead of a contiguous space, each element has a memory structure with one element and the address of the next element. When get(index), only the address of the next element can be obtained from the first element. In time complexity, ArrayList get(index) is O(1), LinkedList is O(n)

I took a look online at the code that tests the speed ratio

package com.Java8;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class ListPerformance {

    private static final int REPS = 100;

    private abstract static class Tester// Inner abstract class, asListThe test.{

        String name;
        int size;

        Tester(String name, int size) {
            this.name = name;
            this.size = size;
        }

        abstract void test(List a);
    }

    private static Tester[] tests = {new Tester("get".300)// A test array that stores get, Iteration, insert, and remove.
    {
        void test(List a) {
            for (int i = 0; i < REPS; i++) {
                for (int j = 0; j < a.size(); j++) { a.get(j); }}}},new Tester("iteration".300) {
        void test(List a) {
            for (int i = 0; i < REPS; i++) {
                Iterator it = a.iterator();
                while(it.hasNext()) { it.next(); }}}},new Tester("insert".1000) {
        void test(List a) {
            int half = a.size() / 2;
            String s = "test";
            ListIterator it = a.listIterator(half);
            for (int i = 0; i < size * 10; i++) { it.add(s); }}},new Tester("remove".5000) {
        void test(List a) {
            ListIterator it = a.listIterator(3);
            while(it.hasNext()) { it.next(); it.remove(); }}}};public static void test(List a) {
        System.out.println("Testing " + a.getClass().getName());// Outputs the name of the test class
        for (int i = 0; i < tests.length; i++) {
            fill(a, tests[i].size);// Populates the empty collection
            System.out.print(tests[i].name);
            long t1 = System.currentTimeMillis();
            tests[i].test(a);// Test
            long t2 = System.currentTimeMillis();
            System.out.print(":" + (t2 - t1) + " ms "); }}public static Collection fill(Collection c, int size) {
        for (int i = 0; i < size; i++) {
            c.add(Integer.toString(i));
        }
        return c;
    }

    public static void main(String[] args) {
        test(new ArrayList());
        System.out.println();
        test(newLinkedList()); }}Copy the code