List实现之LinkedList

        LinkedList是List 接口的链接列表实现。实现List接口所有可选的列表操作，并且允许添加任何元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法（如：getFirst、removeLast等）。这些操作允许将链接列表用作堆栈、队列或双端队列。

        LinkedList还实现了 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

        注意，LinkedList不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须保持外部同步。（结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));

 

        LinkedList的 iterator 和 listIterator 方法返回的迭代器是快速失败（fail-fast）的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。

        所谓fail-fast是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。

        例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

        同样的我们从LinkedList的源码深入来分析LinkedList的结构及应用场景：

 

        1.LinkedList的成员变量

        与ArrayList相同LinkedList依旧只有两个成员变量：

private transient Entry<E> header = new Entry<E>(null, null, null);   
private transient int size = 0;  //列表大小

        既然LinkedList是一个链表实现，那么header必然就是这个链表的头部，其中Entry即为节点对象。

        size与ArrayList实现一样是这个列表的大小（元素个数）。

 

        2.Entry节点元素

        与ArrayList不同，LinkedList的内部是利用Entry这个内部类来实现的，下面是Entry源代码：

private static class Entry<E> {
	//当前元素
	E element;
	//下一个元素
	Entry<E> next;
	//上一个元素
	Entry<E> previous;

	Entry(E element, Entry<E> next, Entry<E> previous) {
		this.element = element;
		this.next = next;
		this.previous = previous;
	}
}

        Entry类只定义了三个属性：previous（前一个元素）、element（当前元素）、next（后一个元素）。这样获取到当前位置节点元素后就可以很容易的找到它之前和之后的两个节点，这样在不同的Entry间就建立了联系，从而就实现了双向的链表结构。

 

 

        3.LinkedList的使用

        使用LinkedList也是需要先实例化：

List list=new LinkedList();

        实例化时会调用LinkedList的默认构造方法：

/**
 * 构建一个空的list实例
 */
public LinkedList() {
    header.next = header.previous = header;
}

        默认构造方法不接受任何参数，只是将header节点的前一节点和后一节点都设置为自身，这样整个链表其实就只有header一个节点，用于表示一个空的链表。

 

        实例化LinkedList之后，利用add方法向其添加元素：

list.add("元素一");

        此时LinkedList其内部结构如图：
 

        此时是列表中只有一个已添加元素的状态，新添加节点元素的previous与next均指向header，那么是如何通过代码来实现此种结构的呢？就需要我们来查看一下add方法的相关源代码：

/**
 * 添加指定元素至此list尾部
 */
public boolean add(E e) {
	addBefore(e, header);
	return true;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
}

         add方法中并没有实际处理的逻辑，而是调用的另一个私有方法addBefore(e, header)，其中E e参数为要添加的元素，Entry<E> entry为header。

        进入addBefore方法后：

        首先，创建了一个新的节点元素 newEntry，newEntry的next指向header，newEntry的previous指向header的previous。

        newEntry的next指向header不难理解，新添加的节点元素必然是在整个链表的尾部，既然LinkedList是一个双向循环链表，那么newEntry的下一个节点将回到整个链表的“原点”header。进而header的上一个节点元素必然就是整个链表的尾部节点，所以newEntry的previous指向header的previous，这样newEntry的上一个节点就指向了原来整个链表的最后一个节点，进而newEntry成为了链表新的尾节点。

        然后，将newEntry的前一个节点的next指向自己，因为链表原来的尾部节点指向的是“原点”header，将其next指向自己后就将两个节点连接了起来。

        再将 newEntry的后一个节点（header）的previous 指向自己，这样header就与newEntry也连接到了一起。

        最后，整个链表就将新添加的节点元素newEntry添加到了尾部。

        以下是添加了三个元素后的结构图示：

        通过图例可以清晰的看到在向LinkedList中添加了三个元素之后，这三个元素与header组成了一个双向循环的链表结构。通过每一个节点元素的previous与next可以访问到前一个与后一个节点元素。

 

        4.获取元素

        在ArrayList中通过get(index)方法可以直接返回该下标位置元素，因为ArrayList的内部实现为数组，所以get方法等效与array[index]，所以性能非常高。

        那么LinkedList的内部是如何获取指定位置元素的呢？以下是相关方法的源代码：

/**
 * 返回指定位置元素
 */
public E get(int index) {
	return entry(index).element;
}

/**
 * 返回指定位置元素
 */
