惯例,笑话开头。
哈哈哈
阅读本文你可以掌握,LinkedList 相关知识点和细节。
目录 |
---|
数据结构基础 |
LinkedList源码解析 |
面试知识 |
数据结构基础
链表的特点
1,链表查询数据,需要遍历整个链表,即便是做了优化,判断当前index,确定从前边遍历或者从后边遍历,时间复杂度仍是O(n)。
2,链表插入和删除的,首先需要找到当前插入的点,也需要遍历链表,然后把节点指针相连,所以时间复杂度也是O(n);但是为什么都说链表更适合插入和删除呢,因为链表查找的时间要比移动数据快很多。
3 ,内存利用率高,不会浪费内存(数组需要提前分配内存,链表则不需要,而且没有大小限制,内存也可以不连续)
单链表和双链表
单链表
缺点:每个节点只有一个next指针,只能一种遍历方式,
优点:单链表存储一个节点,就比较节省内存,当节点N无线大的时候,节省的内存还是挺可观的。
双链表
优点:每个节点有两个指针,可以从前边或者从后边遍历,利用二分查找,所以理论上双链表遍历效率是比单链表快的,
缺点:但是相对单链表来说占用内存相对较大
LinkedList源码解析
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;
}
}
成员属性
属性 | |
---|---|
size | 链表长度 |
first | 头节点 |
last | 尾节点 |
modCount | failFast机制 |
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
为什么定义两个节点?
如果只有一个头节点,添加数据就需要从头结点遍历拿到最后一个节点,这样时间复杂度O(n),数据量庞大的时候效果非常明显,定义一个last节点,添加单个数据的时间复杂度就变成了O(1).
void linkBefore(E e) {
Node newNode = new Node(e, null);
Node next = first;
if (next ==null){
first =newNode;
}else{
//遍历找到最后一个节点
for (int i = 0; i < size; i++){
next = next.next;
}
next.next =newNode;
}
size++;
}
这种写法 每次添加数据的时候需要找到最后一个节点,时间复杂度O(n);
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
定义一个last节点,添加就变成了O(1)级别
构造方法
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
第二种,把当前数据转换成数组,然后遍历数组,创建Node节点添加到链表中。
为什么使用双链表?
单链表遍历只能一个方向遍历,时间复杂度O(n),使用双链表可以两个方向遍历,时间复杂度O(n/2),当N足够大其实也是O(n),但是这样实际减少了遍历消耗。
*/
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;
}
}
面试知识
LinkdeList 面试大部分是对比ArrayList 来的。
1,为什么实现不是单链表
答 :空间换时间,消耗了一定空间,遍历的时候速度相对来说加快一倍。
2,为什么定义两个节点?
答:优化了添加的时间复杂度,一个节点需要遍历找到最后的节点,定义一个尾节点,使得添加时间复杂度从O(n)降低为O(1);
3,什么时候使用Arraylist 什么时候使用lindekList?
答:如果需要频繁移除或者中间插入这种,arraylist都需要调用arraycopy比较消耗性能,这种时候需要考虑linkedlist,如果只是遍历就用arraylist 查询级别O(1);linkedlist查询虽然做了优化,(二分查找) 但是数据足够大还是o(n)级别。
网友评论