java

1. ArrayList

1.1 特点 2. linkedList

2.1 用法

2.1.1 创建方式2.1.2 Queue接口定义2.1.3 Queue举例2.1.4 Deque举例 2.2 特点 3. ArrayDeque

3.1 实例变量

3.2 原理3.2.1 循环数组3.2.2 构造方法3.2.3 头部添加和删除 3.3 特点

随机访问效率很高，但插入和删除性能比较低

linkedList同样实现了List接口，它的特点与ArrayList正好相反。同时还实现了Deque和Queue接口。可以按照队列、栈和双端队列的方式进行操作。

List list = new linkedList<> ();
List list1 = new linkedList<> (Arrays.asList (new String []{"a","b","c"}));

   public interface Queue extends Collection{
        boolean add(E e);//在尾部添加元素，队列满时抛异常
        boolean offer(E e);//在尾部添加元素，队列满时返回false
        E remove();//删除头部元素，队列空时抛异常
        E poll();//删除头部元素，队列空时返回null
        E element();//查看头部元素，队列空时抛异常
        E peek();//查看头部元素，队列空时返回null
    }

    Queue queue = new linkedList<> ();
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    while(queue.peek()!=null){
        System.out.println (queue.poll ());
    }

        Queue q = new linkedList<>();

        for (int i=0;i<5;i++){
            q.offer(i);
        }
        while (!q.isEmpty()) System.out.println(q.poll());
    }

    Deque stack = new linkedList<> ();
    stack.offer("a");
    stack.offer("b");
    stack.offer("c");
    while(stack.peek()!=null){
        System.out.println (stack.pop ());
    }

private transient E[] elements;
private transient int head;
private transient int tail;

ArrayDeque的高效来源于head和tail这两个变量。

对于一般的数组，比如arr ，第一个元素是arr[0],最后一个元素为arr[arr.length-1]。
但是ArrayDeque中的数组，他是一个逻辑上的循环数组，有head和tail这两个变量决定
a.当head=tail，则数组为空，长度为0；
b.当head c.当tail d.当0

public ArrayDeque(){
    elements = (E[])new Object[16];
}

分配了一个长度为16的数组。如果有参数numElements,代码为

public ArrayDeque(int numElements){
    allocateElements(numElements);
}

    public ArrayDeque(Collection c ){
        allocteElements(c.size ());
        addAll(c);
    }

关键方法

addFirst();
removeFirst();//removeFirst()主要调用了pollFirst()方法