List集合以及它的实现类和队列、栈

List集合

Collection层次的结构接口中，一些允许有重复的元素，例如：List接口。而另外一些不允许有重复的元素，例如：Set接口。其中也分为了有序与无序的（存储顺序）。

在JDK中没有提供Collection接口的实现类，但是提供了更加具体的子接口（如Set、List和Queue接口）。

现在我们具体看一下List接口的特点。

List接口的介绍

List接口是位于java.util包下的一个Collection子接口，是单列集合的一种，通常情况下我们会将所有实现了List接口的对象都称为List接口。

List接口的特点：

• List接口中的元素存取是有序的，按照线性方式进行存储。例如：按照 a、b、c进入，也按照a、b、c取出。
• List集合是带有索引的集合，通过索引可以更精确的操作集合中的元素（与数组的索引类似）
• List集合中的元素可以重复。

LIst接口中的常用方法

List接口是Collection集合中的子接口，不仅继承了Collection集合中的全部方法，而且还增加了一些根据元素索引操作集合的特有方法。

Collection集合中的方法详见：Collection集合以及方法

List集合中的特有方法：

1、添加元素

• void add(int index,E ele)：在指定索引位置添加元素ele
• boolean addAll(int index,Collection<? extends E> eles)：在指定位置添加一个集合eles中的所有元素(<? extends E>表示泛型上限)

2、获取元素

• E get(int index)：获取List集合中指定索引位置的元素
• List subList(int fromIndex,int toIndex)：获取List集合中指定片段[fromIndex,toIndex)的索引

3、获取元素索引

• int indexOf(Object obj)：获取指定元素的第一个索引
• int lastIndexOf(Object obj)：获取指定元素的最后一个索引

4、删除元素

• E remove(int index)：删除指定索引位置的元素，返回的是删除的元素的值

5、替换元素

• E set(int index,E ele)：将指定索引位置的元素替换为新的元素ele

代码测试：

public class ListMethod {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(123);
        list.add("abc");
        System.out.println("list = " + list); //list = [123, abc]

        list.add(1,"java");
        System.out.println("list = " + list); //list = [123, java, abc]

        List l = new ArrayList();
        l.add("list");
        l.add("set");
        list.addAll(2,l);
        System.out.println("list = " + list); //list = [123, java, list, set, abc]

        Object o = list.get(1);
        System.out.println("o = " + o); //o = java

        List subList = list.subList(1, 4);
        System.out.println("subList = " + subList); //subList = [java, list, set]

        int javaIndex = list.indexOf("java");
        System.out.println("javaIndex = " + javaIndex); //javaIndex = 1

        list.add("java");
        int javaLastIndex = list.lastIndexOf("java");
        System.out.println("javaLastIndex = " + javaLastIndex); //javaLastIndex = 5

        Object remove = list.remove(4);
        System.out.println("remove = " + remove); //remove = abc
        System.out.println("list = " + list); //list = [123, java, list, set, java]

        list.set(4,"spring");
        System.out.println("list = " + list); //list = [123, java, list, set, spring]
    }
}

结果演示：

List集合的遍历方法

在List集合中除了Collection集合中的Iterator迭代器和增强for循环两种遍历方式外还增加了另外两种迭代器方式：普通for循环和ListIterator迭代器。

• Iterator迭代器

public class GetEleTest {
    public static void main(String[] args) {

        List list = new ArrayList();
        list.add("iterator");
        list.add("foreach");
        list.add("for");
        list.add("ListIterator");

        Iterator iterator = list.iterator();
        while (iterator.hasNext()){ //iterator foreach for ListIterator 
            String element = (String) iterator.next();
            System.out.print(element+" "); 
        }
    }
}

• 增强for

public class GetEleTest {
    public static void main(String[] args) {

        List list = new ArrayList();
        list.add("iterator");
        list.add("foreach");
        list.add("for");
        list.add("ListIterator");

        for (Object element : list){ //iterator foreach for ListIterator 
            String string = (String) element;
            System.out.print(string + " ");
        }
    }
}

• 普通的for循环

因为List集合中提供了根据索引操作元素的方法，所以可以通过使用get(index)方法来进行获取元素值并遍历

public class GetEleTest {
    public static void main(String[] args) {

        List list = new ArrayList();
        list.add("iterator");
        list.add("foreach");
        list.add("for");
        list.add("ListIterator");

        for (int i = 0; i < list.size(); i++) { //iterator foreach for ListIterator 
            System.out.print(list.get(i)+" ");
        }
    }
}

• ListIterator迭代器
  除了上面三种的遍历方式，LIst集合还提供了一种专门用于遍历LIst集合的方式：listIterator()，该方法返回了一个列表的迭代器对象，ListIterator是一个接口，该接口继承了Iterator接口，里面封装了一些特有的方法。

• void add()：铜鼓迭代器添加元素到对应的集合

• void set(Object obj)：通过迭代器替换正在迭代的元素

• void remove()：通过迭代器删除刚迭代的元素

• boolean hasNext()：判断是否有下一个元素

• boolean hasPrevious()：往前遍历，判断是否有前一个元素

• Object next()：获取下一个元素

• Object previous()：获取前一个的元素

• int nextIndex()：向后遍历，返回元素的索引

• int previousIndex()：向前遍历，返回元素的索引

public class GetEleTest {
    public static void main(String[] args) {

        List list = new ArrayList();
        list.add("iterator");
        list.add("foreach");
        list.add("for");
        list.add("ListIterator");

        ListIterator listIterator = list.listIterator();
        while (listIterator.hasNext()){
            System.out.print(listIterator.nextIndex());
            String next = (String) listIterator.next();
            System.out.print(":"+next+" ");
        }
        System.out.println();
        while (listIterator.hasPrevious()){
            System.out.print(listIterator.previousIndex());
            Object previous = listIterator.previous();
            System.out.print(":" +previous+" ");
        }
    }
}

