电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: Java 容器源码分析之 LinkedList（4） [打印本页]

作者: look_w 时间: 2019-1-16 20:31 标题: 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;
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)