集合——LinkedList

  • LinkedList采用双向链表、双端队列实现,线程不安全
  • 举例说明
public class test {
    public static void main(String[] args) {
        //构造LinkedList对象
        LinkedList list = new LinkedList();
        for (int i=0 ;i < 10;i++){
            //添加数据
            list.add(i);
        }
        System.out.println(list);
    }
}
  1. LinkedList list =newLinkedList();
集合——LinkedList

 

2. list.add(i);

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //添加元素
    public boolean add(E e) {
        //看这
        linkLast(e);
        return true;
    }
}

3. linkLast(e);

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
      void linkLast(E e) {
        //得到尾节点,此时为空
        final Node<E> l = last;
        //实例化一个新的节点,存储要添加的数据。此时,pre和next都为null
        final Node<E> newNode = new Node<>(l, e, null);
        //尾节点指向这个新创建的节点
        last = newNode;
        //如果l为null(true),头节点指向这个新创建的节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    <span class="hljs-comment">//元素数量+1
    size++;
    <span class="hljs-comment">//操作数+1
    modCount++;
}

}

集合——LinkedList

 

  • 删除元素
public class test {
    public static void main(String[] args) {
        //构造LinkedList对象
        LinkedList list = new LinkedList();
        for (int i=0 ;i < 2;i++){
            //添加数据
            list.add(i);
        }
        System.out.println(list);
        //默认删除第一个元素
        list.remove();
    }
}
  1. list.remove();
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    public E remove() {
        return removeFirst();
    }
<span class="hljs-function"><span class="hljs-keyword">public E <span class="hljs-title">removeFirst<span class="hljs-params">() {
    <span class="hljs-comment">//获取第一个节点
    <span class="hljs-keyword">final Node&lt;E&gt; f = first;
    <span class="hljs-keyword">if (f == <span class="hljs-keyword">null)
        <span class="hljs-keyword">throw <span class="hljs-keyword">new NoSuchElementException();
    <span class="hljs-keyword">return unlinkFirst(f);
}
<span class="hljs-comment">//删除第一个元素
<span class="hljs-function"><span class="hljs-keyword">private E <span class="hljs-title">unlinkFirst<span class="hljs-params">(Node&lt;E&gt; f) {
    <span class="hljs-comment">// assert f == first &amp;&amp; f != null;
    <span class="hljs-comment">//获取第一个节点中的元素
    <span class="hljs-keyword">final E element = f.item;
    <span class="hljs-comment">//获取第一个节点的下一个node
    <span class="hljs-keyword">final Node&lt;E&gt; next = f.next;
    <span class="hljs-comment">//将第一个节点的值置空
    f.item = <span class="hljs-keyword">null;
    <span class="hljs-comment">//将指向下一节点的指针置空
    f.next = <span class="hljs-keyword">null; <span class="hljs-comment">// help GC
    <span class="hljs-comment">//让头节点指向下一个node
    first = next;
    <span class="hljs-comment">//如果下一节点不存在,置空尾节点指针。否则让下一节点的prev置空,不向前指向。
    <span class="hljs-keyword">if (next == <span class="hljs-keyword">null)
        last = <span class="hljs-keyword">null;
    <span class="hljs-keyword">else
        next.prev = <span class="hljs-keyword">null;
    <span class="hljs-comment">//元素数量-1
    size--;
    <span class="hljs-comment">//操作数+1
    modCount++;
    <span class="hljs-comment">//返回被删除的数据
    <span class="hljs-keyword">return element;
}

}

集合——LinkedList

 

将第一个节点中的next指针、item数据置空,第二个节点pre指针置空,头节点指向下一节点


END

上一篇:ArrayList,Vector, LinkedList的存储性能和特性


下一篇:未排序数组中累加和大于或等于给定值的最短子数组长度