List集合以及Queue集合
一、List集合
List集合代表一个有序、可重复的集合,集合中每个元素有其对应的索引,根据元素的添加顺序设置元素的索引,第一个为0.
List是Collection的子接口,在Collection接口的方法基础上,添加了有关索引的方法
1.Collection接口操作方法
(1) boolean add(Object obj)
将Object对象添加到collection。
(2) boolean remove(Object obj)
如果collection中有与obj相匹配的对象,则删除该对象。
2.List新增方法
(1) void add(int index,Object obj)
将元素添加到索引为index处
(2)Object remove(int index)
删除并返回index处的元素
List集合判断两个对象是否相等的标准是equals()方法,当调用remove(new A)方法时,会先去调用A对象的equals方法,然后依次与集合中的元素进行比较,一旦判断equals方法返回true,就删除第一个匹配的元素。
ArrayList和Vector实现类
这两个都是基于数组实现的list类,他们都是封装了一个动态的、允许再分配的Object[]数组,可以通过使用initialCapacity参数设置该数组长度,当向ArrayList和Vector添加的元素超过数组长度,他们的initialCapactiy会自动增加。我们可以再创建集合对象时候指定initialCapactiy的大小,如果不指定默认长度是10。
List l1 = new ArrayList<>();
List l2 = new ArrayList<>(19);
区别:
- Vector比较古老,很多方法的方法名比较长,且缺点比较多,尽量少用。
- -ArrayList是线程不安全的(可以用Collections工具类将其变成安全),Vector是线程安全的,所以性能较差。
- Vector提供Stack子类,用于模拟栈,由于Stack继承了Vector,因此比较古老,线程安全,性能较差,尽量少用Satck,可用ArrayDeque实现模拟栈。
二、Queue集合
Queue接口常用方法
void add(Object e)
指定元素加入队列尾部,但是如果队列满了,会有异常
boolean offer(Object e)
指定元素加入队列尾部,但如果队列满了不会报异常,而是返回false
Object element()
获取队列头部的元素,但是不删除该元素,如果队列为空报异常
Object peek()
获取队列头部的元素,但是不删除该元素,如果队列为空返回null
Object remove()
获取队列头部的元素,并删除该元素,如果队列为空报异常
Object poll()
获取队列头部的元素,并删除该元素,如果队列为空返回null
2.1PriorityQueue实现类
该队列保存的元素并不是元素加入的顺序,而是会按队列元素大小进行重新排序,因此当调用peek()或者poll()是队列中最小的元素。
2.2Deque接口以及ArrayDeque实现类
Deque是Queue子接口,它代表双端队列(允许从两端操作队列),既可以模拟栈也可以模拟队列。(由于是双端,方法中可操作第一个也可操作最后一个)
模拟队列
boolean offerFirst(Object e)
指定元素加入双端队列开头,但如果队列满了不会报异常,而是返回false
boolean offerLast(Object e)
指定元素加入双端队列末尾,但如果队列满了不会报异常,而是返回false
Object peekFirst()
获取双端队列第一个元素,但是不删除该元素,如果队列为空返回null
Object peekLast()
获取双端队列最后一个元素,但是不删除该元素,如果队列为空返回null
Object pollFist()
获取双端队列第一个元素,并删除该元素,如果队列为空返回null
Object pollLast()
获取双端队列最后元素,并删除该元素,如果队列为空返回null
模拟栈
Object pop()
pop出双端队列所代表的栈的栈顶元素
void push(Object e)
将一个元素push进双端队列所代表栈的栈顶
ArrayDeque是Deque接口的一个实现类,它也是基于动态的、可重分配的Object[]数组。当需要栈时推荐使用ArrayDeque,尽量避免用Stack。当然ArrayDeque由于是双端队列,也可以当成队列来使用。
public class ArrayDequeQueue {
public static void main(String[] args) {
ArrayDeque queue = new ArrayDeque();
queue.offer("1");
queue.offer("2");
queue.offer("3");
System.out.println(queue);
System.out.println(queue.peek());
queue.poll();
System.out.println(queue);
}
}
[1, 2, 3]
1
[2, 3]
public static void main(String[] args) {
ArrayDeque stack = new ArrayDeque();
stack.push("1");
stack.push("2");
stack.push("3");
System.out.println(stack);
System.out.println(stack.peek());
stack.pop();
System.out.println(stack);
}
[3, 2, 1]
3
[2, 1]
这里我发现一个问题就是把stack.pop()改成stack.poll()程序结果跟上面一样。pop是代表出栈的第一个元素,poll是出队列的第一个元素,而程序并不知道栈和队列是什么,即使我们在我们认为的栈里用了队列的方法,他们也只是根据哪个方法是用,比如上面栈中用了stack.poll(),他们就会删除队列的头部的那个元素,用了stack.pop()他们就会删除栈顶元素,而他们删的都是同一个元素,代表他们都认为当我们添加所有元素进去集合后,排在第一个元素处就是栈顶或者队列。因此stack.poll()删除队首元素,即第一个元素3.stack.pop()删除栈顶元素,即第一个元素3。因此我们要知道第一个元素的位置就是他们认为的栈顶或者队首,而最后一个元素就是队尾(非双端队列知道队尾也不能操作)即可–当双端队列使用pollFirst/poll代表出队首元素,即第一个元素,pollLast代表出队尾元素,即最后一个元素(当然拉,非双端队列只能用poll,即出队首元素–第一个元素)。例子留到下面LinkedList举例
三、LinkedList实现类
LinkedList是List接口的实现类,因此可用索引来进行随机访问集合中的元素,它还实现了Deque接口,因此他也是可用被当成双端队列来使用,因此即可模拟栈,又可模拟队列。
public static void main(String[] args) {
LinkedList books = new LinkedList();
books.offer("1");
books.push("2");
books.offerFirst("3");
for (int i=0;i<books.size();i++){
System.out.print(books.get(i)+" ");
}
System.out.println("栈顶元素/队首元素"+books.peekFirst());
System.out.println("队尾元素"+books.peekLast());
System.out.println("栈顶元素弹出"+books.pop());
for (int i=0;i<books.size();i++){
System.out.print(books.get(i)+" ");
}
System.out.println();
books.offerLast("4");
System.out.println("向队尾加入一个元素");
for (int i=0;i<books.size();i++){
System.out.print(books.get(i)+" ");
}
System.out.println();
System.out.println("出队尾元素:"+books.pollLast());
for (int i=0;i<books.size();i++){
System.out.print(books.get(i)+" ");
}
}
3 2 1 栈顶元素/队首元素3
队尾元素1
栈顶元素弹出3
2 1
向队尾加入一个元素
2 1 4
出队尾元素:4
2 1
ArrayList ,Vector, ArrayDeque(其中Vector是线程安全的,性能较差)都是用动态数组形式来保存元素的,随机访问元素时有较好的性能。而LinkedList是以链表形式来保存元素的,因此随机访问元素性能较差,但插入删除时性能出色。
总结:
ArrayList与LinkedList是线性表的典型实现,前者数组实现,后者链表实现。数组随机访问时性能最好,链表插入删除时性能好,但总体来说ArrayList的性能比LinkedList性能好。
Queue代表队列,而Deque作为其子接口具有双端功能,即可模拟栈也可以模拟队列,而LinkedList继承了Deque接口因此也具有双端队列、栈的功能。
推荐阅读
-
JAVA集合学习Queue
-
Java集合框架-Queue
-
Queue集合
-
List集合以及Queue集合
-
SharedPreferences 存List集合,模拟数据库,随时存取
-
Java总结05 Java集合体系.最高集合接口Collection和其迭代器/一般集合接口List和其迭代器/增强版For循环的应用
-
Java学习Day07------集合,迭代器,List集合
-
单列集合Collection-------------List和Set
-
小王说来来斗地主,但是木有牌,怎么办-------模拟斗地主洗牌和发牌 对牌进行排序 并同时使用Map,List,Set等集合
-
Java集合 ——List 接口