Java的ArrayList迭代器的remove方法是O(n^2)还是O(n)？在遍历列表时？
Java的ArrayList迭代器的remove方法的时间复杂度是O(n)。
在遍历列表时，如果使用ArrayList的迭代器进行遍历，并调用remove方法删除元素，该方法的时间复杂度是O(n)。这是因为ArrayList的底层实现是基于数组，当删除一个元素后，后面的元素需要向前移动，以填补被删除元素的空缺位置。这个移动操作的时间复杂度是O(n)。
需要注意的是，如果使用普通的for循环遍历ArrayList，并在循环体内使用remove方法删除元素，会导致错误的结果。这是因为在循环过程中，删除元素会改变列表的大小，导致索引发生变化，可能会漏掉某些元素或者重复遍历某些元素。为了避免这种情况，可以使用迭代器的remove方法进行安全的删除操作。
推荐的腾讯云相关产品：无
参考链接：
相关·内容
我有两个线程在运行，我需要控制子弹是否接触到敌人，但它给了我这个问题，我打印了"s4“。知道那里发生了什么吗？我还是个初学者。我使用的是Java。
ArrayList<Nemico> nemici= o_orda.getNemici();
for (Nemico nemico : nemici) {
if(Collisioni.ControllaCollisioni(o_navicella, nemico)){
nemici.remove(nemico);
this.o_
浏览 0提问于2020-03-15得票数 1
5回答
在java中，ArrayList是数组还是列表？get操作的时间复杂度是多少，是O(n)还是O(1)
浏览 1提问于2010-02-02得票数 72
回答已采纳
关于ArrayList对象的ConcurrentModificationException有很多问题，但是我还没有找到我的问题的答案。
在我的servlet中，我有一个ArrayList作为成员对象：
List myList<Object> = new ArrayList<Object> (...);
该列表必须在用户和会话之间共享。
在servlet的方法之一method1中，我需要迭代ArrayList项，并在迭代后最终添加清空列表。下面是一段代码：
for (Object o : myList) {
// read item o
}
myList.clea
浏览 1提问于2011-11-29得票数 1
回答已采纳
嗯，我已经看过其他的帖子了，解决不了我的问题。我的ManagedBean中有一个dataTable (JSF)绑定。我有一个选定元素的列表，我想删除这个元素，请参见：
public void removeSelected() {
for (Map.Entry<Integer, Boolean> entry : registrosSelecionados.entrySet()){
if (entry.getValue() == true){
int id = entry.getKey();
Iterator<B
浏览 3提问于2015-01-31得票数 0
回答已采纳
我使用while循环遍历ArrayList，如果值满足特定条件，则就地删除它们。我的代码遵循以下代码片段的精神：
List<Integer> list = new ArrayList<>();
int N = 1000
// setup list to show as an example
for (int i = 0; i < N; i++) {
list.add(i);
}
Date start = new Date();
// iterate over entire list, rem
浏览 12提问于2016-07-27得票数 2
下面的代码使用一个简单的列表，并通过foreach循环和while循环显示列表中包含的元素。
final public class Main
{
public static void main(String... args)
{
List<String>list=new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
li
浏览 3提问于2011-11-19得票数 0
回答已采纳
2回答
我是一个具有大O符号和算法复杂性的初学者。我正在尝试计算下面两个java方法的复杂性，这两个方法都做同样的事情。然而，其中一个会稍微快一点。
ArrayList<Person> filter1(Person x, ArrayList<Person> people){
ArrayList<Person> friends = new ArrayList<Person();
for (Person y: people) friends.add(y);
for (Person y: people) if (!x.knows(y)) friends.
浏览 2提问于2015-03-18得票数 2
在迭代LinkedList时，get(i)是O(N)操作。因此，我们使用Iterator对象遍历列表是有意义的。但是对于ArrayList，get(i)是O(1)。那么，在这种情况下，我说的对吗?当使用ArrayList时，无论我们使用c样式的循环还是Iterator对象，都没有什么区别吗？
浏览 4提问于2015-04-09得票数 0
回答已采纳
4回答
所以我的数据结构类涵盖了时间复杂性，我只想问一个关于arraylist和treemap的性能的问题。
ArrayList的get方法是O(1)，TreeMap的get方法是o(log )
现在，如果我创建了一个遍历整个列表或树的循环，比如
for (int i = 0; i < blahblah.size(); i++)
{
blah blah
}
对于arraylist，这个循环性能是o(1)还是o(n)？我意识到，当你检索1个项目时，性能是O(1)，但是这个循环遍历整个列表，所以它不是1* n个项目，这将使它成为n吗？
树地图也是一样，它是o(log n)还是n log n，因为
浏览 0提问于2011-03-05得票数 0
我有两个arrayLists。其中一个列表列出了在一个州出生的所有总统(列表A)。第二个列表列出了所有的总统(列表B)。我必须对这两个州进行比较，并打印出一份不是在我们当前任何一个州出生的总统名单。基本上，它们不会在列表A中，所以我必须找到列表之间的所有公共名称，并从列表B中删除它们。我该如何开始呢？
import java.util.*;
import java.io.*;
// NO CMD ARGS - ALL FILENAMES MUST BE HARDOCDED AS I HAVE DONE FOR YOU HERE
public class Potus
{
public sta
浏览 0提问于2014-04-16得票数 0
1回答
这是我在StackOverflow上的第一个问题。我不是以英语为母语的人，对任何错误感到抱歉。
事实：
我在Android演播室用Java制作2D游戏。我使用的是SurfaceView、抽象类GameObject和ArrayList<GameObject>。要循环通过ArrayList，我主要使用的是-每个循环- for(GameObject obj: ArrayList)。作为一个游戏循环，我使用的是简单的60 fps游戏循环，但我的计算机仿真器只能达到最大35 fps。
问题：
我已经做了几个月了，现在我决定使用更好的游戏循环，以固定的每秒更新速度，所以它将在模拟器和设备上运行
浏览 3提问于2020-02-06得票数 0
回答已采纳
3回答
我在这里读到了一个关于java、ArrayList和LinkedList性能的ArrayList。给出的答案如下所示。
“链接列表添加不一定是O(1)，或者这应该说addLast()是O(1)。只有在ListIterator中进行添加才是正确的。如果没有添加，则LinkList实现中的添加方法必须在列表中搜索。”
我不明白他所说的“只有通过ListIterator完成”是什么意思。这是否意味着链接列表中有一个数据结构，它保存了每个索引的引用，并且当我们从某个索引中获得listiterator时，listiterator就会立即返回，而不需要遍历列表来查找该索引？
谢谢你们！
浏览 2提问于2010-12-12得票数 1
回答已采纳
所以在我写的一些代码上，我得到了一个索引越界异常。我不理解的是，我知道我正在尝试使用的index元素是存在的。
代码如下：
我有一个数组列表的构造函数
public StixBoard(int number)
{
stixGame = new ArrayList<Integer>(number);
for (int i = 0; i < number; i++)
{
stixGame.add(i);
}
}
此块生成一个随机变量1-3
public int computeMove()
{
int numbe
浏览 0提问于2012-12-08得票数 0
回答已采纳
3回答
正如我所知道的，有4种方法可以访问数组列表。
1)使用Java5前级循环进行循环。2)使用for循环和size()方法循环ArrayList。3)使用迭代器迭代ArrayList。4)在Java中使用ArrayList语言遍历ListIterator。
我的问题is..are都一样吗？一切都很好？有什么不同吗？(特别是对于Iterator，我问它)
浏览 5提问于2014-04-22得票数 0
回答已采纳
我有一个对象项目，我将其同时添加到两个ArrayLists中，下面将简要描述这些列表。在完成某些操作之后，我希望从这两个列表中删除一个项目。这个方法正确吗？我不断地得到一个错误: java.util.ConcurrentModificationException
或者，对于以这种方式处理对象的目的，您能想出比ArrayList更好的解决方案吗？
//there are ArrayList<Bullet> bullets and ArrayList<Updatable> updatable, in the class
public void remove
浏览 2提问于2016-03-25得票数 1
回答已采纳
我知道，演员不是正确的词
java.lang.Object
-> java.util.concurrent.CopyOnWriteArrayList<E>
和
java.lang.Object
-> java.util.AbstractCollection<E>
-> java.util.AbstractList<E>
-> java.util.ArrayList<E>
但是我想要的是将CopyOnWriteArrayList的行为添加到ArrayList中。
Eg :
我想跟着做
浏览 6提问于2013-06-21得票数 4
回答已采纳
我有这样的代码：
出口是传递给方法的ArrayList；riverBasin是int (int RiverBasin)的2D“矩阵”；
for (int[] item: outlets) {
if (item[0] < 2 || item[0] > this.riverBasin.length - 1 || item[1] < 2 || item[1] > this.riverBasin[0].length - 1) {
System.out.println("This provisionally substitutes error c
浏览 7提问于2013-08-22得票数 1
回答已采纳
我正在学习Java的集合框架。我写了这个小程序来检查为什么我们不能使用For-each来删除元素。
代码：
import java.util.ArrayList;
class intro{
public static void main(String args[]){
ArrayList<String> names = new ArrayList<String>();
names.add("Rajat");
names.add("Saxena");
for(Str
浏览 3提问于2015-07-28得票数 1
使用传统的for循环、for-each循环还是迭代器来遍历列表是偏好问题？
1) for(MyClass mc : al){ // do something on mc }
or
2) iter = arrayList.iterator();
while(iter.hasNext()){MyClass mc = iter.Next()}
浏览 0提问于2011-08-08得票数 1
回答已采纳
我在ArrayLists上看到了很多关于如何操作它们的信息，但似乎没有什么能回答我的问题。 我想检查arraylist中的一个元素是否不是活动的，如果是这样的话，删除它，但在列表中再添加2个。通常很简单，除了我需要将更改添加到另一个arraylist中，该arraylist包含第一个arraylist中的所有元素以及其他外部arraylist中的元素。 我认为我可以使用如下所示的临时数组列表来完成此操作： import java.util.ArrayList;
public class main {
public static ArrayList<String> ch
浏览 68提问于2017-03-05得票数 1
回答已采纳
我得到了这个代码片段，运行良好。
import java.util.ConcurrentModificationException;
import java.util.*;
ArrayList<Object> s = new ArrayList<>();
s.add(null);
s.add("test");
try {
System.out.println(s + "\n");
for (Object t : s) {
System.out.println(t);
if (t ==
浏览 0提问于2020-08-12得票数 3
回答已采纳
我想使用1 2 3 4或ArrayList来分析移动3 1 2 4 (整数列表)的过程。
我所做的：
aux = arraylist.get(2); // O(1)
arraylist.remove(2); // O(n)
arraylist.add(0, aux); // O(n), shifting elements up.
aux = linkedlist.get(2); // O(n)
linkedlist.remove(2); // O(n)
linkedlist.addFirst(aux); // O(1)
那么，在这种情况下，我们可以说他们是一样的，还是我遗漏了什么？
浏览 2提问于2017-05-10得票数 1
回答已采纳
我正在读"“这个问题的答案。
在回答中，用户这样描述：“ArrayLists迭代器的一个很大的用例是当你想要在迭代时删除元素的时候”。
即使在Java中使用ArrayList的remove方法也可以实现。我的问题是为什么我们在ArrayList中需要迭代器？
考虑下面的代码：
import java.util.*;
public class ocajp66 {
public static void main(String[] args) {
ArrayList a = new ArrayList();
for (int i = 0; i <
浏览 0提问于2013-04-14得票数 38
回答已采纳
1回答
我正在从基于fieldsToRemove列表的XML字符串中删除一些字段。
List<String> fieldsToRemove = //list of fields to be remove.
String eventString = //XML String.
List<String> list = new ArrayList<>(Arrays.asList(eventString.split("\n")));
Iterator<String> iterator = list
浏览 0提问于2021-10-21得票数 0
1回答
理解java中的同步列表
、、、
我有一个ArrayList，它由一个线程修改，另一个线程读取。读线程很乐意在修改后阅读列表中剩下的内容。当从列表中删除所有项目时，它应该停止。Collections.synchronizedList()的java文档中提到，在对列表执行任何操作之前，我们应该手动同步列表。
在迭代返回列表时，用户必须手动同步：
List =Collections.synchronizedList(新ArrayList())；.同步(列表){ Iterator = list.iterator()；//必须处于同步块中，而(i.hasNext()) foo(i.next())；}不遵循此通知可能会导致非确定性行为
浏览 1提问于2019-05-25得票数 1
我正在编写我的代码，并且得到了"java.util.ConcurrentModificationException“。我用谷歌搜索了一下，也知道只有当你试图修改正在进行的迭代变量时，才会出现这样的错误，而在我的情况下，我感觉不到这一点。下面是我的代码。
// This line is having an error
for(Statement s: _mConsumableStatements)
{
System.out.println("s:"+s);
Boolean isConflict=false;
Res
浏览 2提问于2015-02-16得票数 1
我在一些地方读到，LinkedList在Java中添加和删除元素的时间复杂度是O(1)，而O(n)是获取元素的时间复杂度。ArrayList有O(1)来获取元素，O(n)可以添加和删除元素。
我有一个程序，它必须做许多涉及插入和从列表中恢复元素的操作。因此，我想知道访问元素的ArrayDeque时间是否类似于ArrayList。
浏览 0提问于2018-11-27得票数 2
回答已采纳
我希望有人能向我解释一下这种行为以及发生了什么。
如果我运行以下代码：
phrase = "Don't Panic!"
phraseList = list(phrase)
print(phrase)
print(phraseList)
ontap = ['o', 'n', 't', 'a', 'p']
for letter in phraseList:
print("Letter ", letter)
#if letter not in ontap:
浏览 3提问于2018-02-09得票数 2
在一次创建一个元素，然后在稍后读取一个元素的情况下，最快的列表实现(在java中)是什么？读取将通过迭代器完成，然后列表将被销毁。
我知道get的大O符号是O(1)，ArrayList的add是O(1)，而get的LinkedList是O(n)，add是O(1)。迭代器是否使用相同的大O符号？
浏览 2提问于2008-09-25得票数 27
回答已采纳
第一部分：
我在"Data Structure and Algorithms made in Java“一书中读到，从Linkedlist和Arraylist中删除最后一个元素的时间复杂度为O(n)。但是链表在内部实现了DoublyLinkedlist，所以时间复杂度应该是O(1)，类似地，对于数组来说，因为它在内部实现了数组，所以时间复杂度应该是O(1)。
第二部分：
它还指出，在linkedlist结尾处插入元素的时间复杂度为O(n)，但是linkedlist在结尾处和前面都保留了指针。那么这句话是正确的吗？而且，如果数组未满，则在数组末尾插入元素的时间复杂度为O(1)，如果数组已
浏览 14提问于2017-04-01得票数 10
回答已采纳
3回答
我正在尝试使用“迭代器”.remove删除这个ArrayList中具有偶数索引号的字符串。
import java.util.*;
import static java.lang.System.out;
class MAIN
{
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<String>();
Iterator i = al.iterator();
int len;
Sc
浏览 1提问于2014-11-24得票数 0
当我试图从arraylist中删除一个int时，我得到了大约20个错误。这是一个强力球游戏，我试着去掉匹配的球，以避免重复的球。
for (Integer ballNumber : balls) {
for (Integer yballNumber : yballs) {
if (ballNumber == yballNumber) {
match++;
balls.remove(ballNumber);
yballs.remove(yballNumber);
浏览 0提问于2015-01-15得票数 1
2回答
我遇到了一个特定的问题，在迭代Arraylist中的每个元素时，只包含Arraylist中的第一项(搜索/删除)。这意味着，每当我试图迭代时，都找不到n-1之前的第二个小值。编辑:正在改进我的代码。
您可以尝试以下程序。当添加顺序的第一条记录时，它是完全工作的，只有()：我可以删除和搜索它的值。但是，当添加第二个顺序时:我不能删除和搜索它的值，而是找不到它。
源代码
import java.util.*;
import java.io.*;
public class TestOrders {
public static void main(String[] args) throws
浏览 0提问于2019-10-25得票数 0
回答已采纳
我试图找出这个方法在计算时间复杂性方面会有多大的复杂性。其他人告诉我，这将是最坏的情况O (n ^2) (n是树中的元素)，但我很困惑，因为外部while循环只考虑级别的数量，而不是总元素的数量。
任何帮助都会很好！
公共列表returnLevelOrder(TreeNode根){ <List ret =新的ArrayList ()；
Queue<Integer> queue = new List<Integer>();
if(root==null){
return ret;
}
queue.add(root);
while(!queue.empty
浏览 4提问于2022-03-07得票数 0
回答已采纳
考虑一个ArrayList，其中包含Iterator和List迭代器操作，当一个列表被迭代时，每当Collection对象发生更改时，它就会抛出ConcurrentModificationException，如下所示：
package JavaImpPrograms;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Wdfds {
public static void main(String[] arg
浏览 4提问于2018-06-28得票数 2
嗨，这段代码将返回indexoutofboundsException，我真的不知道为什么？我想从pointlist中删除那些与list中的对象相同的对象。
public void listOfExternalPoints(List<Point> list) {
System.out.println(list.size());
System.out.println(pointList.size());
int n = pointList.size();
for (int i = pointList.size() - 1; i >= 0;
浏览 0提问于2010-11-25得票数 2
回答已采纳
我发现，HashSet的删除(对象o)采用O(1)恒定时间，而ArrayList的删除(对象o)操作采用O(N)，其中N是ArrayList的大小。
有人能详细解释一下为什么吗？
浏览 3提问于2017-12-03得票数 0
可能重复：
我有一系列的链接列表
List<LinkedList<File1>> backup = new ArrayList<LinkedList<File1>>();
在运行时，单击一个按钮，我希望从列表中删除几个元素，并将它们添加到其他列表中。我还尝试将链接列表声明为
List<LinkedList<File1>> lists = Collections.synchronizedList(new ArrayList<LinkedList<File1>>());
错误仍然保持不变。我无法找
浏览 0提问于2012-04-04得票数 0
我想要显示出现在字符列表中的数字，然后删除该数字。下面是我的代码：
打包mytrials；
import java.util.ArrayList;
import java.util.ListIterator;
public class MyTrials {
public static void main(String[] args) {
ArrayList<Character> list = new ArrayList<Character>();
list.add('a');
list.add('1');
浏览 0提问于2013-04-26得票数 2
回答已采纳
这里我的想法是检查我的ArrayList元素是以A、B、C开头，还是以另一个字母开头，但由于某种原因，我的IF无法得到一些单词，比如"Almofada“。
package ArrayLists;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class ArrayList2 {
public static void main(String[] args) {
//arraylist pr
浏览 0提问于2020-05-14得票数 3
回答已采纳
7回答
我试图迭代一个列表，而它已经循环了(嵌套循环)。考虑下面的守则：
ArrayList<Integer> list = new ArrayList<Integer>(); // add some values to it
for(int i : list) { // ConcurrentModificationException
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
int n = iterator.next();
if(n % i =
浏览 5提问于2012-09-27得票数 4
回答已采纳
所以我正在尝试创建这个循环，它可以从数组列表中删除给定字符串中的特定字符。问题是，当一行中有两个相同的字符时，它会错过第二个字符，因为当第一个字符被移除时，第二个字符会被下推到数组列表中的一个点上。这就是我到目前为止所拥有的。有人知道怎么解决这个问题吗？我仍然是java的初学者，所以如果有任何帮助，我将不胜感激。
ArrayList<Character> list = new ArrayList();
String string = "BuBBuopB";
for(int i=0;i<string.length();i++)
list.add(string.
浏览 1提问于2017-04-19得票数 0
我发现iterator.remove()显然有o(n)的复杂度。任何人都知道有一种方法可以过滤列表，同时避免在不使用iterator.remove()的情况下使用ConcurrentModificationException。
以下是显示不同之处的代码片段。它创建一个很大的数组列表，然后使用it.remove()从中间删除其中的大部分。然后，它从一开始就做同样的事情。在我的机器上，它是这样的:第一次测试699962ms，第二次测试329181ms
显然有很大的不同
package src;
import java.util.*;
import java.lang.*;
class Main
浏览 12提问于2017-09-18得票数 0
1回答
对于两个散列整数集，Java的分离()方法的大O/时间复杂度是什么？
我不确定是O(1)还是O(n)。
我知道哈希集包含的是O(1)操作，但我不确定不相交的操作是否遍历set 1的所有元素，并检查set 2是否包含这些元素。
浏览 2提问于2020-05-20得票数 0
回答已采纳
3回答
如何删除列表中的项目？
、、、
我有两个嵌套循环中的列表，当我在内部匹配一个项时，我想删除它，这样性能就会提高。
List<String[]> brandList = readCsvFile("/tmp/brand.csv");
List<String[]> themeList = readCsvFile("/tmp/theme.csv");
for (String[] brand : brandList) {
for (String[] theme : themeList) {
if (brand[0].equals(theme[0])) {
浏览 0提问于2016-02-13得票数 0
回答已采纳
3回答
我有一个奇怪的问题，我知道周围的工作，但我想用数组列表这一次。问题是:我有一棵员工树。Employee是一个简单的类(在为该雇员工作的员工列表下)：
class Employee
{
String name;
ArrayList<Employee> under = new ArrayList<Employee>();
//fire function
}
我的任务是递归地解雇所有没有雇员的员工。我知道如何处理定制的列表数据结构，但是我想用数组列表来实现。到目前为止，我的代码如下：
public boolean Fire()
{
if (u
浏览 4提问于2013-05-03得票数 0
回答已采纳
当isActive为false时，我试图删除一个实体。当实体属性isActive设置为false时，它输入if语句并删除该实体，然后再迭代实体列表，然后崩溃。根据我的研究，我正在使用正确的方法从数组列表中删除一个对象。
删除实体和遍历列表时的代码是
for (Entity entity : entities) {// itaarate through all the entities in list of entities
entity.render(shader, camera, this);// render each entity
if (!e
浏览 4提问于2020-03-24得票数 0
回答已采纳
我在我的android应用程序中有以下代码：
/**
* callback executed after fetching the data.
*/
public void OnPointsFetch(ArrayList<Shop> result) {
toggleLoader(false);
this.shops = result;
if(activeFilter == Constants.POINTS_FILTER_AVAILABLE){
for(Shop s : result){
if(s.getCli
浏览 0提问于2012-11-24得票数 19
回答已采纳
在C++中，我有时会将对象存储在链接列表中。我会将对象与指向其位置的迭代器关联起来。然后，给定迭代器，我可以在O(1)时间内从链接列表中删除对象。操作是O(1)，因为列表只更新指向列表中前一个和下一个元素的指针。我所说的C++方法：
是否有一种方法可以在Java中使用相同的O(1)复杂度来实现这一点？
LinkedList似乎改变了后续元素：
也许有一个不同的Java类来实现这一点？
谢谢
浏览 2提问于2016-04-16得票数 1
回答已采纳
原始问题:
最初，我希望减少(1) MyLinkedList中的所有元素。但是，由于我不能在MyLinkedList中使用foreach循环，所以我首先将MyLinkedList中的所有元素转移到ArrayList中，然后对所有元素进行了减少(1)。但问题是，我想每秒钟做一次减少运算。
input : 5-6-7
output : 1 second : 4-5-6
2 second : 3-4-5 ...
我的问题:
我的代码的问题是:对于ArrayList的ith元素，它每秒减少(1)。
input : 5-6-7
output : 1 second 4-6-7
浏览 3提问于2015-02-24得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
