The author of LinkedList said he didn't use LinkedList himself

Hello everyone , I am a yes.

Surfing the Internet today , See an article saying LinkedList The author said he didn't have to LinkedList, I went to his twitter on purpose , Found that he did say that ！

Maybe this is the big guy , I make wheels , But I don't ！ Or this is the legendary cook who doesn't eat his own dishes ？

No more , Get down to business . In fact, I personally feel that what the boss said seems to be true , Because it doesn't seem to be used in business LinkedList , Most of the scenes use ArrayList More appropriate , I counted my daily usage , It's really all ArrayList .

Speaking of this , Someone may disagree , Said I had seen the face-to-face test questions ,LinkedList But it has its advantages ！

I've also read this question , If I remember correctly, it should be ： say something ArrayList and LinkedList Differences between ？

I think this question can be called “ The top three of the eight part essay ”, In fact, this problem is mapped to the comparison between arrays and linked lists .

As long as you read this interview question online , The answer you see must be ：

• Random access to arrays is fast , Insertion and deletion are slow
• The insertion and deletion of linked list is fast , Random access is slow
• Frequent additions and deletions , It is more appropriate to use a linked list
• When there are many random searches , An array is more appropriate

The problem lies in the frequent addition and deletion of the linked list . If only from the perspective of increasing the time complexity of these three methods , Such is the case , No mistake. .

however , In normal use , This statement is completely untenable ！ Do you think , If you want to delete an element from the linked list , You have to find it first ！ The search of this linked list can be time-consuming ！

So in practice , If you have frequent additions and deletions , Nor should we use linked lists .

Don't believe it ？ Let's do an experiment to see .

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); // take list fill , Pretend we get so 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 consuming ：" + (t2-t1));
    }

    public static void main(String[] args) {
    

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

        randomAdd(fillList(new LinkedList<>()), " Linked list ");

    }
}

The experiment is rough and simple , But it's also intuitive , Separate the filled data ArrayList and LinkedList perform 10 Ten thousand random insertion operations , Then count the time consumption separately .

The results are as follows ：

Is that so? , In the case of random insertion , The linked list is not dominant, but much weaker than the array ！

So for the insertion of linked list , You can't just focus on the time complexity of its insertion , Also include the cost of finding the front node , therefore You can't Say arbitrarily ： Frequent additions and deletions , It is more appropriate to use a linked list

Of course , If the amount of data is small , In fact, both are similar , For example, the length is 100 , perform 100 Time , The time consumption is as follows ：

The length is 1000 , perform 1000 Time , The time consumption is as follows ：

therefore , In the case of a small amount of data and a small number of operations, there is no need to worry too much about which one to use . However, when the amount of data is large and sensitive to time delay , It is suggested to do a good job in testing , Can not be based on some plain “ Online conclusion ” And come to a conclusion .

Okay , For the time being . Remember, don't go to the interview directly , We need to question more , Add some personal thinking , This will make people think you have something more .

I am a yes, From a little bit to a billion , See you next time .