List接口——LinkedList学习笔记

作者: Levi_moon | 来源:发表于2021-03-23 22:10 被阅读0次

LinkedList底层采用的是双向链表结构。

LinkedList的每个结点都是一个对象，包括前置指向prev、后置指向next、结点值item。链表首结点的前置指向为空null，尾结点的后置指向为空null。如果结点不是首结点或尾结点的话，结点值item可以为空null。

（一）底层实现原理

如同探究ArrayList底层实现原理从源码入手一样，探究LinkedList的底层实现原理也需要从源码入手。而解读源码的入口，当然还是构造器。

1. 从构造器入手

进入LinkedList的默认构造器，发现这个构造器内没有代码，是一个空的构造器。

public LinkedList() {
}

好吧，构造器内没有代码就没有吧。

总之，通过new LinkedList()后，一个新的LinkedList对象就被创建出来了。

2. 添加元素

LinkedList添加元素的方法有四种，分别是：add(element)、addFirst()、addLast()、add(index,element)。
其中add(element)方法和addLast()方法的实现逻辑一样，唯一不同的是addLast()没有返回值，而add(element)方法会返回true。add(index,element)方法是通过指定索引的方式添加新元素。

由于LinkedList底层实现是双向链表，因此，可以在链表的头部或尾部添加元素。我们先来看看在链表头部添加元素的实现逻辑。

2.1 在头部添加元素

在头部添加元素是调用addFirst()方法，这个方法的代码很简单，只有一行。

public void addFirst(E e) {
    linkFirst(e);
}

可以看到这个方法调用了linkFirst()方法，并且将待添加的元素当作该方法的入参。

接下来看看linkFirst()方法的代码是怎么写的。

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++;
}

可以看到方法体的第一行是由关键字final修饰的Node类型的变量f，并被first赋值。
这里有几个关键点，分别是：

被final关键字修饰，说明该变量只能被赋值一次，其值在当前作用域内（方法体内）不可被改变
Node类型是LinkedList类中的内部类，该类中主要是定义了三个属性：当前元素item、前一个元素的指向prev、后一个元素的指向next

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;
    }
}

first被赋值给变量f，而Java对first的定义是：链表的第一个结点，并且限定为：如果链表的第一个结点为空null的话，那么链表的最后一个结点也为空null；第一个结点没有前节点，并且第一个结点的元素值不能为空null

/**
  * Pointer to first node.
  * Invariant: (first == null && last == null) ||
  *            (first.prev == null && first.item != null)
  */
transient Node<E> first;

接着就是实例化一个新的链表结点，其中，前一个结点指向为null，后一个结点指向链表现有的第一个结点f（或者说是first更贴切）。

当新结点被实例化出来后，将该结点再赋值给first，这样新结点就变为了链表的第一个结点，这也符合从链表头添加元素的定义。

判断在本次添加元素时，第一个结点是不是为空null。如果为空，说明在本次添加元素之前，链表就是一个空链表，那么添加的新元素（结点）就是第一个结点也是最后一个结点；如果不为空，那么当前链表的第一个结点的前一个结点的指向就要从空null指向新建结点。

添加完成新结点后，链表的长度要加一size++;，链表被操作的次数也要被加一modCount++;。

上面对代码的解读有点繁琐，不利于理解其实现逻辑，接下来再整理下代码逻辑，用简略的语言再解释一遍。

在链表头部添加新结点的实现逻辑：

在为链表添加头结点时，首先要将链表头结点对象first赋值给不可变的属性f，代码：final Node<E> f = first;
接下来要新建一个结点，这个结点没有前结点（前结点要指向null），后结点要指向本次添加前链表的首结点f，代码：final Node<E> newNode = new Node<>(null, e, f);
将新建结点赋值给链表的首结点first，此时链表的首结点变成了本次新增结点操作时新增的结点，代码：first = newNode;
判断在本次新增结点操作前，链表是否有首结点（此时变量f指向的是新结点未创建时的(原)首结点），代码：if (f == null)
根据上一步的判断结果，决定新建结点的链接位置。若原链表为空（首结点为空null）的话，则新建结点既是首结点，也是尾结点last = newNode;；若原链表不为空（有首结点），则新建结点要链接在首结点之前f.prev = newNode;
新结点添加完成后，链表长度要加一size++;，链表操作次数要加一modCount++;，代码：size++;modCount++;

2.2 在尾部添加元素

在尾部添加新元素，调用的是addLast()方法。如同在头部添加元素一样，在尾部添加元素的方法也只有一行代码，调用的是linkLast()方法。

public void addLast(E e) {
    linkLast(e);
}

那么，我们来看下linkLast()方法的实现逻辑。

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++;
}

在链表尾部添加新元素的实现逻辑与在头部添加新元素的逻辑类似，下面我就以简略的语言概述下其实现逻辑。

