基于API的类的学习day04——List

List(I):

1)特点:
?a.List是有顺序的接口,所以是有序列表,并且可以使用index定位
?b.List允许有重复值
?c.List中允许有null

2)常用API(只要带有index,都是List新增的方法):
?void add(int index, E element)
?boolean addAll(int index, Collection<? extends E> c)
?E get(int index)
?int lastIndexOf(Object o)
?E remove(int index)
?E set(int index, E element)
?List subList(int fromIndex, int toIndex) - 截取子集合

3)常见实现类:
?(1)ArrayList( C ):
?a.底层数据结构:顺序结构
?b.底层实现:数组
?c.特点:
??①.按照顺序排列,每个元素都带有标号
??②.除了有标号是连续的,内存中的物理空间也是连续的
?d.优缺点:
??优点: 查询速度快(因为有连续的下标,可以根据下标进行查询)
??缺点:
???a.插入/删除速度慢(插入/删除都是要移动元素的,所以元素一多就会执行效率慢)
???b.内存的物理空间是连续的,利用不到碎片空间

Vector( C )

?a.底层数据结构:顺序结构
?b.底层实现:数组
?c.特点:
??①.全部和ArrayList一样
??②.Vector上带有线程同步锁(synchronized),所以是线程安全的,效率低
?d.优缺点:全部和ArrayList一样

LinkedList( C )

?a.底层数据结构:链式结构
?b.底层实现:Node节点(data[数据] + next[下一个节点的引用])
?c.特点:
??①.LinkedList是双向链表
??①.链表是内存中固定顺序,但是他的物理空间不连续
??②.没有下标
??③.所有节点的访问,都必须通过头节点(next)/尾节点(pre)
??④.head(头节点): 只存next,不存data
???last(尾节点): 只存pre,不存data
??⑤.head.next = null -> 空链表
???last.pre = null -> 空链表

?d.优缺点:
??优点:
???a.插入/删除效率高
???b.不需要连续的内存物理空间,所以空间利用率高
??缺点:
???查询效率低,只能从头节点出发开始查询

?e.LinkedList独有的API:
?(只要带有First/last的方法)
?void addFirst(E e)
?void addLast(E e)
?E getFirst()
?E getLast()
?E remove(int index)
?E removeFirst()
?E removeLast()