链表的实现

2023-12-25 22:41:29

单向循环链表

定义

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

图解

?链表内还有一种特殊的节点被称为哨兵(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 方法):如果链表为空,直接创建一个新节点作为头节点;如果链表不为空,创建一个新节点,将其指向原头节点,并更新头指针。
    • 遍历链表(looploop2 方法):通过循环遍历链表中的每个节点,对每个节点执行指定的操作。
    • 在链表尾部插入节点(addLast 方法):找到链表中的最后一个节点,然后在其后插入新节点;如果链表为空,直接在头部插入新节点。
    • 获取指定索引位置的节点值(get 方法):通过循环找到指定索引位置的节点,并返回其值。
    • 在指定索引位置插入节点(insert 方法):找到指定索引位置的上一个节点,然后在其后插入新节点;如果是在头部插入,直接调用头部插入的方法。
    • 删除指定索引位置的节点(removeFirstremove 方法):删除头节点或指定索引位置的节点,更新相邻节点的指针。

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

双向循环链表

图解

代码

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

文章来源:https://blog.csdn.net/weixin_67573348/article/details/135165382
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。