目录

---

一、双向链表是什么？

使用双向链表是可以提升链表的综合性能的。一张图就可以表示得很清楚了

 

二、双向链表自实现

1.node方法（根据下标查找元素）

private Node node(int index) {
		rangeCheck(index);//这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常
		
		if (index < (size >> 1)) {
			Node node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {
			Node node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}
	}

根据下标找出对应的节点，如果是单链表，则要从头到尾挨个找，但是对于双链表，我们可以先判断下标索引值与链表长度的一半进行对比，如果小于长度的一半，则可以从链表的头开始查找，如果大于了长度的一半，则可以从尾开始查找。

2.add (添加元素）

public void add(int index, E element) {
		rangeCheckForAdd(index); //这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常
 
		// size == 0
		// index == 0
		if (index == size) { // 往最后面添加元素
			Node oldLast = last;
			last = new Node<>(oldLast, element, null);
			if (oldLast == null) { // 这是链表添加的第一个元素
				first = last;
			} else {
				oldLast.next = last;
			}
		} else {
			Node next = node(index); 
			Node prev = next.prev; 
			Node node = new Node<>(prev, element, next);
			next.prev = node;
			
			if (prev == null) { // index == 0
				first = node;
			} else {
				prev.next = node;
			}
		}
		
		size++;
	}

3.remove(删除元素）

public E remove(int index) {
		rangeCheck(index); //这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常
 
		Node node = node(index);
		Node prev = node.prev;
		Node next = node.next;
		
		if (prev == null) { // index == 0
			first = next;
		} else {
			prev.next = next;
		}
		
		if (next == null) { // index == size - 1
			last = prev;
		} else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}

  4.clear分析 

	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

 按照之前咱们一般的理解，此时虽然已经把first和last置空了，与链表失去了联系，但是链表中的各个节点都相互指向，都被引用着，所以认为此时双链表不会被JVM回收。错了！！！此时链表相互指向的引线的性质已经变了，他们已经不再是gc root对象了。对于什么是gc root对象，简单的理解就是在栈中被局部变量指向的对象。所以此时clear这个函数是可以的。

 

三、双向链表 vs 单向链表 

 粗略对比一下删除的操作数量：

四、双向链表 vs 动态数组