LinkedList实现 - 查找操作

xhz

查找操作

查找操作的本质是查找元素的下标:


查找第一次出现的index, 如果找不到返回-1；

1. 
   
2.     /**
   
3.      * Returns the index of the first occurrence of the specified element
   
4.      * in this list, or -1 if this list does not contain the element.
   
5.      * More formally, returns the lowest index {@code i} such that
   
6.      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
   
7.      * or -1 if there is no such index.
   
8.      *
   
9.      * @param o element to search for
   
10.      * @return the index of the first occurrence of the specified element in
    
11.      *         this list, or -1 if this list does not contain the element
    
12.      */
    
13.     public int indexOf(Object o) {
    
14.         int index = 0;
    
15.         if (o == null) {
    
16.             for (Node<E> x = first; x != null; x = x.next) {
    
17.                 if (x.item == null)
    
18.                     return index;
    
19.                 index++;
    
20.             }
    
21.         } else {
    
22.             for (Node<E> x = first; x != null; x = x.next) {
    
23.                 if (o.equals(x.item))
    
24.                     return index;
    
25.                 index++;
    
26.             }
    
27.         }
    
28.         return -1;
    
29.     }
    

复制代码

查找最后一次出现的index, 如果找不到返回-1；

1. 
   
2.     /**
   
3.      * Returns the index of the last occurrence of the specified element
   
4.      * in this list, or -1 if this list does not contain the element.
   
5.      * More formally, returns the highest index {@code i} such that
   
6.      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
   
7.      * or -1 if there is no such index.
   
8.      *
   
9.      * @param o element to search for
   
10.      * @return the index of the last occurrence of the specified element in
    
11.      *         this list, or -1 if this list does not contain the element
    
12.      */
    
13.     public int lastIndexOf(Object o) {
    
14.         int index = size;
    
15.         if (o == null) {
    
16.             for (Node<E> x = last; x != null; x = x.prev) {
    
17.                 index--;
    
18.                 if (x.item == null)
    
19.                     return index;
    
20.             }
    
21.         } else {
    
22.             for (Node<E> x = last; x != null; x = x.prev) {
    
23.                 index--;
    
24.                 if (o.equals(x.item))
    
25.                     return index;
    
26.             }
    
27.         }
    
28.         return -1;
    
29.     }
    

复制代码

------
原文链接：https://pdai.tech/md/java/collection/java-collection-LinkedList.html