概述
LinkedList提供了List ADT的双链表实现,关于链表的概念参见wiki。
在之前的文章中介绍了基于数组的ArrayList,有一个重大缺点是插入和删除一个元素,会影响插入/删除位置之后的所有元素,而链表可以轻松完成插入删除动作。
给出java中LinkedList类图
实现
属性
头节点、尾节点、表的大小
|
|
Node是一个静态内部类,静态内部类的作用是把一个类隐藏在另一个类的内部,并不引用外部类对象。可以看做是一个独立的类。
|
|
add & remove
add方法将指定元素添加到链表末端
|
|
remove方法删除链表中第一次出现的指定元素
|
|
get
|
|
由此可见LinkedList对访问指定位置元素的效率不高,node方法先判断index位于表的前半部或后半部再遍历,复杂度O(n/2)
iterator
下面引用java核心技术中的一段话
由于迭代器是描述集合中位置的,所有依赖于位置的add方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。例如Set其元素完全无序,因此Iterator接口中就没有add方法。相反地,集合类库提供了子接口ListIterator,其中包含add方法……
ListIterator接口允许正向反向遍历表,在遍历时改变表结构,获取迭代器在表中的当前位置。
|
|
小结
LinkedList这种双向链表设计减少了添加、删除操作的开销,但如果需要对集合进行随机访问,那么使用数组或ArrayList是更好的选择。