List接口简介
List接口常用的集合类有ArrayList(数组列表)、LinkedList(链表)、Vector(可变组数)和Stack(栈)。
List集合共有的操作分类
其实List集合说到底也不过是存放数据的容器,因此我们可以类比数据库,将对集合的操作方法分为增、删、改、查四大类。这些方法适用于List的任一个实现类(Stack通过继承Vector间接实现了List接口,但是它应该使用另一套方法,我们会在后文叙述)。
添加:
boolean add(E e) 添加元素成功返回True
void add(int index,E element)在指定位置添加元素(零起)
-
boolean addAll(Collection<? extends E> c)将自定集合的所有元素添加到此集合中。
ps:参数Collection<? extends E> c所有实现Collection的类。
查询:
E get(int index) 返回指定位置的元素
** int indexOf(Object o)** 找到第一次出现此元素的位置,不存在返回-1
boolean contains(Object o) 此集合包含此元素,则返回True。
boolean containsAll(Collection<?> c) 此集合包含指定集合的所有元素则返回True
boolean isEmpty() 此结合不包含元素(为空)则返回True
int size() 返回集合中的元素数
Object[] toArray() 返回包含所有元素的数组
删除:
void clean() 删除集合中的所有元素
boolean remove(Object o) 根据内容移除指定元素(第一次出现的)
E remove(int index)删除列表中指定位置的元素
boolean removeAll(Collection<?> c)移除指定集合中包含的所有元素
retainAll(Collection<?> c)与上面是正好相反的,保留指定集合中的所有元素(其他移除)
修改:
- E set(int index, E element) 用指定元素替代该位置的元素
让我们来简单地实践一下:
import java.util.List;
public class ListTest {
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
System.out.println("list1:"+list1);
List<Integer> list2 = new LinkedList<>();
list2.add(4);
list2.add(5);
list1.addAll(list2);
System.out.println("List1+list2:"+list1);
list1.add(3,66);
System.out.println("Insert 66 to 3th:"+list1);
System.out.println("Get 4th element from list1:"+list1.get(3));
System.out.println("If list1 contains 77?"+list1.contains(77));
System.out.println("If list1 contains list2?"+list1.containsAll(list2));
System.out.println("If list1 is empty?"+list1.isEmpty());
System.out.println("List1's size?"+list1.size());
System.out.println("Get 5th element from list1:"+list1.toArray()[5]);
list1.remove(2);
System.out.println("Remove 3rd element:"+list1);
list1.remove(new Integer(5));//[1]
System.out.println("Remove element '5' from list1:"+list1);
List<Integer> list3 = new Stack();
list3.add(1);list3.add(2);
list1.retainAll(list3);
System.out.println("Retain list2's element in list1:"+list1);
list1.set(1,77);
System.out.println("Set 2nd element of value 77:"+list1);
list1.clear();
System.out.println("If list1 is empty?"+list1.isEmpty());
}
}
输出结果:
list1:[1, 2, 3]
List1+list2:[1, 2, 3, 4, 5]
Insert 66 to 3th:[1, 2, 3, 66, 4, 5]
Get 4th element from list1:66
If list1 contains 77?false
If list1 contains list2?true
If list1 is empty?false
List1's size?6
Get 5th element from list1:5
Remove 3rd element:[1, 2, 66, 4, 5]
Remove element '5' from list1:[1, 2, 66, 4]
Retain list2's element in list1:[1, 2]
Set 2nd element of value 77:[1, 77]
If list1 is empty?true
上边的例子为了打字流畅,选择用了蹩脚的引文来做输出的注释,但是大家应该都看得懂把(→ →)
为了说明LinkedList、LinkList、Stack都实现了List接口,我例子用的list1、list2和list、分别使用了它们向上转型。
值得注意的是例子中标【1】的地方,这个地方使用了Integer类作为参数传入,以防止remove方法判断我传入的是用来表示位置的整型,而在前边的add方法中因为不会混淆,直接使用整型作为参数传入,它会被自动装箱为Integer类型。
使用的方法我们大致了解了,接下来我们看看它们的特性:
ArrayList
- ArrayList是基于数组实现的
- 获取和修改元素get、set都是固定时间运行的,所以时间复杂度都为O(1)
- 添加和删除元素操作时间复杂度为O(n),因为ArrayList插入的时候,在插入元素后边的所有元素都要向后移动,因此,插入的位置约靠后,需要的时间就越少,同理,删除
- 扩容机制:如果一开始不指定其实容量,先是10,而后每次扩充1.5倍
- 线程不安全,如果需要多个线程访问,可以在使用Collection.synchronizeList方法包装,如:
List list = Collection.synchronizeList(new ArrayList(...))
LinkedList
- LinkedList是基于双链表实现的,共三个元素,前后分别为前后一个单位的引用,中间为本单位元素
- 获取元素较ArrayList慢,因为要沿着索引查找
- 添加和删除较ArrayList快,因为不涉及内容的移动,只需要沿着索引找到位置就可以快速添加和删除,且不存在容量问题,ArrayList容量满之后要移动整个数组到新的地址
- 线程不安全,可以和ArrayList使用同样的方法保证线程安全
- 除了实现List接口的方法之外,还有两个自己的添加元素方法void addFirst(E e)和void addLast(E e)分别为在头和尾添加元素
ps:其实看了源码就会发现,add(E e)的实现就是addLast(E e)的基础上加了 return true;)
Vector
- 可以看做是线程安全的ArrayList,为了线程安全,各项性能都比ArrayList稍差。
Stack
栈,相信大家很熟悉了,但是它居然也是List接口的实现类,不知道大家怎么想,反正我刚开始知道的时候就很惊讶(看源码才知道是因为它继承了Vector),但是栈不推荐使用List接口的方法(jdk文档里也没写,但是能用),而是有自己的方法对自身操作:
- boolean empty()堆栈为空返回true
- E peek()返回顶部对象
- E pop()返回顶部对象并在栈中删除
- E push(E item)将对象推到此堆栈顶部(返回的也是推进去的对象)
- int search(Object o)返回对象