在链表尾部添加新结点的实现逻辑：

在为链表添加尾结点时，首先要将链表尾结点对象last赋值给不可变的属性l，代码：final Node<E> l = last;
接下来要新建一个结点，这个结点没有后结点（后结点要指向null），前结点要指向本次添加前链表的尾结点l，代码：final Node<E> newNode = new Node<>(l, e, null);
将新建结点赋值给链表的尾结点last，此时链表的尾结点变成了本次新增结点操作时新增的结点，代码：last = newNode;
判断在本次新增结点操作前，链表是否有尾结点（此时变量l指向的是新结点未创建时的(原)尾结点），代码：if (l == null)
根据上一步的判断结果，决定新建结点的链接位置。若原链表为空（尾结点为空null）的话，则新建结点既是首结点，也是尾结点first = newNode;；若原链表不为空（有尾结点），则新建结点要链接在尾结点之后f.next= newNode;
新结点添加完成后，链表长度要加一size++;，链表操作次数要加一modCount++;，代码：size++;modCount++;

2.3 指定索引添加元素

当为链表添加元素时，一般是通过指定索引值来添加元素，因此，通过指定索引值添加元素方法的实现逻辑非常重要，值得我们花时间去研究。

通过指定索引值添加元素方法的代码如下：

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

首先还是要先检查传入的索引值是否在链表的索引范围内，调用的checkPositionIndex()方法，其主要校验逻辑是index >= 0 && index < size;，若传入的索引值不在链表索引范围内则抛出IndexOutOfBoundsException异常。代码：checkPositionIndex(index);
判断要添加的元素是否是在最后一个结点后添加，若是，则调用linkLast()方法；否则调用linkBefore()方法

tips：
需要对第二步的实现逻辑进行进一步的剖析：判断要添加的元素是否是在最后一个结点后添加，若是，则调用linkLast()方法；否则调用linkBefore()方法

若是在链表最后一个结点后再添加一个结点，调用的是linkLast()方法，linkLast()方法的实现逻辑在2.2 在尾部添加元素小节已经剖析完成了，这里就不再赘述了。关键的是对linkBefore()方法实现逻辑的剖析。

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

以上是linkBefore()方法的代码，其中两个入参：e是新添加的元素，succ是要添加位置的结点对象node(index)。

如果在指定索引位置添加新结点的话，那就会把以前在这个索引位置的结点往后“挤”一个位置，随之要把这个被“后挤”一个位置的结点与它前一结点之间的联系打断，并且在打断的位置添加上一个新结点，同时还要将新节点与被“后挤”一个位置的结点和前一结点再联系上。按照这一处理逻辑，用代码实现的话就可以分成这几步骤了：

获取原结点的前一结点的指向final Node<E> pred = succ.prev;
新建一个结点，这个结点的前一结点要指向原结点的前一结点，这个结点的后一结点要指向原结点final Node<E> newNode = new Node<>(pred, e, succ);
原结点由于被向后“挤”了一个位置，所以，原结点的前一结点现在要指向新结点succ.prev = newNode;
如果新结点被放在了链表的首结点位置上，那么新结点就是链表的首结点first = newNode;；否则，上一结点就要与新结点关联起来，即上一结点的后一结点要指向新结点pred.next = newNode;
链表的长度要加一size++;，链表被操作的次数要加一modCount++;

在指定索引位置添加结点的逻辑实现用示意图表示为：

在链表中添加一个新的结点node100

在原链表中添加新结点

首先要获取node1结点的前置指向previous

获取原结点的前置指向

新建一个结点，其前置指向原结点的前置指向，其后置指向原结点

新建结点，并设置好前（后）置指向

原结点的前置指向现在要改为新结点

原结点的前置指向改为新结点

原结点的前一结点的后置指向要改为新结点

原结点的前一结点的后置指向改为新结点

自此，一个新结点才算是真正的添加到了原链表中。

3. 修改元素

修改元素可以通过LinkedList自带的set()方法，也可以通过迭代器（ListItr）的set()方法。通过迭代器修改元素的话，需要先遍历集合，而且只能修改被遍历过的最后一个元素。

在此只讨论LinkedList自带的set()方法的实现逻辑。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

从set()方法可以看出，要想修改结点的值，需要传入索引值index和新元素element。

首先是检查索引值是否越界
接下来是调用node()方法，通过传入索引index，获取索引值对应的结点对象。代码：Node<E> x = node(index);
最后是获取索引对应结点的（原）值，并将新值赋值给结点，最终将原值返回。代码：E oldVal = x.item; x.item = element; return oldVal;

