欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

List集合以及Queue集合

程序员文章站 2024-03-18 11:17:52
...

一、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基础