Hello, I’m Yes.

Today, while surfing the Internet, I saw an article that said the author of LinkedList said he doesn’t even use LinkedList, so I went to his Twitter account and found out he actually said that!

Maybe this is the big guy. I make wheels, but I don’t use them! Or is it the legendary cook who doesn’t eat his own cooking?

Let’s cut to the chase. In fact, I personally think it is true that the boss said yes, because it seems that business does not use LinkedList, most scenarios are used ArrayList is more appropriate, I counted my daily use, it is really ArrayList.

Some people may disagree and say I read the interview questions and my LinkedList has its advantages!

What is the difference between ArrayList and LinkedList?

I think this question can be called “eight article top three a”, in fact, this question mapping is also about arrays and linked list comparison.

If you’ve ever looked at this interview question online, the answer you’re likely to see is:

  • Random access to arrays is fast, and insertion and deletion are slow
  • Linked list insertion and deletion is fast, random access is slow
  • In the case of frequent additions and deletions, a linked list is appropriate
  • In the case of a lot of random lookups, arrays are appropriate

The problem lies in the frequent addition and deletion of linked lists. This is true, if only in terms of increasing the time complexity of checking these three methods.

However, in ordinary use, this statement is completely untenable! If you think about it, if you want to delete an element from a linked list, you first have to find it! This list search can be time-consuming!

So in practice, if you have frequent additions and deletions, you should not use linked lists.

Don’t believe it? Let’s do an experiment.


public class YesArrayLinkedBattle {
    private static final int COUNT = 100000;

    static List<Integer> fillList(List<Integer> list) {
        for (int i = 0; i < COUNT; i++) {
            list.add(i); // Fill the list and pretend we have this much data in the database
        }
        return list;
    }
    static void randomAdd(List<Integer> list, String listType) {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            list.add(ThreadLocalRandom.current().nextInt(0,COUNT), i);
        }
        long t2 = System.currentTimeMillis();
        System.out.println(listType +"Random position insertion" + COUNT + "Time:" + (t2-t1));
    }

    public static void main(String[] args) {

        randomAdd(fillList(new ArrayList<>(COUNT)), "Array");

        randomAdd(fillList(new LinkedList<>()), "The list"); }}Copy the code

The experiment is crude and simple, but also intuitive: perform 100,000 random inserts on each ArrayList and LinkedList filled with data, and count the time spent on each.

The result is as follows:

Right? In the case of random insertion, linked lists are not superior but rather weaker than arrays!

Therefore, for the insertion operation of linked list, we should not only pay attention to the time complexity of insertion, but also take into account the cost of finding the previous node. Therefore, we cannot arbitrarily say that linked list is suitable for frequent addition and deletion

Of course, if the amount of data is very small, in fact, both of them are similar. For example, if the length is 100, the execution time of 100 times is as follows:

The length of the command is 1000. If the command is executed for 1000 times, the time is as follows:

So, you don’t have to worry too much about which one to use when you don’t have a lot of data and you don’t have a lot of operations. However, in the case of large amount of data and time-delay sensitivity, it is recommended to do a good job of testing, not just based on some “online conclusions” and make a conclusion.

Okay, that’s enough for now. Remember that the next time you go to an interview, don’t go straight to the eight-part essay. Let’s ask more questions and think more personally. This will make you seem more knowledgeable.

I am yes, from a little bit to a hundred million little bit, welcome to pay attention to my personal public account [YES training level guide], we will see you next ~