[Java] 单链表

什么是单链表

单链表是链表的其中一种基本结构。它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点，称为单链表。

顺序表与单链表的区别

顺序表

(顺序存储)

优点：可随机存取，存储密度高缺点：要求大片连续空间，改变容量不方便

单链表

(链式存储)

优点：不要求大片连续空间，改变容量方便缺点：不可随机存取，要耗费一定空间存放指针（地址）

单链表结构

public class SinglyLinkedList <T> {

    /**
     * 头结点
     */
    private Node head;

    /**
     * 链表长度
     */
    private int size;

    /**
     * 结点
     */
    class Node {

        /**
         * 结点数据
         */
        private T t;

        /**
         * 下一个结点
         */
        private Node next;

        Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }

        public Node(T t) {
            this(t, null);
        }

        @Override
        public String toString() {
            return "Node{" + t + '}';
        }
    }
}

单链表基本操作

插入

/**
* 在指定下标处插入一个结点

* @param t
* @param index
* @return
*/
public boolean insert(T t, int index) {

    if (index < 0 || index > size) {
        throw new IllegalArgumentException("非法下标参数");
    }

    Node node = new Node(t);
    // 链表头部插入结点
    if (index == 0) {
        node.next = this.head;
        this.head = node;
        this.size++;
        return true;
    }

    // 找到要插入结点的前一个结点
    Node preNode = getNode(index - 1);
    // 前一个结点的下一个结点地址赋给当前结点的 next
    node.next = preNode.next;
    // 当前结点的地址赋给前一个结点的 next
    preNode.next = node;
    this.size++;
    return true;
}

这里的插入是一个后插操作，既在某个结点之后插入一个结点，因为结点中存有下一个结点的地址，所以其后面的结点都很好寻找和操作了。对应的还有前插操作，既在某个结点之前插入一个结点，这要求得拿到前一个结点，才能改变前结点的 next 指向。要拿到前一个结点，可以从头结点开始，依次寻找，有了头结点就等于有了整个单链表。如果没有头结点，就无法拿到前一个结点。此时只能对当前结点使用后插操作，在交换两个结点当中的数据，变相地实现了前插操作。

删除

/**
 * 根据下标删除结点
 *
 * @param index
 * @return
 */
public Node remove(int index) {

    if (index < 0 || index > size) {
        throw new IllegalArgumentException("非法下标参数");
    }
    Node removeNode = null;
    // 删除头结点
    if (index == 0) {
        removeNode = this.head;
        // 把头结点的下一结点作为头节点
        this.head = head.next;
        this.size--;
        return removeNode;
    }
    // 找到删除结点的前一结点
    Node preNode = getNode(index - 1);
    // 把要删除的结点保存和返回
    removeNode = preNode.next;
    // 把前一结点的下下个结点地址赋值给前一结点的 next
    preNode.next = preNode.next.next;
    this.size--;
    return removeNode;
}

/**
 * 根据数据删除结点
 *
 * @param t
 * @return
 */
public Node remove(T t) {
    // 链表或元素为空 直接返回
    if (size == 0 || null == t) {
        return null;
    }

    Node removeNode = null;
    for (int i = 0; i < size; i++) {
        Node node = getNode(i);
        if (t == node.t) {
            removeNode = remove(i);
            break;
        }
    }
    return removeNode;
}

查找

/**
 * 根据下标获取一个结点
 *
 * @param index
 * @return
 */
public Node getNode(int index) {

    if (index < 0 || index > size) {
        throw new IllegalArgumentException("非法下标参数");
    }
    Node curNode = this.head;
    // 下标为 0 直接返回头结点
    if (index == 0) {
        return curNode;
    }
    for (int i = 0; i < index; i++) {
        curNode = curNode.next;
    }
    return curNode;
}

/**
 * 根据元素值返回对应下标
 *
 * @param t
 * @return
 */
public Node getNode(T t) {

    // 从头结点开始
    Node curNode = this.head;
    // 当前结点不为空且结点数据不等于传入元素
    while (null != curNode && curNode.t != t) {
        // 当前结点后移
        curNode = curNode.next;
    }
    return curNode;
}

