JAVA8 LinkedList学习笔记

向右看齐 2022-05-24 20:46 232阅读 0赞

### LinkedList ###

*  LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
 *  LinkedList 实现 List 接口，能对它进行队列操作。
 *  LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
 *  LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
 *  LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
 *  LinkedList 是非同步的

### 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;  
        //省略内部类和方法。。  
    }

### API ###

*  **add(E e)**

该方法直接将新增的元素放置链表的最后面，然后链表的长度（size）加1，修改的次数（modCount）加1

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

*  **add(int index, E element)**

指定位置往数组链表中添加元素

1.  检查添加的位置index 有没有小于等于当前的长度链表size，并且要求大于0
2.  如果是index是等于size，那么直接往链表的最后面添加元素，相当于调用add(E e)方法
3.  如果index不等于size，则先是索引到处于index位置的元素，然后在index的位置前面添加新增的元素

public void add(int index, E element) {
        checkPositionIndex(index);
    
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

*  **get(int index)**

首先是判断索引位置有没有越界，确定完成之后开始遍历链表的元素，那么从头开始遍历还是从结尾开始遍历呢，这里其实是要索引的位置与当前链表长度的一半去做对比，如果索引位置小于当前链表长度的一半，否则从结尾开始遍历

Node<E> node(int index) {
        // assert isElementIndex(index);
    
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }