美文网首页
JAVA LinkedList学习笔记

JAVA LinkedList学习笔记

作者: luoyoub | 来源:发表于2018-05-31 22:08 被阅读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;
        }
    }
    

    相关文章

      网友评论

          本文标题:JAVA LinkedList学习笔记

          本文链接:https://www.haomeiwen.com/subject/eemcsftx.html