private Entry<E> entry(int index) {
	if (index < 0 || index >= size)
		throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	Entry<E> e = header;
	if (index < (size >> 1)) {
		for (int i = 0; i <= index; i++)
			e = e.next;
	} else {
		for (int i = size; i > index; i--)
			e = e.previous;
	}
	return e;
}

 

        get方法中引用的是另一个方法Entry<E> entry(int index)，通过此方法可以返回index位置的元素，所以entry方法才是关键。

        entry方法中首先是下标越界的判断；然后判断index是否小于(size >> 1)，这里size>>1等同于size/2（size除以2），只不过用位移性能更高。这里是要判断index位于链表的前半部分还是后半部分，从而判断从那个方向遍历。最后就是用循环方式遍历到index那个位置，得到该位置的元素并返回。

        从源代码中可以看出，LinkedList获取元素采用的是遍历链表的方式，虽然最多只会循环列表大小的一半，但其性能也是比较低的。

 

        5.LinkedList移除元素

        如果对于添加操作已经理解清晰，那么对于移除元素即便不看源代码也应该大致了解其内部处理方式，无非就是改变相关节点元素的previous与next指向问题。

        以下为LinkedList中remove方法的源代码：

/**
 * 移除指定位置元素
 */
public E remove(int index) {
	return remove(entry(index));
}

private E remove(Entry<E> e) {
	if (e == header)
		throw new NoSuchElementException();

	E result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
	e.next = e.previous = null;
	e.element = null;
	size--;
	modCount++;
	return result;
}

        remove方法调用了两个相关其他方法，一个是根据index返回指定位置元素的Entry<E> entry(int index)方法，另一个是删除指定元素的方法E remove(Entry<E> e)。

        remove方法的核心就是找到index位置元素，将此元素上一个和下一个节点元素的指向连接，进而达到移除的目的：

 

        6.LinkedList的一些特殊操作及用途

        本文最开始已经介绍了很多LinkedList不同于ArrayList的用途，因为LinkedList的实现结构为链表形式，所以LinkedList可以用于堆栈、队列或双端队列等形式结构。

        所以LinkedList提供了一些*First，*Last类似的操作，如：getFirst，getLast；offerFirst，offerLast等。

        1）用LinkedList实现堆栈结构

        LinkedList中提供了pop和push两个方法：

 E pop() 
          从此列表所表示的堆栈处弹出一个元素。 
 void push(E e) 
          将元素推入此列表所表示的堆栈。 

        通过这两个方法就可以模拟内存堆栈的结构，从而对一些特殊场景业务进行处理，以下是一个简单实例：

LinkedList list = new LinkedList();
list.push("栈帧1");
list.push("栈帧2");
list.push("栈帧3");
list.push("栈帧4");
for (int i = 0, j = list.size(); i < j; i++) {
	System.out.println("entry:"+list.pop());
	System.out.println("size :"+list.size());
}
//打印结果
entry:栈帧4
size :3
entry:栈帧3
size :2
entry:栈帧2
size :1
entry:栈帧1
size :0

        首先，将四个“栈帧”压入了LinkedList中，然后，循环将所有“栈帧”弹出，随着“栈帧”的弹出，list的大小也在减小，直至为0。这样就实现了一个简单的栈结构列表，实现了后进先出的原则。

 

        2）用LinkedList实现队列结构

        队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。

        在生活中我们也会经常接触到队列，如车站买票，进站安检，排队购物等等：

        在结构上队列如图所示：

        LinkedList类实现了Queue（队列）接口，在Queue接口中提供了offer，peek和poll三个方法用于添加和获取元素：

 boolean offer(E e) 
          将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。 
 E peek() 
          获取但不移除此队列的头；如果此队列为空，则返回 null。 
 E poll() 
          获取并移除此队列的头，如果此队列为空，则返回 null。 

        所以我们可以利用这几个相关方法结合LinkedList来实现一个队列结构：

LinkedList list = new LinkedList();
list.offer("成员1");
list.offer("成员2");
list.offer("成员3");
list.offer("成员4");
for (int i = 0, j = list.size(); i < j; i++) {
	System.out.println("entry:" + list.peek());
	System.out.println("size :" + list.size());
}
for (int i = 0, j = list.size(); i < j; i++) {
	System.out.println("entry:" + list.poll());
	System.out.println("size :" + list.size());
}
// 打印结果
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :4
entry:成员1
size :3
entry:成员2
size :2
entry:成员3
size :1
entry:成员4
size :0

        使用peek方法可以获取到该队列的头，但是不会移除头元素，所以打印结果中出现了4次“成员一”。

        使用poll方法也可以获取到该队列的头，但是会移除该元素，所以可以通过poll方法依次将队列中的成员取出进行操作。

          LinkedList还可以实现一些其他的特殊结构，这里就不再赘述了，可以根据自己的实际情况去处理和编写相应代码。