linkedlist
linkedlist是一种可以在任何位置进行高效地插入和删除操作的有序序列。
它的最基本存储结构是一个节点：每个节点将存储对象，以及前后节点的引用。
结构图
从上面的结构图中，我们可以了解到 listedlist 底层是基于双向链表实现的。
围起来的可以看成 linkedlist 类，它定义了三个 transient 成员变量：first、last、size。这三个变量是整个 linkedlist 类的关键点。
- 由于是双向链表（每个node都有保存前后节点的引用），因此我们不管是由 first 还是 last 节点开始迭代，都可以将整个链表的数据找出来；
- 在查询、随机插入以及set等操作都有涉及 size 判断；
- 由于 linkedlist 是双向链表，类中只存储了首尾两个节点，因此查询第n个元素都要从头遍历进行查找。
源码分析
add(e e) 源码分析
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/** * appends the specified element to the end of this list. * * <p>this method is equivalent to {@link #addlast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link collection#add}) */ public boolean add(e e) { linklast(e); return true; } /** * links e as last element. */ void linklast(e e) { final node<e> l = last; // 将当前最后一个元素寄存在 l final node<e> newnode = new node<>(l, e, null); // new 一个新节点：pre的引用为l；存储元素为e；next的引用为null last = newnode; // 将新节点引用覆盖成员变量 last if (l == null) first = newnode; // 若l为null，说明之前链表为空，此时新节点为首个元素 else l.next = newnode; // 否则，更新l的next引用 size++; // size+1 modcount++; // 非查询操作 modcount 都会 +1 } |
add(int index, e element) 方法分析
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
/** * inserts the specified element at the specified position in this list. * shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws indexoutofboundsexception {@inheritdoc} */ public void add(int index, e element) { checkpositionindex(index); // 检查 index 是否大于 size if (index == size) linklast(element); // 直接在链表末尾追加 else linkbefore(element, node(index)); // 插入index 节点前面 } // 检查 index 是否超出范围 超出则抛出 indexoutofboundsexception private void checkpositionindex(int index) { if (!ispositionindex(index)) throw new indexoutofboundsexception(outofboundsmsg(index)); } /** * tells if the argument is the index of a valid position for an * iterator or an add operation. */ private boolean ispositionindex(int index) { return index >= 0 && index <= size; } /** * 根据 index 查找 node * 该方法利用了双向链表的特性，index 距离哪个链表头近就从哪边开始开始遍历 * 时间复杂度为 o(n/2)； * 当 index 接近 size 的中间值时，效率最低 * returns the (non-null) node at the specified element index. */ node<e> node(int index) { // assert iselementindex(index); if (index < (size >> 1)) { // size 右移一位（除以2） 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; } } |
优缺点
优点
增删元素效率高（只需要更新节点附近的引用即可）
缺点
由于查询需要进行遍历，因此效率低
知识脑图
以上所述是小编给大家介绍的java 集合系列（三）—— linkedlist详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持！
