链表的实现

单向循环链表

定义

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

图解

?链表内还有一种特殊的节点被称为哨兵（Sentinel）节点，也叫做哑元，它不存储数据，通常用作头尾，用来简化边界判断。

链表的实现

package com.ma.test;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/2311:01
 * @function
 * @comment
 */
// 单向链表
public class SinglyLinkedList implements Iterable<Integer> {  // 整体

    private Node head = null; // 头指针

    /*
    节点类
     */
    private static class Node {
        int value; // 值
        Node next; // 下一个节点指针

        /**
         * 构造方法，创建一个节点
         *
         * @param value 值
         * @param next  下一个节点指针
         */
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 在链表头部插入一个值为 value 的节点
     *
     * @param value 要插入的节点值
     */
    public void addFirst(int value) {
        if (head == null) {
            // 链表为空，直接创建新节点作为头节点
            head = new Node(value, null);
        } else {
            // 链表不为空，创建新节点并更新头指针
            Node newNode = new Node(value, head);
            head = newNode;
        }
    }

    /**
     * 遍历链表，对每个节点执行指定的操作
     *
     * @param consumer 对每个节点执行的操作
     */
    public void loop(Consumer<Integer> consumer) {
        Node p = head;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    /**
     * 遍历链表，对每个节点执行指定的操作（使用 for 循环实现）
     *
     * @param consumer 对每个节点执行的操作
     */
    public void loop2(Consumer<Integer> consumer) {
        for (Node p = head; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    /**
     * 获取链表的迭代器，用于支持增强的 for 循环
     *
     * @return 迭代器对象
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int v = p.value;
                p = p.next;
                return v;
            }
        };
    }

    /**
     * 查找链表中的最后一个节点
     *
     * @return 最后一个节点，如果链表为空则返回 null
     */
    private Node findLast() {
        Node p = head;
        while (p != null && p.next != null) {
            p = p.next;
        }
        return p;
    }

    /**
     * 在链表尾部插入一个值为 value 的节点
     *
     * @param value 要插入的节点值
     */
    public void addLast(int value) {
        Node last = findLast();

        if (last == null) {
            // 链表为空，直接在头部插入
            addFirst(value);
        } else {
            // 在最后一个节点后插入新节点
            last.next = new Node(value, null);
        }
    }

    /**
     * 根据索引查找节点
     *
     * @param index 索引值
     * @return 索引位置的节点，如果索引非法则返回 null
     */
    private Node findNode(int index) {
        int i = 0;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    /**
     * 获取指定索引位置的节点值
     *
     * @param index 索引值
     * @return 索引位置的节点值，如果索引非法则抛出 IllegalArgumentException
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node == null) {
            Illega(index);
        }
        return node.value;
    }


    // 向索引位置插入一个值为 value 的节点
    public void insert(int index, int value) {
        // 向头部插入值
        if (index == 0) {
            addFirst(value);
            return;
        }

        // 找到索引位置的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            // 如果上一个节点为 null，说明索引非法
            Illega(index);
        }

        // 在上一个节点后插入新节点
        prev.next = new Node(value, prev.next);
    }

    // 删除链表中的第一个元素
    public void removeFirst() {
        if (head == null) {
            // 如果链表为空，抛出索引非法异常
            Illega(0);
        }
        // 更新头指针，跳过第一个节点
        head = head.next;
    }

    // 根据索引位置删除节点
    public void remove(int index) {
        // 删除头节点的情况
        if (index == 0) {
            removeFirst();
            return;
        }

        // 找到索引位置的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            // 如果上一个节点为 null，说明索引非法
            Illega(index);
        }

        // 被删除的节点
        Node removed = prev.next;
        if (removed == null) {
            // 如果被删除的节点为 null，说明索引非法
            Illega(index);
        }

        // 更新上一个节点的 next 指针，跳过被删除的节点
        prev.next = removed.next;
    }

    // 抛出 IllegalArgumentException 异常，表示索引非法
    private void Illega(int index) {
        throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

}

测试

    static void t2() {
        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        singlyLinkedList.addLast(1);
        singlyLinkedList.addLast(2);
        singlyLinkedList.addLast(3);
        singlyLinkedList.addLast(4);

        singlyLinkedList.remove(2);
        for (Integer value : singlyLinkedList) {
            System.out.println(value);
        }


    }

思路

这是一个单向链表（Singly Linked List）的简单实现。单向链表是一种数据结构，其中的元素按顺序存储，并通过每个元素中的指针链接到下一个元素，形成一个链条。在这个实现中，链表的基本结构如下：

1. 节点类 Node：

   • Node 类表示链表中的每个节点，包含两个字段：value 存储节点的值，next 存储指向下一个节点的引用。

2. 链表类 SinglyLinkedList：

   • SinglyLinkedList 类表示整个单向链表，包含一个头指针 head，指向链表的第一个节点。
   • 提供了基本的链表操作方法，如在头部插入节点、遍历链表、在尾部插入节点、获取指定索引位置的节点值、在指定索引位置插入节点、删除指定索引位置的节点等。
   • 实现了 Iterable 接口，使得链表对象可以通过增强的 for 循环遍历。

3. 思路概述：

   • 在链表头部插入节点（addFirst 方法）：如果链表为空，直接创建一个新节点作为头节点；如果链表不为空，创建一个新节点，将其指向原头节点，并更新头指针。
   • 遍历链表（loop 和 loop2 方法）：通过循环遍历链表中的每个节点，对每个节点执行指定的操作。
   • 在链表尾部插入节点（addLast 方法）：找到链表中的最后一个节点，然后在其后插入新节点；如果链表为空，直接在头部插入新节点。
   • 获取指定索引位置的节点值（get 方法）：通过循环找到指定索引位置的节点，并返回其值。
   • 在指定索引位置插入节点（insert 方法）：找到指定索引位置的上一个节点，然后在其后插入新节点；如果是在头部插入，直接调用头部插入的方法。
   • 删除指定索引位置的节点（removeFirst 和 remove 方法）：删除头节点或指定索引位置的节点，更新相邻节点的指针。

这个实现是链表数据结构的基础，可以用于在不需要连续内存分配的情况下动态管理数据。链表的特点是插入和删除操作相对高效，但随机访问某个位置的元素相对较慢。

双向循环链表

图解

代码

package com.ma.lianbiao;

import java.util.Iterator;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/2517:27
 * @function
 * @comment
 */

// 双向循环列表
public class DoublyLinkedListSentinel implements Iterable<Integer> {

    static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针


        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }

    }

    private Node head;
    private Node tail;

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            Illega(index);
        }
        Node removed = prev.next;
        if (removed == tail) {
            Illega(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;
    }


    void removeFirst() {
        remove(0);
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void insert(int index, int value) {
        Node prev = findNode(index - 1);

        if (prev == null) {
            Illega(index);
        }

        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;
    }

    private void addLast(int value) {
        Node last = tail.prev;
        Node added = new Node(last, value, tail);
        last.next = added;
        tail.prev = added;
    }

    public void First(int value) {

    }

    public void removeLast() {
        Node removed = tail.prev;
        if (removed == head) {
            Illega(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    // 抛出 IllegalArgumentException 异常，表示索引非法
    private void Illega(int index) {
        throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            private Node current = head.next; 

            @Override
            public boolean hasNext() {
                return current != tail;
            }

            @Override
            public Integer next() {
                if (!hasNext()) {
                    throw new IllegalStateException("No more elements");
                }
                int value = current.value;
                current = current.next;
                return value;
            }
        };
    }
}

环形链表

定义

双向环形链表带哨兵，这是哨兵即作为头，也作为尾。

图解

代码

package com.ma.lianbiao;

import java.util.Iterator;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/2520:37
 * @function
 * @comment
 */
public class DoublyLinkedListSentinelx implements Iterable<Integer> {
    private static class Node {

        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }


    private Node sentinel = new Node(null, -1, null);

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    public void removeFirst() {
        Node removed = sentinel.next;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    public void removeLast() {
        Node removed = sentinel.prev;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    public void addLast(int value) {
        Node a = sentinel.prev;
        Node b = sentinel;
        Node added = new Node(a, value, b);
        a.next = added;
        b.prev = added;
    }

    public DoublyLinkedListSentinelx() {
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }

    public void addFirst(int value) {
        Node a = sentinel;
        Node b = sentinel.next;
        Node added = new Node(a, value, b);
        a.next = added;
        b.prev = added;
    }

    private Node findByValue(int value) {
        Node p = sentinel.next;
        while (p != sentinel) {
            if (p.value == value) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public void removeByValue(int value) {
        Node removed = findByValue(value);
        if (removed == null) {
            return;
        }
        Node a = removed.prev;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    private void Illega(int index) {
        throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }
}