首页 > 代码库 > 数据结构和算法分析 表、栈和队列

数据结构和算法分析 表、栈和队列

表是ArrayList,LinkedList,Stack,Queue的抽象定义。我理解为有序的单数据存储。

remove方法对LinkedList类的使用

模拟一个场景,遍历一个LinkedList,将其中存储的数值是偶数的都删除。

  • 方法一:通过下标i进行for循环,如果发现是偶数,然后使用remove(i)进行删除。这种方法的时间复杂度是O(N2),因为外层遍历的复杂度是N,内存要进行get(i)和remove(i)他们的复杂度都是N。
  • 方法二:使用增强for循环,会产生异常:增强for循环在循环的过程中,使用iterator,但是由于没有在iterator中使用remove,而是使用list.remove方法,这种是不会被iterator识别到的。所以有如下要求:增强型的for循环过程中,不能删除数据。
  • 方法三:使用iterator。iterator.hashNext, iterator.next, iterator.remove,因为iterator在remove的时候,已经定位到了要删除的链表元素位置,所以删除操作的复杂度为O(1),整个实现的时间复杂度为O(N)。

ListIterator

ListIterator在Iterator(hasNext,next,remove)的基础上增加了hasPrevious,previous,add,set方法。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

数据结构和算法分析 表、栈和队列