6L-单向链表实现

关注公众号 MageByte，有你想要的精彩内容。文中涉及的代码可访问 GitHub:https://github.com/UniqueDong/algorithms.git

上一篇《链表导论心法》讲解了链表的理论知识以及链表操作的实现原理。talk is cheap, show me the code ! 今天让我以一起把代码撸一遍，在写代码之前一定要根据上一篇的原理多画图才能写得好代码。举例画图，辅助思考。

废话少说，撸起袖子干。

接口定义

首先我们定义链表的基本接口,为了显示出 B 格，我们模仿我们 Java 中的 List 接口定义。

package com.zero.algorithms.linear.list;

public interface List<E> {

    /**

     * Returns <tt>true</tt> if this list contains no elements.

     *

     * @return true if this list contains no elements

     */

    boolean isEmpty();

    /**

     * Returns the number of elements in this list.

     *

     * @return the number of elements in this list

     */

    int size();

    /**

     * Returns the element at the specified position in this list.

     * @param index index of the element to return

     * @return the element at the specified position in this list

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    E get(int index);

    /**

     * Appends the specified element to the end of this list (optional operation).

     *

     * @param e element to be appended to this list

     * @return

     */

    boolean add(E e);

    /**

     * Inserts the specified element at the specified position in this list

     * (optional operation).  Shifts the element currently at that position

     * (if any) and any subsequent elements to the right (adds one to their

     * indices).

     *

     * @param index   index at which the specified element is to be inserted

     * @param element element to be inserted

     */

    void add(int index, E element);

    /**

     * return true if this list contains the specified element

     *

     * @param o element whose presence in this list is to be tested

     * @return true if this list contains the specified element

     */

    boolean contains(Object o);

    /**

     * Removes the first occurrence of the specified element from this list,

     * if it is present (optional operation).

     *

     * @param o element to be removed from this list, if present

     * @return <tt>true</tt> if this list contained the specified element

     */

    boolean remove(Object o);

    /**

     * Removes the element at the specified position in this list (optional

     * operation).  Shifts any subsequent elements to the left (subtracts one

     * from their indices).  Returns the element that was removed from the

     * list.

     *

     * @param index the index of the element to be removed

     * @return the element previously at the specified position

     */

    E remove(int index);

    /**

     * Returns the index of the first occurrence of the specified element

     * in this list, or -1 if this list does not contain the element.

     * More formally, returns the lowest index <tt>i</tt> such that

     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,

     * or -1 if there is no such index.

     *

     * @param o element to search for

     * @return the index of the first occurrence of the specified element in

     * this list, or -1 if this list does not contain the element

     */

    int indexOf(Object o);

}

抽象链表模板

看起来是不是很像骚包，接着我们再抽象一个抽象类，后续我们还会继续写双向链表，循环链表。双向循环链表。把他们的共性放在抽象类中，将不同点延迟到子类实现。

package com.zero.algorithms.linear.list;

public abstract class AbstractList<E> implements List<E> {

    protected AbstractList() {

    }

    public abstract int size();

    /**

     * Inserts the specified element at the beginning of this list.

     *

     * @param e the element to add

     */

    public abstract void addFirst(E e);

    @Override

    public boolean isEmpty() {

        return size() == 0;

    }

    public void add(int index, E element) {

        throw new UnsupportedOperationException();

    }

    public E remove(int index) {

        throw new UnsupportedOperationException();

    }

    /**

     * check index

     * @param index to check

     */

