blocks|key|1126571|text|老生常谈，它是一个由数组支持的List。是的，get()的时间复杂度是O(1)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1126572|entityMap^0|F|4|N|5|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

To be pedantic, it's a <code>List</code> backed by an array. And yes, the time complexity for <code>get()</code> is O(1).

blocks|key|1126625|text|Java中的ArrayList是由array支持的List。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1126626|get(index)方法是一个恒定时间的O(1)操作。|1126627|直接从ArrayList.get(index)的Java库中取出的代码|1126628|public+E+get(int+index)+{
++++RangeCheck(index);
++++return+(E)+elementData[index];
}|code-block|syntax|javascript|1126629|基本上，它只是直接从后备数组返回一个值。(RangeCheck(index))也是恒定时间)|1126630|entityMap^0|6|9|H|5|P|4|0|0|A|K|4|0|3|K|0|0|L|H|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Z|8|@$9|10|A|11|B|C]|$9|12|A|13|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|14|8|@$9|15|A|16|B|C]]|D|@]|E|$]]|$1|J|3|K|5|L|7|17|8|@]|D|@]|E|$M|N]]|$1|O|3|P|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|R|$]]

An <code>ArrayList</code> in Java is a <code>List</code> that is backed by an <code>array</code>.

The <code>get(index)</code> method is a constant time, <code>O(1)</code>, operation.

The code straight out of the Java library for <code>ArrayList.get(index)</code>:

<pre><code>public E get(int index) {
 RangeCheck(index);
 return (E) elementData[index];
}
</code></pre>

Basically, it just returns a value straight out of the backing array. (<code>RangeCheck(index)</code>) is also constant time)

blocks|key|1126666|text|只是一张纸条。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1126667|get(index)方法是一个常量时间，O(1)|offset|length|style|CODE|1126668|但如果我们知道索引，情况就是这样。如果我们尝试使用indexOf(something)获取索引，这将耗费O(n)|1126669|entityMap^0|0|0|A|K|4|0|P|I|1G|4|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@$D|N|E|O|F|G]|$D|P|E|Q|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@$D|S|E|T|F|G]|$D|U|E|V|F|G]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|K|$]]

Just a Note.

The <code>get(index)</code> method is a constant time, <code>O(1)</code>

But that's the case if we know the index. If we try to get the index using <code>indexOf(something)</code>, that will cost <code>O(n)</code>

blocks|key|1126717|text|arraylist基本上是array的一个实现。因此，CRUD操作的时间复杂度为：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1126718|get/read+:++O(1)+since+you+can+seek+the+address+directly+from+base

remove/delete+:+O(n)+why+?+Because+once+we+delete+the+element+at+index,+then+we+need+to+move+the+after+values+one+by+one+to+the+left.+

add+:+O(1)+becuase+you+always+add+the+end+of+the+array+-+next+free+address+available.

update+:+O(1)+since+you+are+just+changing+the+value+but+nothing+value+moving....across+the+array.|code-block|syntax|javascript|1126719|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

The arraylist is basically an implementation of array. so the time complexity of the CRUD operations on it would be : 

<pre><code>get/read : O(1) since you can seek the address directly from base

remove/delete : O(n) why ? Because once we delete the element at index, then we need to move the after values one by one to the left. 

add : O(1) becuase you always add the end of the array - next free address available.

update : O(1) since you are just changing the value but nothing value moving....across the array.
</code></pre>

Is <code>ArrayList</code> an array or a list in java? what is the time complexity for the get operation, is it <code>O(n)</code> or <code>O(1)</code>?

Time complexity for java ArrayList

Java

在java中，ArrayList是数组还是列表？get操作的时间复杂度是多少，是O(n)还是O(1)

问java ArrayList的时间复杂性
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java ArrayList的时间复杂性EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问java ArrayList的时间复杂性
EN