集合——list

list

list是Collection的子接口

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

与 set 不同，列表通常允许重复的元素

List：支持角标操作，允许重复元素，允许null元素，一维数据实现

在集合类中，List是最基础的一种集合：它是一种有序列表。

List的行为和数组几乎完全相同：List内部按照放入元素的先后顺序存放，每个元素都可以通过索引确定自己的位置，List的索引和数组一样，从0开始。

public class CollectionDemo02 {
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            list1.add(0, i);
        }
        System.out.println(list1.get(3));
        System.out.println(list1.indexOf(10));  //从左到右第1个
        System.out.println(list1.lastIndexOf(1));   //从右到左第1个
        List<Integer> list2 = list1.subList(0, 4);   //[0,4)  实际上 0,1,2,3
        System.out.println(list2);

        Iterator<Integer> it1 = list1.iterator();   //从角标-1开始
        ListIterator<Integer> it2 = list1.listIterator();   //从角标-1开始
        ListIterator<Integer> it3 = list1.listIterator(4);
        //Iterator : 最好只用来遍历 单向遍历
        //ListIterator : 用来遍历 双向遍历 修改元素
        /*
        listIterator() 默认位置在角标-1 只能向后走 next 向前走previous没有元素的
        listIterator(list1.size()) 默认位置在最后 只能向前走 previous 向后走next没有元素的
        遍历一个副本，遍历的过程中可以对源数据进行增删改操作

        */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

ArrayList

在实际应用中，需要增删元素的有序列表，我们使用最多的是ArrayList。实际上，ArrayList在内部使用了数组来存储所有元素。ArrayList是一个初始容量为 10 的空列表

ArrayList把添加和删除的操作封装起来，让我们操作List类似于操作数组，却不用关心内部元素如何移动。

大小可变数组的实现
并允许包括 null 在内的所有元素 允许重复元素
不同步的 线程不安全 函数没有同步关键synchronized - 适用于单线程情况

List接口，可以看到几个主要的接口方法：

• 在末尾添加一个元素：boolean add(E e)
• 在指定索引添加一个元素：boolean add(int index, E e)
• 删除指定索引的元素：E remove(int index)
• 删除某个元素：boolean remove(Object e)
• 获取指定索引的元素：E get(int index)
• 获取链表大小（包含元素的个数）：int size()

ArrayList<Integer> list1 = new ArrayList<>();   //默认容量为10
ArrayList<Integer> list2 = new ArrayList<>(20);//指定容量为20
ArrayList<Integer> list3 = new ArrayList<>(list2);
System.out.println(list1.size());
System.out.println(list2.size());
        for (int i = 1; i <= 12; i++) {
            list1.add(i);   //动态扩容 超了 每次+1
        }
        list1.ensureCapacity(20);   //20 > 12 容量20
        list1.remove(0);
        list1.trimToSize(); //将列表的容量调整为元素的个数 容量12
1
2
3
4
5
6
7
8
9
10
11

LinkedList

实现List接口并非只能通过数组（即ArrayList的实现方式）来实现，另一种LinkedList通过“链表”也实现了List接口。

链接列表实现 双向循环链表 具有头尾指针的 first last
具有Queue队列功能 也具有Deque双端队列功能 也具有栈的功能

在LinkedList中，它的内部每个元素都指向下一个元素：

        ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
HEAD ──>│ A │ ●─┼──>│ B │ ●─┼──>│ C │ ●─┼──>│ D │   │
        └───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘
1
2
3

我们来比较一下ArrayList和LinkedList：

通常情况下，我们总是优先使用ArrayList。

把LinkedList作为栈来使用 push pop peek

LinkedList<Integer> stack = new LinkedList<>();
for (int i = 1; i <= 10; i++) {
stack.push(i);  //push 进栈 表头添加
}
System.out.println(stack);
System.out.println(stack.pop());    //pop 出栈 表头删除
System.out.println(stack);
System.out.println(stack.peek());   //peek 查看栈顶 查看表头

1
2
3
4
5
6
7
8
9

把LinkedList作为队列来使用 offer poll element

