【Java刷题】初始化List应该选择ArrayList还是LinkedList

class Solution {
    public int minimumOperations(TreeNode root) {
        //层次遍历结果
        List<List<Integer>> list = levelOrder(root);
        
        int res = 0;
        //加上每层按照排序结果交换的次数
        for(int i = 0; i < list.size(); i++){
            res += getMinswap(list.get(i));
        }

        return res;
    }

    List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new LinkedList<>();
            for(int i = 0; i < size; i++){
                TreeNode now = queue.poll();
                tmp.add(now.val);
                if(now.left != null) queue.offer(now.left);
                if(now.right != null) queue.offer(now.right);
            }
            list.add(tmp);
        }
        return list;
    }

    int getMinswap(List<Integer> nums){
        if(nums.size() == 1) return 0;
        int n = nums.size();
        int res = 0;
        List<Integer> sortedNums = new LinkedList<>(nums);
        Collections.sort(sortedNums);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < sortedNums.size(); i++){
            map.put(sortedNums.get(i), i);
        }
        for(int i = 0; i < n; ){
            if(sortedNums.get(i).equals(nums.get(i))){
                i++;
                continue;
            }
            Collections.swap(nums, i, map.get(nums.get(i)));
            res++;
        }

        return res;
    }

}

class Solution {
    public int minimumOperations(TreeNode root) {
        //层次遍历结果
        List<List<Integer>> list = levelOrder(root);
        
        int res = 0;
        //加上每层按照排序结果交换的次数
        for(int i = 0; i < list.size(); i++){
            res += getMinswap(list.get(i));
        }

        return res;
    }

    List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode now = queue.poll();
                tmp.add(now.val);
                if(now.left != null) queue.offer(now.left);
                if(now.right != null) queue.offer(now.right);
            }
            list.add(tmp);
        }
        return list;
    }

    int getMinswap(List<Integer> nums){
        if(nums.size() == 1) return 0;
        int n = nums.size();
        int res = 0;
        List<Integer> sortedNums = new ArrayList<>(nums);
        Collections.sort(sortedNums);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < sortedNums.size(); i++){
            map.put(sortedNums.get(i), i);
        }
        for(int i = 0; i < n; ){
            if(sortedNums.get(i).equals(nums.get(i))){
                i++;
                continue;
            }
            Collections.swap(nums, i, map.get(nums.get(i)));
            res++;
        }

        return res;
    }

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int count = 10000000;

        List<Integer> listArray = new ArrayList<>();
        List<Integer> listLinked = new LinkedList<>();
        Random random = new Random();
        //生成count个随机值
        for (int i = 0; i < count; i++) {
            int rand = random.nextInt();
            listArray.add(rand);
            listLinked.add(rand);
        }

        //开始计时
        long startTime1 = System.currentTimeMillis();
        //对ArrayList排序
        Collections.sort(listArray);
        long endTime1 = System.currentTimeMillis();
        long usedTime1 = (endTime1 - startTime1);

        //开始计时
        long startTime2 = System.currentTimeMillis();
        //对LinkedList排序
        Collections.sort(listLinked);
        long endTime2 = System.currentTimeMillis();
        long usedTime2 = (endTime2 - startTime2);

        //打印排序时间
        System.out.println("ArrayList排序用时：" + usedTime1);
        System.out.println("LinkedList排序用时：" + usedTime2);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int count = 100000;

        List<Integer> listArray = new ArrayList<>();
        List<Integer> listLinked = new LinkedList<>();
        Random random = new Random();
        //生成count个随机值
        for (int i = 0; i < count; i++) {
            int rand = random.nextInt();
            listArray.add(rand);
            listLinked.add(rand);
        }

        //开始计时
        long startTime1 = System.currentTimeMillis();
        //对ArrayList遍历
        for(int i = 0; i < listArray.size(); i++){
            int a = listArray.get(i);
        }
        long endTime1 = System.currentTimeMillis();
        long usedTime1 = (endTime1 - startTime1);

        //开始计时
        long startTime2 = System.currentTimeMillis();
        //对LinkedList遍历
        for(int i = 0; i < listLinked.size(); i++){
            int a = listLinked.get(i);
        }
        long endTime2 = System.currentTimeMillis();
        long usedTime2 = (endTime2 - startTime2);

        //打印遍历时间
        System.out.println("ArrayList遍历用时：" + usedTime1);
        System.out.println("LinkedList遍历用时：" + usedTime2);
    }
}