List接口——LinkedList学习笔记

2021-03-23  本文已影响0人  Levi_moon

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赋值。
这里有几个关键点，分别是：

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

/**
  * 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++;。

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

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

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

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

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

2.3 指定索引添加元素

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

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

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

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

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)。

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

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

在原链表中添加新结点 获取原结点的前置指向 新建结点，并设置好前（后）置指向 原结点的前置指向改为新结点 原结点的前一结点的后置指向改为新结点

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

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。

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的链表 
if (index < (size >> 1)) {
    //结点在前半部分的处理逻辑
} else {
    //结点在后半部分的处理逻辑
}

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

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

4. 查看元素

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

get()方法的代码如下：

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

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

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

老规矩，还是用图说话。

删除链表中的一个结点 结点的前置指向置为空，前一结点的后置指向指到后一结点 结点的后置指向置为空，后一结点的前置指向指到前一结点 删除结点值

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

（二）总结

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

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

上一篇 下一篇

猜你喜欢

热点阅读