一、概述
从ArrayList深入研究，我们得知，当删除和插入操作的时候，存在元素的大量移动，它们的时间复杂度很高，那么有没有一种数据结构来减少它的时间复杂度呢，答案很显然，使用LinkedList，因为使用指针来指示其逻辑的位置，所以插入与删除的操作的时间复杂度都是 ** O(1) **。
二、自己动手系列-实现LinkedList
图解分析：
双向链表每个结点除了数据域之外，还有一个前指针和后指针，分别指向前驱结点和后继结点（如果有前驱/后继的话）。另外，双向链表还有一个 first 指针，指向头节点，和 last 指针，指向尾节点。
实现的LinkedList的方法如下：
add方法、get方法、indexOf方法、remove方法；与实现ArrayList的名字一样，为MyLinkedList。
构建一个双向链表
构建的代码如下：
private static class Node<E>{
E item;
Node<E> next;
Node<E> prev;
public Node(E item, Node<E> next, Node<E> prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
常规的双向链表的构建方法，一个数字域存放数组，一个前指针指向一个Node类型的元素，一个后指针指向一个Node类型的元素。
对于LinkedList的实现而言，还需要以下三个成员变量
private int size;
private Node<E> first;
private Node<E> last;
Add方法
这里实现的add方法是简单的add(E e)以及add(int index,E e)两个方法，addAll()将其他集合转换LinkedList的方法，暂时放到以后去实现。
add方法两个重载方法，其分别对应不同的添加方式。先说add(E e)方法的实现。
public boolean add(E element) {
addAtLast(element);
return true;
}
不指定位置添加元素，则默认添加到了链表的最后。addAtLast的核心代码如下：
private void addAtLast(E element) {
Node<E> l = last;
Node<E> node = new Node<E>(element, null, l);
last = node;
if (l == null) {
first = node;
} else {
l.next = node;
}
size++;
}
首先找到最后一位的Node元素，然后根据element创建一个新的Node元素，其next指向为null,prev指向为最后一位Node元素。在创建完Node元素之后，last就变成了先创建的Node元素，接下来只需要把新node元素加到链表中即可。即让l对象(原最后一位，现倒数第二位元素的next指针，指向新node元素)。至此，新node元素的next指向null,prev指向倒数第二个元素，倒数第二个元素的next指向新node，就将node成功加入链表。
上述的操作也可以看出，其插入的操作非常省时间，比起ArrayList，扩容，移动元素快很多。
通过Debug来分析添加的整个过程：
比如添加
lists.add(111);
lists.add(222);
lists.add(333);
执行lists.add(111)后
lists.add(111)
lists.add(222)
add的第二个重载方法 add(int index ,E e),先看代码实现：
public void add(int index, E element) {
checkRangeForAdd(index);
if (index == size) {
addAtLast(element);
} else {
Node<E> l = node(index);
addBeforeNode(element, l);
}
}
首先判断要插入的index是否在范围内，在的话，再执行后续的add操作。如果要插入的index刚好是最后一位，则执行上面讲的addAtLast，如果不是，则得到index所对应的Node元素，执行addBeforeNode。 获取index所对应的Node元素，是node方法，代码如下：
private Node<E> node(int index) {
if (index < (size << 1)) {
Node<E> cursor = first;
for (int i = 0; i < index; i++) {
cursor = cursor.next;
}
return cursor;
} else {
Node<E> cursor = last;
for (int i = size - 1; i > index; i--) {
cursor = cursor.prev;
}
return cursor;
}
}
这里的查找采用二分查找，节省查找时间，而且也应用到了双向链表的特点。首先判断index在前一半的范围内，还是后一半的范围内。如果是前一半，则游标Node初始为first,用游标Node元素的next，不断指向index所在的元素。如果是后一半，则游标Node初始为last,用游标Node元素的prev,不断指向index所在的元素。
在指定元素的前面插入新节点的addBeforeNode的方法如下：
private void addBeforeNode(E element, Node<E> specifiedNode) {
Node<E> preNode = specifiedNode.prev;
Node<E> newNode = new Node<>(element, specifiedNode, preNode);
if (preNode == null) {
first = newNode;
} else {
preNode.next = newNode;
}
specifiedNode.prev = newNode;
size++;
}
插入的方式很简单，新节点的prev是原index元素的prev,新节点的next是原index元素。剩下的操作是把该node放到链表中，让原index元素的prev的next为新节点，但是要判断preNode是不是空，是的话，表示newNode为第一个元素，就是first。
至此，一个add方法，就实现完了。
get方法
get方法在有了上述node方法之后，就非常的简单。代码如下：
public E get(int index) {
checkRange(index);
return node(index).item;
}
checkRange检查index是否不在范围内。
private void checkRange(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("指定index超过界限");
}
}
indexOf方法
indexOf(Object o)用来得到指定元素的下标。
public int indexOf(Object element) {
Node<E> cursor = first;
int count = 0;
while (cursor != null) {
if (element != null) {
if (element.equals(cursor.item)) {
return count;
}
}else{
if (cursor.item == null) {
return count;
}
}
count ++;
cursor = cursor.next;
}
return -1;
}
与ArrayList一样，从第一位开始查找，首先先判断element是不是null,分成两种情况。
remove方法
remove方法与add方法一样，同样有两个重载的方法，remove(Object o)与remove(int index)
先看简单的remove(int index)方法，代码如下：
public E remove(int index) {
checkRange(index);
return deleteLink(index);
}
deleteLink是将该index所对应的节点的链接删除的方法，其代码如下：
private E deleteLink(int index) {
Node<E> l = node(index);
E item = l.item;
Node<E> prevNode = l.prev;
Node<E> nextNode = l.next;
if (prevNode == null) {
first = nextNode;
}else{
prevNode.next = nextNode;
l.next = null;
}
if (nextNode == null) {
last = prevNode;
}else{
nextNode.prev = prevNode;
l.prev = null;
}
size--;
l.item = null;
return item;
}
首先获得该index对应的Node元素，得到该Node元素的前一个元素和后一个元素。接下来，只需要将前一个元素和后一个元素直接相连即可，其他只需要额外判断前一个元素和后一个元素是否为null就行。在判断前一个元素是否为null的时候，只需要操作前一个元素，在判断后一个元素是否为null的时候，也只需要操作后一个元素。最后，将要删除的元素各个引用至为null。
remove另一个重载方法remove(Object o)，在实现了indexOf和deleteLink方法之后，就非常简单。
public boolean remove(Object o) {
int index = indexOf(o);
if (index < 0){
return false;
}
deleteLink(index);
return true;
}
获取该元素对应对应的下标，然后执行deleteLink方法，完成remove操作。
网友评论