LinkedList<Integer> queue = new LinkedList<>();
for (int i = 1; i <= 10; i++) {
queue.offer(i);     //offer 进队 表尾添加
}
System.out.println(queue);
System.out.println(queue.poll());   //poll 出队 表头删除
System.out.println(queue);
System.out.println(queue.element());    //element 查看队首元素 查看表头
System.out.println(queue.pop());    //函数的调用一定注意语义
System.out.println(queue);
1
2
3
4
5
6
7
8
9
10

Vector

大小可变数组的实现
并允许包括 null 在内的所有元素 允许重复元素
同步的 线程安全 函数有同步关键synchronized - 适用于多线程情况

Vector 类实现了一个动态数组。和 ArrayList 很相似，但是两者是不同的：

• Vector 是同步访问的。
• Vector 包含了许多传统的方法，这些方法不属于集合框架。

Vector 主要用在事先不知道数组的大小，或者只是需要一个可以改变大小的数组的情况。

Vector 类支持 4 种构造方法。

第一种构造方法创建一个默认的向量，默认大小为 10：

Vector()
1

第二种构造方法创建指定大小的向量。

Vector(int size)
1

第三种构造方法创建指定大小的向量，并且增量用 incr 指定。增量表示向量每次增加的元素数目。

Vector(int size,int incr)
1

第四种构造方法创建一个包含集合 c 元素的向量：

Vector(Collection c)
1

Vector v = new Vector(3, 2);
      System.out.println("Initial size: " + v.size());
      System.out.println("Initial capacity: " +
      v.capacity());
      v.addElement(new Integer(1));
      v.addElement(new Integer(2));
      v.addElement(new Integer(3));
      v.addElement(new Integer(4));
      System.out.println("Capacity after four additions: " +
          v.capacity());

      v.addElement(new Double(5.45));
      System.out.println("Current capacity: " +
      v.capacity());
      v.addElement(new Double(6.08));
      v.addElement(new Integer(7));
      System.out.println("Current capacity: " +
      v.capacity());
      v.addElement(new Float(9.4));
      v.addElement(new Integer(10));
      System.out.println("Current capacity: " +
      v.capacity());
      v.addElement(new Integer(11));
      v.addElement(new Integer(12));
      System.out.println("First element: " +
         (Integer)v.firstElement());
      System.out.println("Last element: " +
         (Integer)v.lastElement());
      if(v.contains(new Integer(3)))
         System.out.println("Vector contains 3.");
      // enumerate the elements in the vector.
      Enumeration vEnum = v.elements();
      System.out.println("\nElements in vector:");
      while(vEnum.hasMoreElements())
         System.out.print(vEnum.nextElement() + " ");
      System.out.println();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Stack

栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。

只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）来

是Vector的子类 做为栈来使用的
大小可变数组的实现
并允许包括 null 在内的所有元素 允许重复元素
同步的 线程安全 函数有同步关键synchronized - 适用于多线程情况

Stack只有入栈和出栈的操作：

• 把元素压栈：push(E)；
• 把栈顶的元素“弹出”：pop()；
• 取栈顶元素但不弹出：peek()。

在Java中，我们用Deque可以实现Stack的功能：

• 把元素压栈：push(E)/addFirst(E)；
• 把栈顶的元素“弹出”：pop()/removeFirst()；
• 取栈顶元素但不弹出：peek()/peekFirst()。

为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque(允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名Deque)接口来“模拟”一个Stack了。

当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。

JVM会创建方法调用栈，每调用一个方法时，先将参数压栈，然后执行对应的方法；当方法返回时，返回值压栈，调用方法通过出栈操作获得方法返回值。

因为方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发StackOverflowError

利用Stack把一个给定的整数转换为十六进制：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String hex = toHex(12500);
        if (hex.equalsIgnoreCase("30D4")) {
            System.out.println("测试通过");
        } else {
            System.out.println("测试失败");
        }
    }

    static String toHex(int n) {
        return "";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在Java中，我们用Deque可以实现Stack的功能，注意只调用push()/pop()/peek()方法，避免调用Deque的其他方法。