JAVA栈和队列的表示-LinkedList

Java中实现栈和队列操作都可以通过使用linkedList类实现：

结论：linkedList是一种常用的数据容器，与ArrayList相比，linkedList的增删操作效率相对较高，而查改操作效率较低。

1、linkedList是通过双向链表实现的，创建linkedList时，存入了首尾节点first last以及链表长度size，可以直接调用。
linkedList结构：

public class linkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable{
    transient int size = 0;
    transient Node first;
    transient Node last;
    public linkedList() {
    }
    
    public linkedList(Collection c) {
        this();
        addAll(c);
    }
}

Node结构：

private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

读写（改查）效率低：
查：get(int index)
get(int index)方法是通过**node(int index)**来实现的，它的实现机制是比较传入的索引参数index与集合长度size/2，如果是index小，那么从第一个节点顺序循环，直到找到为止；如果index大，那么从最后一个倒序循环，直到找到为止。越靠近中间的元素，调用get(int index)方法执行的次数越多，效率也就越低。
因此在使用linkedList的时候，我们不建议使用这种方式读取数据，可以使用getFirst()，getLast()方法，将直接用到类中的first和last变量。
改类似：set(int index, E element)

增删效率高：
增：add(E e) 和 add(int index, E element)；
add(E e) 新建一个Node实体，同时指定其prev和next
add(int index, E element)，与add(E e)不同的是，需要先调用**node(int index)**通过传入的index来定位到要插入的位置（返回当前索引对应的node，调用了linkedList的查找方法，这个方法也比较耗时）。
但是它省去了ArrayList插入数据可能的数组扩容和数据元素移动时所造成的开销，插入效率高是相对的。
删除类似: remove(Object o)和remove(int index).

常用方法：
读写
增删
遍历：三种方法：普通for循环，增强for循环，Iterator迭代器
Java集合 linkedList的原理及使用

public E removeFirst() 移除LIst第一个元素 返回移除元素的值 : 从队列弹出
public E removeLast() 移除LIst最后一个元素 返回移除元素的值：从栈弹出

2、ArrayList
（待）