Posts LinkedList源码分析
Post
Cancel

LinkedList源码分析

类图

image-20210707120008429

构造函数

1
2
3
4
5
6
7
8
9
transient int size = 0;
transient Node<E> first; //记录第一个节点
transient Node<E> last; //记录最后一个节点
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//调用addAll方法
}

添加

add()

1
2
3
4
public boolean add(E e) {
    linkLast(e);//调用linkLast
    return true;
}

addLast()

1
2
3
4
public void addLast(E e) {
    //add和addLast等价
    linkLast(e);
}
1
2
3
4
5
6
7
8
9
10
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void linkLast(E e) {
    final Node<E> l = last;
    //创建一个新节点
    final Node<E> newNode = new Node<>(l, e, null);
    //赋值给最后一个节点
    last = newNode;
    //如果最后一个节点为空说明链表中还没有元素,将创建的节点赋值给第一个节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

addFirst()

1
2
3
public void addFirst(E e) {
    linkFirst(e);
}
1
2
3
4
5
6
7
8
9
10
11
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

获取

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<E> node(int index) {
    // assert isElementIndex(index);
  //如果index<size/2从前面查否则从后面查找
    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
public E remove() {
    return removeFirst();
}
1
2
3
4
5
6
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
1
2
3
4
5
6
//根据索引删除
public E remove(int index) {
    checkElementIndex(index);
    //先调用node方法查找然后调用unlink删除
    return unlink(node(index));
}
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
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;
    //pre.next指向next
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    //next的prev指向prev
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}
This post is licensed under CC BY 4.0 by the author.