完整代码

/**
 * @description: 自定义单链表
 * @author: opoa
 * @create: 2021-02-28 20:21
 **/
public class SinglyLinkedList <T> {

    /**
     * 头结点
     */
    private Node head;

    /**
     * 链表元素个数
     */
    private int size;

    /**
     * 结点
     */
    class Node {

        /**
         * 结点数据
         */
        private T t;

        /**
         * 下一个结点
         */
        private Node next;

        Node(T t, Node next) {
            this.t = t;
            this.next = next;
        }

        public Node(T t) {
            this(t, null);
        }

        @Override
        public String toString() {
            return "Node{" + t + '}';
        }
    }

    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    /**
     * 根据下标获取一个结点
     *
     * @param index
     * @return
     */
    public Node getNode(int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法下标参数");
        }
        Node curNode = this.head;
        // 下标为 0 直接返回头结点
        if (index == 0) {
            return curNode;
        }
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        return curNode;
    }

    /**
     * 根据元素值返回对应下标
     *
     * @param t
     * @return
     */
    public Node getNode(T t) {

        // 从头结点开始
        Node curNode = this.head;
        // 当前结点不为空且结点数据不等于传入元素
        while (null != curNode && curNode.t != t) {
            // 当前结点后移
            curNode = curNode.next;
        }
        return curNode;
    }

    /**
     * 在指定下标处插入一个结点
     *
     * @param t
     * @param index
     * @return
     */
    public boolean insert(T t, int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法下标参数");
        }

        Node node = new Node(t);
        // 链表头部插入结点
        if (index == 0) {
            node.next = this.head;
            this.head = node;
            this.size++;
            return true;
        }

        // 找到要插入结点的前一个结点
        Node preNode = getNode(index - 1);
        // 前一个结点的下一个结点地址赋给当前结点的 next
        node.next = preNode.next;
        // 当前结点的地址赋给前一个结点的 next
        preNode.next = node;
        this.size++;
        return true;
    }

    /**
     * 使用头插法插入一个元素
     *
     * @param t
     * @return
     */
    public boolean insertFirst(T t) {
        return insert(t, 0);
    }

    /**
     * 使用尾插法插入一个元素
     *
     * @param t
     * @return
     */
    public boolean insertLast(T t) {
        return insert(t, size);
    }

    /**
     * 根据下标删除结点
     *
     * @param index
     * @return
     */
    public Node remove(int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法下标参数");
        }
        Node removeNode = null;
        // 删除头结点
        if (index == 0) {
            removeNode = this.head;
            // 把头结点的下一结点作为头节点
            this.head = head.next;
            this.size--;
            return removeNode;
        }
        // 找到删除结点的前一结点
        Node preNode = getNode(index - 1);
        // 把要删除的结点保存和返回
        removeNode = preNode.next;
        // 把前一结点的下下个结点地址赋值给前一结点的 next
        preNode.next = preNode.next.next;
        this.size--;
        return removeNode;
    }

    /**
     * 根据数据删除结点
     *
     * @param t
     * @return
     */
    public Node remove(T t) {
        // 链表或元素为空 直接返回
        if (size == 0 || null == t) {
            return null;
        }

        Node removeNode = null;
        for (int i = 0; i < size; i++) {
            Node node = getNode(i);
            if (t == node.t) {
                removeNode = remove(i);
                break;
            }
        }
        return removeNode;
    }

    /**
     * 返回当前链表长度
     *
     * @return
     */
    public int length() {
        return this.size;
    }

    /**
     * 打印输出单链表
     *
     * @return
     */
    @Override
    public String toString() {

        if (size == 0) {
            return null;
        }
        Node curNode = this.head;
        StringBuilder sb = new StringBuilder();
        while (null != curNode) {
            sb.append(curNode.t.toString())
              .append(" -> ");
            curNode = curNode.next;
        }
        sb.append("null");
        return sb.toString();
    }
}

参考资料

2020 王道考研数据结构【单链表的定义】
2020 王道考研数据结构【单链表的插入删除】
2020 王道考研数据结构【单链表的查找】
Java 基础 – 单链表的实现