找外地的做网站,企业推广的成功在于他们发现,网站兼容设置,网络组建与配置 2018版清华大学出版社LinkedList是一种常见的数据结构#xff0c;但是大多数开发者并不了解其底层实现原理#xff0c;以至于存在很多误解#xff0c;在这篇文章中#xff0c;将带大家一块深入剖析LinkedList的源码#xff0c;并为你揭露它们背后的真相。首先想几个问题#xff0c;例如#…LinkedList是一种常见的数据结构但是大多数开发者并不了解其底层实现原理以至于存在很多误解在这篇文章中将带大家一块深入剖析LinkedList的源码并为你揭露它们背后的真相。首先想几个问题例如
LinkedList 的底层是基于什么数据结构实现的LinkedList 的插入和删除操作时间复杂度是否都是 O(1) ?LinkedList 和 ArrayList 相比哪种结构存储数据的时候更占内存LinkedList 真的不支持随机访问吗LinkedList 是线程安全的吗
接下来一块分析一下 LinkedLis t的源码看完 LinkedList 源码之后可以轻松解答上面几个问题
简介
LinkedList底层是基于双向链表实现的内部有三个属性size用来存储元素个数first指向链表头节点last指向链表尾节点。
public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable {// 元素个数transient int size 0;// 头节点transient NodeE first;// 尾节点transient NodeE last;
} 头尾节点都是由Node节点组成Node节点表示双向链表内部结构如下 private static class NodeE {// 存储元素数据E item;// 后继节点指向下一个元素LinkedList.NodeE next;// 前驱节点指向上一个元素LinkedList.NodeE prev;// 构造函数Node(LinkedList.NodeE prev, E element, LinkedList.NodeE next) {this.item element;this.next next;this.prev prev;}
}
再看一下LinkedList的继承类图还是很清晰的 LinkedList实现了List接口提供了集合操作的常用方法当然也包含随机访问的方法只不过没有相ArrayList那样实现RandomAccess接口LinkedList提供的随机访问的方法时间复杂度并不是常量级别的。
public interface ListE extends CollectionE {// 查询方法int size();boolean isEmpty();boolean contains(Object o);IteratorE iterator();Object[] toArray();T T[] toArray(T[] a);// 修改方法boolean add(E e);boolean remove(Object o);// 批量修改方法boolean containsAll(Collection? c);boolean addAll(Collection? extends E c);boolean addAll(int index, Collection? extends E c);boolean removeAll(Collection? c);boolean retainAll(Collection? c);default void replaceAll(UnaryOperatorE operator) {}default void sort(Comparator? super E c) {}void clear();// 比较方法boolean equals(Object o);int hashCode();// 随机访问方法E get(int index);E set(int index, E element);void add(int index, E element);E remove(int index);// 搜索方法int indexOf(Object o);int lastIndexOf(Object o);// 迭代方法ListIteratorE listIterator();ListIteratorE listIterator(int index);java.util.ListE subList(int fromIndex, int toIndex);
}
LinkedList还实现了Deque接口Deque是 double ended queue 的缩写读音是 [dek] 读错就尴尬了。 Deque是双端队列可以在头尾进行插入和删除操作兼具栈和队列的性质。 内部结构如下
public interface DequeE extends QueueE {// 基础方法void addFirst(E e);void addLast(E e);boolean offerFirst(E e);boolean offerLast(E e);E removeFirst();E removeLast();E pollFirst();E pollLast();E getFirst();E getLast();E peekFirst();E peekLast();boolean removeFirstOccurrence(Object o);boolean removeLastOccurrence(Object o);// 队列方法boolean add(E e);boolean offer(E e);E remove();E poll();E element();E peek();// 栈方法void push(E e);E pop();// 集合方法boolean remove(Object o);boolean contains(Object o);public int size();IteratorE iterator();IteratorE descendingIterator();
}
Deque为什么提供了这么多增删查的方法为了满足不同的使用场景。比如Deque队列已经满了再往里面添加元素addFirst() 方法会抛出异常offerFirst() 方法会返回false
初始化
LinkedList只有一个构造方法无参构造方法并不能像ArrayList那样指定长度。
ListInteger list new LinkedList();
//构造方法
public LinkedList() {
}
添加元素
添加元素的方法根据位置区分共有三种在头部添加、在尾部添加和在任意位置添加。
在头部添加 addFirst/push offerFirst 在尾部添加 addLast add/offer/offerLast 在任意位置添加 add(index, e)
先看一下使用的最多的add(e)方法底层实现
// 添加元素
public boolean add(E e) {// 在末尾添加元素linkLast(e);return true;
}// 在末尾添加元素
void linkLast(E e) {// 1. 获取尾节点final LinkedList.NodeE l last;// 2. 初始化新节点final LinkedList.NodeE newNode new LinkedList.Node(l, e, null);// 3. 追加到末尾last newNode;if (l null) {first newNode;} else {l.next newNode;}size;modCount;
}
可以看到add(e
// 添加元素
public void push(E e) {// 在头部添加元素addFirst(e);
}// 在头部添加元素
public void addFirst(E e) {linkFirst(e);
}// 在头部添加元素底层私有实现
private void linkFirst(E e) {// 1. 获取头节点final LinkedList.NodeE f first;// 2. 初始化新节点final LinkedList.NodeE newNode new LinkedList.Node(null, e, f);// 3. 追加到头部first newNode;if (f null) {last newNode;} else {f.prev newNode;}size;modCount;
}
)方法是尾部添加元素再看一个从头部添加元素的push()。
最后看一个在任意位置添加到方法add(index, e)的底层实现
// 在下标index位置添加元素
public void add(int index, E element) {// 检查下标是否越界checkPositionIndex(index);// 如果index等于链表的最后一个元素则添加到末尾if (index size) {linkLast(element);} else {// 添加到指定位置前面先找到index位置的元素linkBefore(element, node(index));}
}// 在当前元素前面添加新元素
void linkBefore(E e, LinkedList.NodeE succ) {final LinkedList.NodeE pred succ.prev;// 创建新节点并将新节点插入到当前节点之前final LinkedList.NodeE newNode new LinkedList.Node(pred, e, succ);succ.prev newNode;if (pred null) {first newNode;} else {pred.next newNode;}size;modCount;
}
再看一下检查下标是否越界的方法底层实现
/ 检查下标是否越界
private void checkElementIndex(int index) {if (!isElementIndex(index)) {throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
}// 判断下标是否越界
private boolean isElementIndex(int index) {return index 0 index size;
}
查询元素
查询元素的方法跟位置区分共有三种查询头节点、查询尾节点和查询任意位置元素。
方法含义 如果不存在则返回null 如果不存在则抛异常
查询头部 peek/peekFirst getFirst/element
查询尾部 peekLast getLast
查询任意位置 - get
看一下从头查询的element()方法的底层实现
// 查询元素
public E element() {return getFirst();
}// 获取第一个元素
public E getFirst() {final LinkedList.NodeE f first;if (f null) {throw new NoSuchElementException();}return f.item;
}
再看一个查询尾节点的方法getLast()的底层实现
// 获取最后一个元素
public E getLast() {final LinkedList.NodeE l last;if (l null) {throw new NoSuchElementException();}return l.item;
}
再看一个查询任意位置的方法get(index)的底层实现
// 查询下标是index位置的元素
public E get(int index) {// 检查下标是否越界checkElementIndex(index);// 返回对应下标的元素return node(index).item;
}// 返回对应下标的元素
LinkedList.NodeE node(int index) {// 判断下标是否落在前半段if (index (size 1)) {// 如果在前半段则从头开始遍历LinkedList.NodeE x first;for (int i 0; i index; i) {x x.next;}return x;} else {// 如果在后半段则从尾开始遍历LinkedList.NodeE x last;for (int i size - 1; i index; i--) {x x.prev;}return x;}
} 可见LinkedList的也支持随机访问只不过时间复杂度是O(n)。
删除元素
删除元素的方法按照位置区分也分为三种分别是删除头节点、删除尾节点和删除任意位置节点。
方法含义 返回布尔值如果不存在返回false 返回旧值如果不存在则抛异常 从头部删除 remove(o)/removeFirstOccurrence remove/poll/pollFirst/removeFirst/pop
从尾部删除 removeLastOccurrence pollLast/removeLast
从任意位置删除 - remove(index)
先看一个从头开始删除的方法remove()的底层实现
// 删除元素
public E remove() {// 删除第一个元素return removeFirst();
}// 从头删除元素
public E removeFirst() {final LinkedList.NodeE f first;if (f null) {throw new NoSuchElementException();}// 调用实际的删除方法return unlinkFirst(f);
}// 删除第一个元素
private E unlinkFirst(LinkedList.NodeE f) {final E element f.item;final LinkedList.NodeE next f.next;// 断开头节点与后继节点的连接f.item null;f.next null;first next;if (next null) {last null;} else {next.prev null;}size--;modCount;return element;
} 再看一个从最后一个节点开始删除的方法removeLast()的底层实现
// 删除最后一个元素
public E removeLast() {final LinkedList.NodeE l last;if (l null) {throw new NoSuchElementException();}// 实际的删除逻辑return unlinkLast(l);
}// 删除最后一个元素
private E unlinkLast(LinkedList.NodeE l) {final E element l.item;// 断开与前一个节点的连接final LinkedList.NodeE prev l.prev;l.item null;l.prev null;last prev;if (prev null) {first null;} else {prev.next null;}size--;modCount;return element;
}
再看一个从任意位置的节点开始删除的方法remove(index)的底层实现
// 删除下标是index位置的元素
public E remove(int index) {// 检查下标是否越界checkElementIndex(index);// 删除下标对应的元素先找到下标对应的元素return unlink(node(index));
}// 删除下标对应的元素
E unlink(LinkedList.NodeE x) {final E element x.item;// 1. 备份当前节点的前后节点final LinkedList.NodeE next x.next;final LinkedList.NodeE prev x.prev;// 2. 断开与前驱节点的连接if (prev null) {first next;} else {prev.next next;x.prev null;}// 3. 断开与后继节点的连接if (next null) {last prev;} else {next.prev prev;x.next null;}x.item null;size--;modCount;return element;
} 总结
学完了LinkedList的核心方法的源码现在可以很容易回答文章开头的几个问题了。
LinkedList的底层是基于什么数据结构实现的
答案双向链表。
LinkedList的插入和删除操作时间复杂度是否都是 O(1) ?
答案不是在头尾操作的时间复杂度是O(1)在其他位置操作的时间复杂度是O(n)。
LinkedList和ArrayList相比哪种结构存储数据的时候更占内存
答案由于LinkedList的每个节点还包含前后节点的引用所以会占用更多的空间。
LinkedList真的不支持随机访问吗
答案LinkedList支持随机访问比如get(index)和get(o)方法不过它们的时间复杂度是O(n)。
LinkedList是线程安全的吗
答案LinkedList不是线程安全的内部没有提供同步机制来保证线程安全。并发修改的时候可能导致数据错乱在遍历过程中修改会抛出ConcurrentModificationException异常。 想要线程安全其中一种方式是初始化List的时候使用 Collections.synchronizedList() 修饰。这样LinkedList所有操作都变成同步操作性能较差。还有一种性能较好又能保证线程安全的方式是使用 CopyOnWriteArrayList
// 第一种方式使用 Collections.synchronizedList() 修饰
ListInteger list Collections.synchronizedList(new LinkedList());// 第二种方式使用 CopyOnWriteArrayList
ListInteger list new CopyOnWriteArrayList();
同样因为 LinkedList有队列的相关属性也可以当做队列来使用并且可以实现简单的LRU算法来进行数据淘汰的方式。
