首页 > 代码库 > 数据结构和算法分析 表、栈和队列
数据结构和算法分析 表、栈和队列
表是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方法。
数据结构和算法分析 表、栈和队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。