    public final void checkPositionIndex(int index) {

        if (!isPositionIndex(index))

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    /**

     * Tells if the argument is the index of a valid position for an

     * iterator or an add operation.

     */

    private boolean isPositionIndex(int index) {

        return index >= 0 && index <= size();

    }

    /**

     * Constructs an IndexOutOfBoundsException detail message.

     * Of the many possible refactorings of the error handling code,

     * this "outlining" performs best with both server and client VMs.

     */

    private String outOfBoundsMsg(int index) {

        return "Index: " + index + ", Size: " + size();

    }

    public final void checkElementIndex(int index) {

        if (!isElementIndex(index))

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    /**

     * Tells if the argument is the index of an existing element.

     */

    private boolean isElementIndex(int index) {

        return index >= 0 && index < size();

    }

}

Node 节点

单向链表的每个节点有两个字段，一个用于保存当前节点的数据 item，另外一个则是指向下一个节点的 next 指针。所以我们在单向链表定义一个静态内部类表示 Node 节点。

构造方法分别将数据构建成 Node 节点，默认 next 指针是 null。

    /**

     * Node data

     *

     * @param <E>

     */

    private static class Node<E> {

        /**

         * Node of data

         */

        E item;

        /**

         * pointer to next Node

         */

        Node<E> next;

        public Node(E item, Node<E> next) {

            this.item = item;

            this.next = next;

        }

        public Node(E item) {

            this(item, null);

        }

    }

单项链表，size 属性保存当前节点数量，Node<E> head指向第一个节点的指针，并且存在

(head == null && last == null) || (head.prev == null && head.item !=null)

是真事件。以及 last指针指向最后的节点。最后我们还要重写 toString 方法，便于测试。

代码如下所示：

public class SingleLinkedList<E> extends AbstractList<E> {

    transient int size = 0;

    /**

     * pointer to head node

     */

    transient Node<E> head;

    /**

     * pointer to last node

     */

    transient Node<E> last;

    public SingleLinkedList() {

    }

    @Override

    public String toString() {

        StringBuilder sb = new StringBuilder();

        Node<E> cur = this.head;

        while (Objects.nonNull(cur)) {

            sb.append(cur.item).append("->");

            cur = cur.next;

        }

        sb.append("NULL");

        return sb.toString();

    }

}

添加元素

添加元素可能存在三种情况：

头结点添加。
中间任意节点添加。
尾节点添加。

在尾节点添加

将数据构造成 newNode 节点，将原先的 last 节点 next 指向 newNode 节点，如果 last 节点是 null 则将 head 指向 newNode ，同时 size + 1。

public boolean add(E e) {

        linkLast(e);

        return true;

}

    /**

     * Links e as last element

     *

     * @param e data

     */

    private void linkLast(E e) {

        // 先取出原 last node

        final Node<E> l = last;

        final Node<E> newNode = new Node<>(e);

        // 修改 last 指针到新添加的 node

        last = newNode;

        // 如果原 last 是 null 则将 newNode 设置为 head，不为空则原 last.next 指针 = newNode

        if (Objects.isNull(l)) {

            head = newNode;

        } else {

            l.next = newNode;

        }

        size++;

    }

在头结点添加

将数据构造成 newNode 节点，同时 newNode.next 指向原先 head节点，并将 head 指向 newNode 节点，如果 head == null 标识当前链表还没有数据，将 last 指针指向 newNOde 节点。

    @Override

    public void addFirst(E e) {

        final Node<E> h = this.head;

        // 构造新节点,next 指向原先的 head

        final Node<E> newNode = new Node<>(e, h);

        head = newNode;

        // 如果原先的 head 节点为空，则 last 指针也指向新节点

        if (Objects.isNull(h)) {

            last = newNode;

        }

        size++;

    }

在指定位置添加

分两种情况，当 index = size 的时候意味着在最后节点添加，否则需要找到当前链表指定位置的节点元素，并在该元素前面插入新的节点数据，重新组织两者节点的 next指针。

linkLast 请看前面，这里主要说明 linkBefore。

首先我们先查询出 index 位置的 Node 节点，并将 newNode.next 指向该节点。同时还需要找到index 位置的上一个节点，将 pred.next = newNode。这样就完成了节点的插入，我们只要画图辅助思考就很好理解了。

    @Override

    public void add(int index, E element) {

        checkPositionIndex(index);

        if (index == size) {

            linkLast(element);

        } else {

            linkBefore(element, index);

        }

    }

    /**

     * Inserts element e before non-null Node of index.

     */

    void linkBefore(E element, int index) {

        final Node<E> newNode = new Node<>(element, node(index));

        if (index == 0) {

            head = newNode;

        } else {

            Node<E> pred = node(index - 1);

            pred.next = newNode;

        }

        size++;

    }

    /**

     * Returns the (non-null) Node at the specified element index.

     */

    Node<E> node(int index) {

        Node<E> x = this.head;

        for (int i = 0; i < index; i++) {

            x = x.next;

        }

        return x;

    }

判断是否存在

indexOf(Object o) 用于查找元素所在位置，若不存在则返回 -1。

    @Override

    public boolean contains(Object o) {

        return indexOf(o) != -1;

    }

    @Override

    public int indexOf(Object o) {

        int index = 0;

        if (Objects.isNull(o)) {

            for (Node<E> x = head; x != null; x = x.next) {

                if (x.item == null) {

                    return index;

                }

                index++;

            }

        } else {

            for (Node<E> x = head; x != null; x = x.next) {

                if (o.equals(x.item)) {

                    return index;

                }

                index++;

            }

        }

        return -1;

    }

查找方法

根据 index 查找该位置的节点数据，其实就是遍历该链表。所以这里的时间复杂度是 O(n)。

    @Override

    public E get(int index) {

        return node(index).item;

    }

删除节点

删除有两种情况，分别是删除指定位置的节点和根据数据找到对应的节点删除。

先来看第一种根据 index 删除节点:

先检验 index 是否合法，然后根据 index 找到待删除 node。这里的删除比较复杂，老铁们记得多画图来辅助理解，防止出现指针指向错误造成意想不到的结果。

    @Override

    public E remove(int index) {

        checkElementIndex(index);

        return unlink(node(index));

    }

    public final void checkElementIndex(int index) {

        if (!isElementIndex(index))

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    /**

     * Tells if the argument is the index of an existing element.

     */

    private boolean isElementIndex(int index) {

        return index >= 0 && index < size();

    }

最难理解的就是后面这段代码了，但是只要多画图，多思考就好多了。

x 节点就是当前要删除的节点数据，我们先把该节点保存的 item 以及 next 指针保存到临时变量。第 10 ~13 这块 while 循环主要是用于找出被删除节点的引用 cur 以及上一个节点的引用 prev。
在找到被删除的 cur 指针以及 cur 上一个节点指针 prev 后我们做删除操作，这里有三种情况：当链表只有一个节点的时候，当一个以上节点情况下分为删除头结点、尾节点、其他节点。

    /**

     * Unlinks non-null node x.

     */

    E unlink(Node<E> x) {

        final E item = x.item;

        final Node<E> next = x.next;

        Node<E> cur = head;

        Node<E> prev = null;

        // 寻找被删除 node cur 节点以及 cur 的上一个节点 prev

        while (!cur.item.equals(item)) {

            prev = cur;

            cur = cur.next;

        }

        // 当只有一个节点的时候 prev  = null,next = null

        // 如果删除的是头结点，则 head = x.next，否则 prev.next = next 打断与被删除节点的联系

        if (prev == null) {

            head = next;

        } else {

            prev.next = next;

        }

        // 如果删除最后一个节点，则 last 指向 prev，否则打断被删除的节点 next = null

        if (next == null) {

            last = prev;

        } else {

            x.next = null;

        }

        size--;

        x.item = null;

        return item;

    }

单元测试

我们使用 junit做单元测试，引入maven 依赖。

<dependencies>

        <dependency>

            <groupId>org.junit.jupiter</groupId>

            <artifactId>junit-jupiter-engine</artifactId>

            <version>5.5.2</version>

            <scope>test</scope>

        </dependency>

        <dependency>

            <groupId>org.junit.jupiter</groupId>

            <artifactId>junit-jupiter-params</artifactId>

            <version>5.5.2</version>

            <scope>test</scope>

        </dependency>

    </dependencies>

创建测试用例

package com.zero.linkedlist;

import com.zero.algorithms.linear.list.SingleLinkedList;

import org.junit.jupiter.api.*;

import org.junit.jupiter.params.ParameterizedTest;

import org.junit.jupiter.params.provider.ValueSource;

@DisplayName("单向链表测试")

public class SingleLinkedListTest {

    SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

    @BeforeAll

    public static void init() {

    }

    @AfterAll

    public static void cleanup() {

    }

    @BeforeEach

    public void tearup() {

        System.out.println("当前测试方法开始");

        System.out.println(singleLinkedList.toString());

    }

    @AfterEach

    public void tearDown() {

        System.out.println("当前测试方法结束");

        System.out.println(singleLinkedList.toString());

    }

    @DisplayName("add 默认末尾添加")

    @Test

    void testAdd() {

        singleLinkedList.add(1);

        singleLinkedList.add(2);

    }

    @DisplayName("在指定位置添加 add")

    @Test

    void testAddIndex() {

        singleLinkedList.add(0, 1);

        singleLinkedList.add(0, 0);

        singleLinkedList.add(1, 2);

    }

    @DisplayName("addFirst 表头添加测试")

    @Test

    void testAddFirst() {

        singleLinkedList.addFirst(0);

        singleLinkedList.addFirst(1);

    }

    @DisplayName("contains 测试")

    @ParameterizedTest

    @ValueSource(ints = {1})

    void testContains(int e) {

        singleLinkedList.add(e);

        boolean contains = singleLinkedList.contains(e);

        Assertions.assertTrue(contains);

    }

    @DisplayName("testIndexOf")

    @ParameterizedTest

    @ValueSource(ints = {3})

    void testIndexOf(int o) {

        singleLinkedList.add(1);

        singleLinkedList.add(2);

        singleLinkedList.add(3);

        int indexOf = singleLinkedList.indexOf(o);

        Assertions.assertEquals(2, indexOf);

    }

    @DisplayName("test Get")

    @Test

    void testGet() {

        singleLinkedList.addFirst(3);

        singleLinkedList.addFirst(2);

        singleLinkedList.addFirst(1);

        Integer result = singleLinkedList.get(1);

        Assertions.assertEquals(2, result);

    }

    @DisplayName("testRemoveObject 删除")

    @Test

    void testRemoveObjectWithHead() {

        singleLinkedList.add(1);

        singleLinkedList.add(2);

        singleLinkedList.add(3);

        singleLinkedList.addFirst(0);

        singleLinkedList.remove(0);

        singleLinkedList.remove(Integer.valueOf(3));

        singleLinkedList.remove(Integer.valueOf(2));

        singleLinkedList.remove(Integer.valueOf(1));

    }

}

到这里单向链表的代码就写完了，我们一定要多写才能掌握指针打断的正确操作，尤其是在删除操作最复杂。

课后思考

Java 中的 LinkedList 是什么链表结构呢？
如何 java 中的LinkedList 实现一个 LRU 缓存淘汰算法呢？

加群跟我们一起探讨，欢迎关注 MageByte，我第一时间解答。

巴特西