List接口的实现类

ArrayList集合

ArrayList集合是List接口的典型实现类，底层使用的是长度可变的数组,ArrayList集合中的元素可以为空。

因为ArrayList集合的底层使用的动态数组进行存储数据，所以ArrayList集合的查询元素效率较快，但是增、删较慢。

ArrayList集合的底层实现：

ArrayList没有自己特殊的方法，常用的方法都是来自于Collection集合和List集合

Collection集合中的方法详见：Collection集合以及方法

ArrayList集合与Vector集合进行比较，两者都是使用的动态数组，但是ArrayList集合线程不安全，效率相对较高，Vector集合线程安全，基本上里面的每一个方法都有synchronized，所以效率相对较低。

ArrayList和Vector底层分析：

ArrayList底层实现：可变长的数组，有索引，查询效率高，增删效率低
    构造方法：
            new ArrayList（）：
                    jdk6中，空参构造直接创建10长度的数组。
                    jdk7(新版)、jdk8中，默认初始容量0，在添加第一元素时初始化容量为10
             new ArrayList(int initialCapacity):
                    指定初始化容量
    添加元素：add(E e);
    	首次添加元素，初始化容量为10
        每次添加修改modCount属性值
        每次添加检查容量是否足够，容量不足时需要扩容，扩容大小为原容量的1.5倍
        如果添加的元素容量大于原容量的0.5倍，则直接以添加元素的容量作为扩容的容量大小
    移除元素：remove(E e);
        每次成功移除元素，修改modCount值
        每次成功移除需要需要移动元素，以保证所以元素是连续存储的（删除操作效率低的原因）
------------------------------
Vector实现类的不点：
	初始容量为10，容量不足时扩容，如果capacityIncrement为0 扩容增加为原来的2倍,否则容量为旧的长度+capacityIncrement。

LinkedList实现类

LinkedList类是另一个List接口的常用实现类

因为LinkedList集合的底层使用的双向链表结构,所以LinkedList集合的特点是增删快，但是查询慢。

LinkedLIst集合的底层结构：

LinkedList集合的底层源码实现

LinkedList集合特有的操作首尾元素的方法：
首尾元素的操作效率高

• void addFirst(Object obj)：在链表的首节点添加一个元素
• void addLast(Object obj)：在链表的添加元素
• Object getFirst()：获取链表首节点的元素
• Object getLast()：获取链表尾结点的元素
• Object removeFirst()：移除链表首节点的元素
• Object removeLast()：移除链表尾结点的元素

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Object> linkedList = new LinkedList<>();
        linkedList.add("linkedList");
        System.out.println("linkedList = " + linkedList); //[linkedList]
        linkedList.addFirst("ArrayList");
        System.out.println("linkedList = " + linkedList); //[ArrayList, linkedList]
        linkedList.addLast("Vector");
        System.out.println("linkedList = " + linkedList); //[ArrayList, linkedList, Vector]

        Object o = linkedList.get(1);
        System.out.println("o = " + o); //linkedList
        Object first = linkedList.getFirst();
        System.out.println("first = " + first); //ArrayList
        Object last = linkedList.getLast();
        System.out.println("last = " + last); //Vector

        Object remove = linkedList.remove(1);
        System.out.println("remove = " + remove); //linkedList
        System.out.println("linkedList = " + linkedList); //[ArrayList, Vector]
        Object removeFirst = linkedList.removeFirst();
        System.out.println("removeFirst = " + removeFirst); //ArrayList
        System.out.println("linkedList = " + linkedList); //[Vector]
        Object removeLast = linkedList.removeLast();
        System.out.println("removeLast = " + removeLast); //Vector
        System.out.println("linkedList = " + linkedList); //[]
    }
}

队列与栈

队列和栈都属于逻辑结构的一种，属于特殊的线性结构，其物理结构可以是数组，也可以是链表。

LinkedList也实现了Deque接口（双端队列），Deque接口提供了实现队列和栈结构的方法。

Stack是Vector的子类，Stack也是实现了栈结构，它是数组实现的栈结构

队列

队列(Queue)是一种（并非一定）先进先出（FIFO）的结构

public class QueueAndDequeTest {
    public static void main(String[] args) {
        //LinkedList实现了Deque，Deque又继承了Queue
        Queue queue = new LinkedList();
        queue.add("queue");
        System.out.println("queue = " + queue); //[queue]
        Object element = queue.element();
        System.out.println("element = " + element); //queue
        Object remove = queue.remove();
        System.out.println("remove = " + remove); //queue
        System.out.println("queue = " + queue); //[]

        boolean dequeBoolean = queue.offer("deque");
        System.out.println("dequeBoolean = " + dequeBoolean); //true
        System.out.println("queue = " + queue); //[deque]
        Object peek = queue.peek();
        System.out.println("peek = " + peek); //deque
        System.out.println("queue = " + queue); //[deque]
        Object poll = queue.poll();
        System.out.println("poll = " + poll); //deque
        System.out.println("queue = " + queue); //[]
    }
}

栈

栈是一种先进后出（FILO）或后进后进先出（LIFO）的结构。
Deque，名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：文章来源地址https://www.toymoban.com/news/detail-412271.html

    @Test
    public void test02(){
        //模拟栈操作
        LinkedList<String> stack = new LinkedList<>();

        //入栈
        stack.push("张三");
        stack.push("李四");
        stack.push("王五");
        stack.push("赵六");

        //删除栈顶元素 弹栈
        stack.pop();
        stack.pop();

        //获取栈顶元素
        Object peek = stack.peek();
        System.out.println("peek = " + peek);
    }

到了这里，关于List集合以及它的实现类和队列、栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！