Java 容器源码分析之 LinkedList（4）
|
- UID
- 1066743
|
Java 容器源码分析之 LinkedList（4）
根据索引获取元素因为是双向链表，可向前遍历，也可向后遍历。查找时双向进行，靠近头节点则从前向后查找；靠近尾部，则从后向前查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| //根据索引获取元素
Node<E> node(int index) {
// assert isElementIndex(index);
//双向查找，根据index和size判断
//前半段，从头节点向后查找
//后半段，从尾节点向前查找
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;
}
}
|
反查一个元素的索引第一次出现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
|
最后一次出现，从后向前查找：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
} |
|
|
|
|
|
|
