博客

对于频繁的插入或删除元素操作，建议使用LinkedList，效率较高。

LinkedList

是通过一个双向链表来实现的，它允许插入所有元素，包括 null，同时，它是线程不同步的。


双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点
（如果有前驱/后继的话）。
另外，双向链表还有一个 first 指针，指向头节点，和 last 指针，指向尾节点。

节点结构：


Node是在LinkedList里定义的一个静态内部类，它表示链表每个节点的结构，包括一个数据域item，一个后指针next，一个前指针prev

private static class Node<E> {
	E items;
	Node<E> next;
	Node<E> prev;
	
	Node(Node<E> prev, E element, Node<E> next){
		this.item = element;
		this.next = next;
		this.prev = prev;
	}
}

添加元素：


对于链表这种数据结构来说，添加元素的操作无非就是在表头/表尾插入元素，又或者在指定位置插入元素。因为 LinkedList 有头指针和尾指针，所以在表头或表尾进行插入元素只需要 O(1) 的时间，而在指定位置插入元素则需要先遍历一下链表，所以复杂度为 O(n)。

当向表头插入一个节点时，很显然当前节点的前驱一定为 null，而后继结点是 first 指针指向的节点，当然还要修改 first 指针指向新的头节点。除此之外，原来的头节点变成了第二个节点，所以还要修改原来头节点的前驱指针，使它指向表头节点。

1、LinkedList 的底层结构是一个带头/尾指针的双向链表，可以快速的对头/尾节点进行操作。

2、相比数组，链表的特点就是在指定位置插入和删除元素的效率较高，但是查找的效率就不如数组那么高了。