Java-LinkedList

LinkedList(参考文章

【介绍】

public class LinkedList<E>
	extends AbstractSequentialList<E>
	implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 底层的数据结构是基于双向循环链表的,且头结点中不存放数据

LinkedList 是一个继承了 AbstractSequentialList 的双向链表

(1)LinkedList 实现了 List 接口,能对它进行队列操作。

(2)LinkedList 实现了 Cloneable 接口,即实现克隆功能。(实现clone()函数)

(3)LinkedList 实现 java.io.Serializable 接口,表示支持序列化,能通过序列化去传输。

(4)LinkedList 实现了 Deque 接口,即能将LinkedList当作双端队列使用。

LinkedList 是非线程安全的。


【使用】

一、构造方法:

LinkedList 不存在容量问题,只有两个构造方法

(1)无参构造器:

public LinkedList() {
}

(2)传入一个集合的有参构造器:

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
二、API:(与实现了List接口的都差不多)

(1)remove()方法:默认是移除 头结点 :

public E remove() {
    return removeFirst();
}

(2)get()方法:如何将“双向链表和索引值联系起来的”

起作用的方法:

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;
    }
}

实际原理非常简单,它就是通过一个计数索引值来实现的。例如,当我们调用get(int index)时,首先会比较“index”和“双向链表长度的1/2”;若前者大,则从链表头开始往后查找,直到 index 位置;否则,从链表末尾开始先前查找,直到 index 位置。


【源码分析】

  1. add操作:

     public boolean add(E e) {
     	linkLast(e);
     	return true;
     }
    
  2. 插入到尾部:

    如果 last 是空结点,则表示 add 进一条空链表,此时 first 和 last 指向这个新结点:

     		last = newNode;
     	if (l == null)
     		first = newNode;
    

    否则,原尾结点指向新结点, last 还是指向新结点:

     		else
     			l.next = newNode;
    

    源码:

     	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++;
     	}
    
  3. 创造新结点:

     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
上一篇:VUE使用防抖和节流,避免重复触底加载和点击


下一篇:ORACLE 分页和行限制