List接口

List 接口继承自 Collection 接口，其中定义了一个用于顺序存储元素的合集，我们可以使用它的两个具体类 ArrayList 或者 LinkedList 来创建一个 线性表

ArrayList和LinkedList

数组线性表类 ArrayList 和 链表 类 LinkedList 是实现 List 接口的两个具体类

ArrayList 用数组存储元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中，而 LinkedList 则是在一个链表中存储元素

要选用这两种类中的哪一个依赖于特定需求。如果需要通过下标随机访问元素，而不会在线性表起始位置插入或删除元素，那么 ArrayList 提供了最高效率的合集。但是，如果应用程序需要在线性表的起始位置上插入或删除元素，就应该选择 LinkedList 类

ArrayList 的 构造方法 和其特有方法：

LinkedList 的构造方法和其特有方法：

我们写一个程序来感受一下：

 import  java .util.*;

public class TestArrayAndLinkedList {
    public  static  void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add();
        arrayList.add();
        arrayList.add();
        arrayList.add();
        arrayList.add(, 10);
        arrayList.add(, 30);
        System.out.println("A list of integers in the array list:");
        System.out.println(arrayList);

        LinkedList<Object> linkedList = new LinkedList<>(arrayList);
        linkedList.add(, "red");
        linkedList.removeLast();
        linkedList.addFirst("green");
        System.out.println("Display the linked list backward:");
        for (int i = linkedList.size() -; i >= 0; --i) {
            System.out.print(linkedList.get(i) + " ");
        }
    }
}

运行结果如下：

Comparator接口

Java API 的一些类，比如 String 、 Date 、 Calendar 、 BigInteger 、 BigDecimal 以及所有基本类型的数字包装类都实现了 Comparator 接口。 Comparator 接口中定义了 compareTo 方法，用于比较实现了 Comparable 接口的同一个类的两个元素

如果元素的类没有实现 Comparable 接口又将如何呢？这些元素可以比较吗？我们可以定义一个 比较器 （ Comparator ）来比较不同类的元素。要做到这一点，需要创建一个实现 java.util.Comparator<T> 接口的类并重写它的 compare 方法

 public int compare(T element, T element2)

如果 element1 小于 element2 ，就返回一个负值；如果 element1 大于 element2 ，就返回一个正值；如果两者相等，则返回 0

线性表和合集的 静态方法

Collections 类（不是 Collection 接口）包含了执行合集和线性表中通用操作的静态方法

Collections 类包含用于线性表的 sort 、 binary Search 、 reverse 、 shuffle 、 copy 和 fill 方法，以及用于合集的 max 、 min 、 disjoint 和 frequency 方法，如下表所示

下面的代码是对线性表中的 字符串 进行排序：

 import java.util.*;

public class test {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("red", "green", "blue");
        Collections.sort(list);
        System.out.println(list);
    }
}

执行结果如下：

如果想要降序排列，我们可以简单地使用 Collection.reverseOrder() 方法，它会返回一个 Comparator 对象，该方法以逆序排列元素，下面是一段简单的降序排列的代码：

 import java.util.*;

public class test {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("red", "green", "blue");
        Collections.sort(list, Collections.reverseOrder());
        System.out.println(list);
    }
}

执行结果如下：

队列和优先队列

队列（ queue ）是一种先进先出的数据结构，元素被追加到队列末尾，然后从队列头删除。在优先队列（ priority queue ）中，元素被赋予优先级。当访问元素时，拥有最高优先级的元素最先被删除

将LinkedList作为队列使用

JFC 中并没有提供具体的队列类，而只是提供了 Queue 接口和 Deque 接口，而具体类 LinkedList 继承了 Deque 接口，而 Deque 接口又继承了 Queue 接口，事实上 LinkedList 可以作为队列使用

 import java.util.*;

public class TestQueue {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("red");
        queue.offer("green");
        queue.offer("blue");
        queue.offer("cyan");

        while (queue.size() >) {
            System.out.print(queue.remove() + " ");
        }
    }
}

执行结果如下：

实现栈和队列

需求：

• 实现栈 GenericStack ：

具体代码如下：

 import java.util.*;

public class  Generic Stack<E> {
     private  final ArrayList<E> list;

    public GenericStack() {
        list = new ArrayList<>();
    }

    public int getSize() {
        return list.size();
    }

    public E peek() {
        return list.get(getSize() -);
    }

    public void push(E o) {
        list.add(o);
    }

    public E pop() {
        E o = list.get(getSize() -);
        list.remove(getSize() -);
        return o;
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

• 实现队列 GenericQueue ：

具体代码如下：

 import java.util.*;

public class GenericQueue<E> {
    private final LinkedList<E> list;

    public GenericQueue() {
        list = new LinkedList<>();
    }

    public void enqueue(E e) {
        list.add(e);
    }

    public E dequeue() {
        return list.removeFirst();
    }

    public int getSize() {
        return list.size();
    }

    @Override
    public String toString() {
        return "GenericQueue{" +
                "list=" + list +
                '}';
    }
}

优先队列

PriorityQueue 类实现了一个优先队列，默认情况下，优先队列使用 Comparable 以元素的自然顺序进行排序，拥有最小数值的元素被赋予最高优先级，因此最先从队列中删除。如果几个元素具有相同的最高优先级，则任意选择一个，也可以使用构造方法 PriorityQueue(initialCapacity, comparator) 中的 Comparator 来指定一个顺序

运行实例：

 import java.util.*;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<String> q = new PriorityQueue<>();
        q.offer("red");
        q.offer("green");
        q.offer("blue");
        q.offer("cyan");
        System.out.println("Priority queue using Comparable:");
        while (q.size() > 0) {
            System.out.print(q.remove() + " ");
        }
        System.out.println();

        PriorityQueue<String> q = new PriorityQueue<>(4, Collections.reverseOrder());
        q.offer("red");
        q.offer("green");
        q.offer("blue");
        q.offer("cyan");
        System.out.println("Priority queue using Comparator:");
        while (q.size() > 0) {
            System.out.print(q.remove() + " ");
        }
        System.out.println();
    }
}

运行结果如下：