avatar

LinkList相关学习

介绍

LinkList也是工作中常见的集合, 底层使用双向链表结构
比较适合新增和删除, 查询和修改需要遍历相对ArrayList比较消耗性能

内部类 Node

private static class Node<E> {
// 元素值
E item;
// 下一个节点
Node<E> next;
// 上一个几点
Node<E> prev;
// 构造一个新节点 指向上一个节点和下一个节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

add 新增

通过代码可以看出, 在新增元素时只需要创建一个新节点 Node, 并将原始链表最后一个Node的next指向新Node

public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
// 声明 l 为最后一个节点
final Node<E> l = last;
// 创建新节点, 指向上一个节点, 下一个节点为空
final Node<E> newNode = new Node<>(l, e, null);
// 最后一个节点为新创建的节点
last = newNode;
// 判断是否为第一个元素, 否则将 新创建的 Node加入链表
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

remove 删除

1.删除操作需要遍历链表找到相应元素, 然后移动指针即可
2.删除首尾元素直接移动指针即可 removeFirst()/removeLast() 方法


public boolean remove(Object o) {
if (o == null) {
// 遍历链表
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

/**
* 删除元素
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 判断上一个Node是否为空
if (prev == null) {
// 空, 该节点为链表头, 将下一个节点设置为链表头
first = next;
} else {
// 不为空, 将上一个节点的next 指向当前节点的 next, 并将当前节点的 prev置为空
prev.next = next;
x.prev = null;
}
// 判断下一个Node是否为空
if (next == null) {
// 空, 该节点为链表尾, 将链表尾设置为当前节点的上一个节点
last = prev;
} else {
// 不为空, 将下一个节点的prev, 设置为上一个节点, 并将当前节点的 next置为空
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

get/set

get/set时都需要获取指定索引的元素, 使用二分法查找, 然后进行遍历查找, 所以此处相较于ArrayList多了遍历查询, 虽然使用了二分法进行优化, 但是get/set操作相比ArrayList来说性能还是相对较差

public E get(int index) {
// 校验索引
checkElementIndex(index);
// 二分法遍历查找节点
return node(index).item;
}

public E set(int index, E element) {
// 校验索引
checkElementIndex(index);
// 二分法遍历查找节点
Node<E> x = node(index);
// 修改Node节点的 item值
E oldVal = x.item;
x.item = element;
return oldVal;
}

/**
* 返回指定索引处非null节点.
*/
Node<E> node(int index) {
// assert isElementIndex(index);

// 判断索引是否小于长度的一半 (二分法) 然后遍历查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
文章作者: liuzhihang
文章链接: https://liuzhihang.com/2018/08/23/linklist-related-learning.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Notes

评论