目录
- 一、双向链表是什么?
- 二、双向链表自实现
- 1.node方法
- 2.add
- 3.remove
- 4.clear分析
- 三、双向链表 vs 单向链表
- 四、双向链表 vs 动态数组
一、双向链表是什么?
使用双向链表是可以提升链表的综合性能的。一张图就可以表示得很清楚了
二、双向链表自实现
1.node方法(根据下标查找元素)
private Node<E> node(int index) {
rangeCheck(index);//这是自己封装的一个检查函数,用来检查index的合法性,否则抛出异常
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> 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<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 这是链表添加的第一个元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> 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<E> node = node(index);
Node<E> prev = node.prev;
Node<E> 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 单向链表
粗略对比一下删除的操作数量:
◼
单向链表:1 + 2 + 3 + … + n = (1+n) ∗ n/ 2 = n/2 + n^2/2 ,除以n平均一下是 1/2 + n/2
单向链表:1 + 2 + 3 + … + n = (1+n) ∗ n/ 2 = n/2 + n^2/2 ,除以n平均一下是 1/2 + n/2
◼
双向链表:(1 + 2 + 3 + … + n/2 ) * 2 = ((1+ n/2)∗ n/2 )/2 * 2 = n/2 + n^2/4,除以n平均一下是 1/2 + n/4
双向链表:(1 + 2 + 3 + … + n/2 ) * 2 = ((1+ n/2)∗ n/2 )/2 * 2 = n/2 + n^2/4,除以n平均一下是 1/2 + n/4
经过对比,操作数量减少了一半
四、双向链表 vs 动态数组
◼动态数组:开辟、销毁内存空间的次数相对较少,但可能造成内存空间浪费
◼ 双向链表:开辟、销毁内存空间的次数相对较多,但不会造成内存空间的浪费
◼ 如果频繁在尾部进行添加、删除操作,动态数组、双向链表均可选择
◼ 如果频繁在头部进行添加、删除操作,建议选择使用双向链表
◼ 如果有频繁的(在任意位置)添加、删除操作,建议选择使用双向链表
◼ 如果有频繁的查询操作(随机访问操作),建议选择使用动态数组
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/94605.html