tips：
需要解释的是第二步的逻辑：接下来是调用node()方法，通过传入索引index，获取索引值对应的结点对象。代码：Node<E> x = node(index);
其中node()方法的作用是通过索引值获取对应的结点对象，其代码如下：

Node<E> node(int 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;
    }
}

从代码可以看到，先采用二分法的方式，定位索引对应的元素在链表的哪个位置if (index < (size >> 1))（size >> 1相当于size/2），然后再从链表的头（尾）向链表中部遍历，直到遍历到索引对应结点的前（后）一个结点时，结束遍历，当前结点的后（前）一个结点就是我们要找的结点。

寻找结点对象的逻辑很简单，但是只用文字描述还不够直观，俗话说一图抵千言，我们用画图的方式来解释下这段逻辑。

假设有个长度为11的链表，我需要获取第3个结点

长度为11的链表

判断希望获取的结点在链表的前半部分还是后半部分，由于index = 2，size = 11，通过判断可知结点在前半部分

if (index < (size >> 1)) {
    //结点在前半部分的处理逻辑
} else {
    //结点在后半部分的处理逻辑
}

知道要获取的结点在链表的前半部分，那么就从链表的头结点开始向后找，直到找到期望的结点为止

Node<E> x = first;
for (int i = 0; i < index; i++)
    x = x.next;

用画图来表示链表的查找逻辑：

当for循环结束时，x的值为上一个结点向后的指向x = x.next;

4. 查看元素

查看链表中结点的值，既可以通过LinkedList的get()方法，也可以通过迭代器（ListItr）的get()方法。我们只解析LinkedList的get()方法的实现逻辑。

get()方法的代码如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

从get()方法的代码可以看出，查看结点值的逻辑非常简单，

首先还是要检查索引是否越界checkElementIndex(index);
接着是通过node()方法获取结点对象，然后再取出结点中的值返回即可return node(index).item;

5. 删除元素

删除链表中的元素，可以通过迭代器（ListItr）的remove()方法，也可以使用LinkedList中的remove()方法，可以传入要删除元素的值，也可以传入要删除元素的索引值。这三种方法都可以删除链表中的元素，虽然处理逻辑不同，但是底层实现都是一样的，都是通过调用unlink()方法，将该结点的前置指向、后置指向、结点值置为空（null）。

以传入结点值删除结点的方法remove(o)为例

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

从代码可以看出，不管传入的值是空null还是有具体的值，都需要先从链表头遍历，直到链表找到与传入值相同的结点时，就去调用unlink()方法，入参是被定位到的结点对象。

接下来还是把主要精力放在unlink()方法上，毕竟这个方法是最基本的处理逻辑。

E unlink(Node<E> x) {
    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;
}

先取出传入结点的结点值item、结点的后置指向next、结点的前置指向prev。代码：final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev;
处理结点的前置指向。如果前置指向为空null，那么该结点为链表的首结点，删除该结点后，后一结点变成首结点first = next;；否则，前一结点的后置指向要指向被删除结点的后置指向prev.next = next;，并且当前结点的前置指向要置为空null。代码：if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }
处理结点的后置指向。如果后置指向为空null，那么该结点为链表的尾结点，删除该结点后，前一结点变成尾结点last = prev;；否则，后一结点的前置指向要指向被删除结点的前置指向next.prev = prev;，并且当前结点的后置指向要置为空null。代码：if (next == null) { last = prev; } else { next.prev = prev; x.next = null; }
处理结点的结点值。将结点值置为空null。代码：x.item = null;
链表长度减一size--;，链表操作次数加一modCount++;，最后返回被删除的结点

老规矩，还是用图说话。

假设有个链表，要删除其中一个结点node1

删除链表中的一个结点

删除node1结点的前置指向，将node1结点的前置指向previous置为空null，将node0结点的后置指向指到node2结点

结点的前置指向置为空，前一结点的后置指向指到后一结点

删除node1结点的后置指向，将node1结点的后置指向next置为空null，将node2结点的前置指向指到node0结点

结点的后置指向置为空，后一结点的前置指向指到前一结点

删除node1的结点值

删除结点值

自此，node1结点被从链表中删除掉了。

（二）总结

LinkedList是通过操作双向链表来实现对数据的增、删、改、查操作。采用双向链表的方式可以通过较低的代价进行插入和删除操作，但是它在随机访问方面相对较慢。

在使用List时，最佳的做法一般是采用ArrayList作为首选，只有在需要使用一些额外的功能，或者当程序的性能因为需要频繁的从表中间插入或删除操作而变差时，才应该去选择LinkedList。

List接口——LinkedList学习笔记

（一）底层实现原理

1. 从构造器入手

2. 添加元素

2.1 在头部添加元素

2.2 在尾部添加元素

2.3 指定索引添加元素

3. 修改元素

4. 查看元素

5. 删除元素

（二）总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读