Shulou(Shulou.com)06/01 Report--

This article introduces the knowledge of "which is faster for LinkedList and ArrayList to add / delete elements". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Comparison of deleted elements between ArrayList and LinkedList

The principle of deleting an element is the same as that of adding an element, so the operation of deleting an element is similar to that of adding a new element.

I won't repeat it here.

Comparison of ArrayList and LinkedList traversal elements

The test results are very obvious. For LinkedList, it is very inefficient if you use a for loop, but if ArrayList uses a for loop to traverse, it is relatively high.

Why is that?

Emmm, we have to start with the source code

First, let's take a look at the source code of ArrayList. This is relatively simple.

Public class ArrayList extends AbstractList

Implements List, RandomAccess, Cloneable, java.io.Serializable

As you can see, ArrayList implements List, RandomAccess, Cloneable and Serializable interfaces

Are you a stranger to RandomAccess? What is this?

But by looking at the source code, we can find that it is only an empty interface, so why does ArrayList have to implement it?

Because the RandomAccess interface is a flag interface, it indicates that "as long as the list class that implements the interface, you can achieve fast random access."

Achieve fast random access? What can you think of? This is the characteristic of array. You can quickly locate and read through index.

Can you imagine that ArrayList is implemented in an array, so it implements the RandomAccess interface, and LinkedList is implemented in a linked list, so it is not implemented in the RandomAccess interface?

Beautiful ~ that's it.

Let's take a look at the LinkedList source code

Public class LinkedList

Extends AbstractSequentialList

Implements List, Deque, Cloneable, java.io.Serializable

Sure enough, as we imagined, the RandomAccess interface was not implemented

So why is it so slow when the LinkedList interface uses a for loop to traverse?

Let's see what LinkedList does with the get element.

Public E get (int index) {

CheckElementIndex (index)

Return node (index). Item

}

Node node (int index) {

/ / assert isElementIndex (index)

If (index

> 1) {

Node x = first

For (int I = 0; I

Index; iMurt -)

X = x.prev

Return x

}

}

In the get method, the node () method is mainly called, because LinkedList is a two-way linked list, so if (index)

> 1) when determining whether I is in the first half or the second half, traversing in positive order if it is in the first half, and traversing in reverse order if it is in the second half, why is it so slow to use for loop to traverse LinkedList? (it seems to be getting closer and closer to the truth

The reason lies in two for loops. Take the first for loop as an example.

Get (0): get the node0 address directly, and then get the data of node0

Get (1): first get the node0 address, then I < index, start to get the node1 address, meet the conditions, and then get the node1 data.

Get (2): first get the address of node0, then I < index, get the address of node1, I < index, go down, get the address of node2, meet the conditions, and get the data of node2.

Did you find a problem? I just want the data of 2. When LinkedList traverses, it also traverses 0 and 1. If the amount of data is very large, the efficiency will come down quickly.

By now, we have made it very clear that if we want to traverse ArrayList, it is best to do it with a for loop, and if we want to traverse LinkedList, it is best to do it with an iterator.

I guess you must say, A Fan, if the other party sent me a list, I don't know if it is ArrayList or LinkedList? What should I do

Remember the difference between ArrayList and LinkedList? Is it possible that ArrayList implements the RandomAccess interface, but LinkedList does not, so we can start from this point

Warm A Fan here to give a simple little demo, you can refer to:

Public class ListTest {

Public static void main (String [] args) {

List arrayList = new ArrayList ()

ArrayList.add ("aaa")

ArrayList.add ("bbb")

IsUseIterator (arrayList)

List linkedList = new LinkedList ()

LinkedList.add ("ccc")

LinkedList.add ("ddd")

IsUseIterator (linkedList)

}

Public static void isUseIterator (List list) {

If (list instanceof RandomAccess) {

System.out.println ("implements the RandomAccess interface, traversing using for loops")

For (int I = 0; I < list.size (); iTunes +) {

System.out.println (list.get (I))

}

} else {

System.out.println ("RandomAccess interface is not implemented, traversal using iterators")

Iterator it = list.iterator ()

While (it.hasNext ()) {

System.out.println (it.next ())

}

}

}

} the content of "which is faster to add / remove elements, LinkedList or ArrayList" is introduced here. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.