java源码解读--linkedList

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

linkedlist

  1. 底层采用双向链表实现，插入O(1)，查找On)
  2. 实现了deque接口，可以进行队列操作，在此不做分析
  3. fail-fast机制，防止结构意外改变

基础结构

linkedlist内部采用双向链表结构存储数据，其内部定义了Node数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   private static class Node<E> {
//值
       E item;
//前向指针
       Node<E> next;
//后向指针
       Node<E> prev;

       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }

构造方法

linkedlist有两个构造方法，一种用于构造空链表，一种用传入的集合创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

添加元素

add(E e)

把新节点加入到链表末尾，所以调用linklast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   public boolean add(E e) {
       linkLast(e);
       return true;
   }

   /**
    * Links e as last element.
    */
   void linkLast(E e) {
//获取原来最后一个元素
       final Node<E> l = last;
//创建新元素对应的node，并将前向指针指向原来最后一个元素
       final Node<E> newNode = new Node<>(l, e, null);
//把last指向新插入的元素
       last = newNode;
       if (l == null)
    //如果原来最后一个元素是null，说明新加入的元素是第一个元素，所以first也指向该元素
           first = newNode;
       else
    //如果原来链表中存在元素，则把倒数第二个元素的后向指针指向新元素	
           l.next = newNode;
       size++;
       modCount++;
   }

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
   public void add(int index, E element) {
//检查index是否合法
       checkPositionIndex(index);

       if (index == size)
    //如果是在最后一个位置增加元素，则调用linklast方法
           linkLast(element);
       else
    //否则调用linkBefore
           linkBefore(element, node(index));
   }


   private void checkPositionIndex(int index) {
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

   private boolean isPositionIndex(int index) {
//下标范围[0,size]
       return index >= 0 && index <= size;
   }

调用linkBefore

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
   //根据下标查找node
   Node<E> node(int index) {
       // assert isElementIndex(index);
//如果是前半部分，则从前向后查找
       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;
       }
  }

   /**
    * Inserts element e before non-null Node succ.
    */
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
//找到succ前向节点
       final Node<E> pred = succ.prev;
//新建节点，并连接前后节点
       final Node<E> newNode = new Node<>(pred, e, succ);
//改变succ节点的前向指针
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
   //改变pre的后项指针
           pred.next = newNode;
       size++;
       modCount++;
   }

删除元素

remove(Object o)

删除指定元素

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
   public boolean remove(Object o) {
       if (o == null) {
	//如果是值等于null，从first开始遍历，依次查找node的值是否为null
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
	//如果不是null，从fist开始遍历，用equals判断是否相等
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
   }

//删除某个节点
 /**
    * Unlinks non-null node x.
    */
   E unlink(Node<E> x) {
       // assert x != null;
       final E element = x.item;
       final Node<E> next = x.next;
       final Node<E> prev = x.prev;

       if (prev == null) {
           first = next;
       } else {
           prev.next = next;
           x.prev = null;
       }

       if (next == null) {
           last = prev;
       } else {
           next.prev = prev;
           x.next = null;
       }

       x.item = null;
       size--;
       modCount++;
       return element;
   }

remove(int index)

移除指定位置元素

1
2
3
4
5
6
   public E remove(int index) {
//检查index是否合法
       checkElementIndex(index);
//删除改位置节点
       return unlink(node(index));
   }

remove()

删除头节点

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
public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeFirstOccurrence(Object o)

删除第一次出现的元素

1
2
3
4
//底层借助remove实现
   public boolean removeFirstOccurrence(Object o) {
       return remove(o);
   }

removeLastOccurrence(Object o)

删除最后一次出现的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

查找元素

get(int index)

1
2
3
4
5
6
   public E get(int index) {
//检查下标是否合法
       checkElementIndex(index);
//根据下标查找到对应node并返回该节点的元素值
       return node(index).item;
   }

indexOf(Object o)

从前向后遍历，返回改元素第一次出现的下标位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   public int indexOf(Object o) {
       int index = 0;
//目标元素是null的情况
       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) {
	//使用equals判断对象是否相等
               if (o.equals(x.item))
                   return index;
               index++;
           }
       }
       return -1;
   }

lastIndexOf(Object o)

从后向前遍历，返回该元素第一次出现的位置，如果没有匹配元素返回-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;
}

迭代器

linkedlist可返回的迭代器和arraylist类似，都有Itr和ListItr，但是linkedlist能返回DescendingIterator，DescendingIterator用于反向遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
//基于ListItr实现
   private class DescendingIterator implements Iterator<E> {
       private final ListItr itr = new ListItr(size());
       public boolean hasNext() {
           return itr.hasPrevious();
       }
       public E next() {
           return itr.previous();
       }
       public void remove() {
           itr.remove();
       }
   }

clone

linkedlist实现了cloneable接口，表明linkedlist可以复制
linkedlist的clone方法调用了Object的clone，该方法为浅复制；链表复制时，add方法也只是拿到了x的指针，所以linkedlist的clone方法也是浅复制

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
   public Object clone() {
//产生新链表
       LinkedList<E> clone = superClone();
//初始化新链表
       // Put clone into "virgin" state
       clone.first = clone.last = null;
       clone.size = 0;
       clone.modCount = 0;
//复制链表
       // Initialize clone with our elements
       for (Node<E> x = first; x != null; x = x.next)
           clone.add(x.item);

       return clone;
   }

   @SuppressWarnings("unchecked")
   private LinkedList<E> superClone() {
       try {
	//浅克隆
           return (LinkedList<E>) super.clone();
       } catch (CloneNotSupportedException e) {
           throw new InternalError(e);
       }
   }
-------------本文结束感谢您的阅读-------------

本文标题:java源码解读--linkedList

文章作者:小建儿

发布时间:2018年05月28日 - 20:05

最后更新:2018年05月28日 - 20:05

原始链接:http://yajian.github.io/java源码解读-linkedList/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多