JAVA栈和队列的表示-LinkedList

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

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

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

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
          
   
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    public LinkedList() {
          
   
    }
    /**
     * Constructs a list containing the elements of the specified collection,
     *  in the order they are returned by the collections iterator.
     */
    public LinkedList(Collection<? extends E> c) {
          
   
        this();
        addAll(c);
    }
}

Node结构：

private static class Node<E> {
          
   
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> 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迭代器

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