Article directory
- Introducing ArrayList and LinkedList
- Where is the destruction of the three views?
-
- reason
- Try it yourself and compare
-
- Query efficiency
-
- 1. Million-level data volume, write test methods.
- 2. Five million data volume, write test methods
- 3. Tens of millions of data volumes, writing test methods
- Addition and deletion efficiency
-
- Increase elemental efficiency
-
- 1. Increase the head
- 2. Increase in the middle part
- 3. Increase the tail
- Deletion element efficiency
-
- 1. Header deletion
- 2. Delete the middle part
- 3. Tail deletion
- Thought questions?
- Preface: The author is also a beginner. If there are any mistakes in what I write, please forgive me and help remind me to make corrections. Thank you.
Introduce ArrayList and LinkedList
- There is such a classic interview question:
What is the difference between ArrayList and LinkedList?
- I attach the answer here
The data structure is different:
- The bottom layer of ArrayList is an array, and it is a dynamic array. The space in the memory is continuous; why is it a dynamic array? Because ArrayList has its own dynamic expansion mechanism, I will not introduce it in detail here. If you are interested, you can learn about it yourself.
- The bottom layer of LinkedList is a linked list, and it is a double linked list. The space in the memory is discontinuous because it is connected through pointers. There are head nodes and tail nodes. The tail node last of the previous element points to the head node prev of the next element. The tail node last of the last element points to the head node prev of the first element.
Thread safety issues:
- ArrayList is thread unsafe, but discarding safety improves performance.
- LinkedList is thread-safe, but its performance is relatively low.
Query efficiency is different:
- ArrayList searches for elements through subscripts, so it can quickly locate the element position and query efficiency is fast.
- LinkedList points to the next element or the previous element through a pointer. Relatively speaking, it needs to be searched one by one, which is slow in query efficiency.
The efficiency of additions and deletions is different:
- Because ArrayList is continuous in memory, the array structure needs to be rearranged when adding or deleting elements. This process consumes a lot of resources, so the addition and deletion efficiency is slow.
- LinkedList only needs to change the pointer to add or delete, so relatively speaking, addition and deletion are more efficient.
There may be a few more… Welcome to summarize
Where can we destroy the three views?
- Okay, the author has attached a relatively standard answer above, but the question arises. I said that the three views are destroyed, but where do I destroy the three views?
- What I just said, ArrayList query efficiency is fast, addition and deletion efficiency is slow; LinkedList query efficiency is slow, addition and deletion efficiency is fast. And now I want to ask,Is this really the case?
Reason
- Okay, I won’t give it away. ArrayList query efficiency is indeed fast. This is an indisputable fact. However, the addition and deletion efficiency is not necessarily “worse” than LinkedList. The reason is that based on a certain data amount, it can break my What was said before.
Try it yourself and compare it
- OK, let’s talk about the code. First we write a test class:
public class ListTest {<!-- -->
private static List<String> array = new ArrayList<>();
private static List<String> linked = new LinkedList<>();
}
Query efficiency
1. Million-level data volume, write test methods.
/**
* Million level query comparison 0 0
*/
@Test
public void millionQeuryTest(){<!-- -->
//Add two million data each
for (int i = 0; i < 2000000; i + + ) {<!-- -->
array.add("array");
linked.add("link");
}
long startTime = System.currentTimeMillis();
System.out.println(array.get(1999999));
long endTime = System.currentTimeMillis();
System.out.println("ArrayList query time: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
System.out.println(linked.get(1999999));
long endTime1 = System.currentTimeMillis();
System.out.println("LinkedList query time:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
As you can see, there is no difference in the results.
2. Five million data volume, write test method
/**
* Five million level query comparison
*/
@Test
public void fiveMillionQeuryTest(){<!-- -->
//Add five million data each
for (int i = 0; i < 5000000; i + + ) {<!-- -->
array.add("array");
linked.add("link");
}
long startTime = System.currentTimeMillis();
System.out.println(array.get(4999999));
long endTime = System.currentTimeMillis();
System.out.println("ArrayList query time: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
System.out.println(linked.get(4999999));
long endTime1 = System.currentTimeMillis();
System.out.println("LinkedList query time:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
As you can see, there is no difference.
3. Tens of millions of data volumes, write test methods
/**
* Tens of millions of data queries
*/
@Test
public void tenMillionQeuryTest(){<!-- -->
//Add 10 million data each
for (int i = 0; i < 10000000; i + + ) {<!-- -->
array.add("array");
linked.add("link");
}
long startTime = System.currentTimeMillis();
System.out.println(array.get(4999999));
long endTime = System.currentTimeMillis();
System.out.println("ArrayList query time: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
System.out.println(linked.get(4999999));
long endTime1 = System.currentTimeMillis();
System.out.println("LinkedList query time:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
It can be seen that ListedList is significantly different from ArrayList only when the amount of data is tens of millions.
Next we look at the efficiency of additions and deletions.
Adding and deleting efficiency
- Compare deletions and additions. Since we have compared queries before and found that tens of millions of data can be clearly compared, we will also use tens of millions of data for comparison.
- Comparison of additions and deletions will be divided into: head insertion method, tail insertion method and middle deletion.
- First write the test class, here is a lazy price static code block
public class ListTest2 {<!-- -->
/**
* Compare execution deletions and additions:
* Since we have compared queries before and found that tens of millions of data can show obvious comparisons, so next we will also use tens of millions of data for comparison.
*/
private static List<String> array = new ArrayList<>();
private static List<String> linked = new LinkedList<>();
static {<!-- -->
//Add 10 million data each
for (int i = 0; i < 10000000; i + + ) {<!-- -->
array.add("array");
linked.add("link");
}
}
}
Increase element efficiency
1. Increase the head
code show as below:
/**
* Add contrast to the header
*/
@Test
public void headAdd(){<!-- -->
long startTime = System.currentTimeMillis();
linked.add(0,"link");
long endTime = System.currentTimeMillis();
System.out.println("It takes time to add the LinkedList header: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.add(0,"array");
long endTime1 = System.currentTimeMillis();
System.out.println("It takes time to add the ArrayList header: " + (endTime1-startTime1) + "ms");
}
The result is as follows:
Header addition, LinkedList is faster than ArrayList. Because ArrayList has nearly 10 million elements to move backward, LinkedList only needs to change the pointer to point.
2. Increase in the middle part
code show as below:
/**
* Add contrast in the middle
*/
@Test
public void bodyAdd(){<!-- -->
long startTime = System.currentTimeMillis();
linked.add(5000000,"link");
long endTime = System.currentTimeMillis();
System.out.println("It takes time to add to the middle of LinkedList:" + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.add(5000000,"array");
long endTime1 = System.currentTimeMillis();
System.out.println("It takes time to add to the middle of ArrayList:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
Add in the middle, but LinkedList slows down. This is because before adding, there are nearly five million data to be added. Traverse the query, and then perform the addition operation, and we know that the LinkedList query itself is slower than the ArrayList, so the result is like this
3. Increase the tail
code show as below:
/**
* Add contrast at the end
*/
@Test
public void endAdd(){<!-- -->
long startTime = System.currentTimeMillis();
linked.add("link");
long endTime = System.currentTimeMillis();
System.out.println("It takes time to add the end of LinkedList: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.add("array");
long endTime1 = System.currentTimeMillis();
System.out.println("It takes time to add to the end of ArrayList: " + (endTime1-startTime1) + "ms");
}
The result is as follows:
Adding at the end, ArrayList does not need to rearrange the structure, just add at the end, so the time is similar to LinkedList.
Efficiency of deleting elements
- Since deleting is similar to adding, I will just demonstrate it.
1. Header deletion
code show as below:
/**
* Add contrast to the header
*/
/**
* Header deletion comparison
*/
@Test
public void headRemove(){<!-- -->
long startTime = System.currentTimeMillis();
linked.remove(0);
long endTime = System.currentTimeMillis();
System.out.println("LinkedList header deletion time: " + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.remove(0);
long endTime1 = System.currentTimeMillis();
System.out.println("ArrayList header deletion time: " + (endTime1-startTime1) + "ms");
}
The result is as follows:
Header removal, LinkedList is faster than ArrayList.
2. Delete the middle part
code show as below:
/**
* Delete comparison in the middle part
*/
@Test
public void bodyRemove(){<!-- -->
long startTime = System.currentTimeMillis();
linked.remove(5000000);
long endTime = System.currentTimeMillis();
System.out.println("Deletion time in the middle of LinkedList:" + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.remove(5000000);
long endTime1 = System.currentTimeMillis();
System.out.println("Deletion time in the middle of ArrayList:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
Delete in the middle, LinkedList is slow.
3. Tail deletion
code show as below:
/**
* Delete comparison at tail
*/
@Test
public void endRemove(){<!-- -->
long startTime = System.currentTimeMillis();
linked.remove(9999999);
long endTime = System.currentTimeMillis();
System.out.println("LinkedList tail deletion time:" + (endTime-startTime) + "ms");
long startTime1 = System.currentTimeMillis();
array.remove(9999999);
long endTime1 = System.currentTimeMillis();
System.out.println("Deletion time at the end of ArrayList:" + (endTime1-startTime1) + "ms");
}
The result is as follows:
Tail deletion, ArrayList does not need to rearrange the structure, only elements are deleted at the end, so the time is similar to LinkedList.
- OK, this is a little knowledge point shown in this blog post. The addition and deletion efficiency of ArrayList is not necessarily slower than that of LinkedList, because with the support of a certain amount of data, LinkedList also needs to consider the time of querying elements before operating elements.
Thinking questions?
- We know that HashMap is thread-unsafe, while CurrentHashMap is thread-safe. So why do we usually use HashMap in most cases?
- Tip: The author here only talks about what I know. I’m going to learn more about it too! On what basis do we usually write code? (Spring framework! Answer right away), and what is the singleton pool SingletonObjects that stores beans in the Spring container?