Java单链表的实现代码

下面是关于Java单链表的实现代码的完整攻略：

什么是单链表？

单链表是一种常见的数据结构，它由节点构成，每个节点包括一个数据域和一个指针域，指针指向下一个节点。单链表有头节点和尾节点，头节点不存储具体数据，用于表示单链表的起点，尾节点的指针指向null（空）。

如何实现单链表？

首先，我们要定义单链表的节点：

class Node<T> {
    T value;   // 数据域
    Node<T> next;  // 指针域，指向下一个节点

    Node(T value) {
        this.value = value;
    }
}

然后，我们可以定义单链表类：

class LinkedList<T> {
    Node<T> head;   // 定义头节点

    LinkedList() {
        head = new Node<>(null);
    }

    // 在链表末尾添加一个节点
    void add(T value) {
        Node<T> node = new Node<>(value);
        Node<T> curNode = head;
        while (curNode.next != null) {
            curNode = curNode.next;
        }
        curNode.next = node;
    }

    // 删除第index个节点
    void remove(int index) {
        if (index < 1) {
            System.out.println("超过范围");
            return;
        }
        Node<T> curNode = head;
        int i = 1;
        while (curNode.next != null && i < index) {
            curNode = curNode.next;
            i++;
        }
        if (i == index && curNode.next != null) {
            curNode.next = curNode.next.next;
        } else {
            System.out.println("超过范围");
        }
    }

    // 输出链表中的所有节点的值
    void print() {
        Node<T> curNode = head.next;
        while (curNode != null) {
            System.out.print(curNode.value + " ");
            curNode = curNode.next;
        }
        System.out.println();
    }
}

其中，add方法可以在链表末尾添加一个节点，remove方法可以删除第index个节点，print方法可以输出链表上所有节点的值。

如何使用单链表？

下面来看两个使用单链表的示例：

示例1：用单链表实现一个简单的队列

// 定义队列类
class Queue<T> {
    LinkedList<T> linkedList;

    Queue() {
        linkedList = new LinkedList<>();
    }

    // 插入一个元素
    void push(T value) {
        linkedList.add(value);
    }

    // 弹出一个元素
    T pop() {
        Node<T> head = linkedList.head;
        if (head.next == null) {
            System.out.println("队列为空");
            return null;
        }
        Node<T> first = head.next;
        head.next = first.next;
        return first.value;
    }
}

// 测试代码
public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.out.println(queue.pop());  // 输出 1
        System.out.println(queue.pop());  // 输出 2
        queue.push(4);
        System.out.println(queue.pop());  // 输出 3
        System.out.println(queue.pop());  // 输出 4
        System.out.println(queue.pop());  // 输出 队列为空，并返回null
    }
}

在这个示例中，我们定义了一个Queue类，用单链表实现了队列的基本功能。

示例2：用单链表实现一个简单的斐波那契数列

// 用单链表实现斐波那契数列
class Fibonacci {
    LinkedList<Integer> linkedList;

    Fibonacci() {
        linkedList = new LinkedList<>();
        linkedList.add(0);
        linkedList.add(1);
    }

    // 获取第n个斐波那契数
    int get(int n) {
        if (n < 1) {
            System.out.println("不存在第" + n + "个斐波那契数");
            return -1;
        }
        while (linkedList.head.next == null || linkedList.head.next.value < n) {
            int len = linkedList.head.next == null ? 1 : linkedList.head.next.value;
            int last = linkedList.head.next == null ? 0 : linkedList.head.next.next.value;
            linkedList.add(len + last);
        }
        if (linkedList.head.next.value > n) {
            System.out.println("不存在第" + n + "个斐波那契数");
            return -1;
        } else {
            return linkedList.head.next.next.value;
        }
    }
}

// 测试代码
public class Main {
    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        System.out.println(fibonacci.get(0));  // 输出 -1
        System.out.println(fibonacci.get(1));  // 输出 0
        System.out.println(fibonacci.get(2));  // 输出 1
        System.out.println(fibonacci.get(9));  // 输出 21
        System.out.println(fibonacci.get(10));  // 输出 34
        System.out.println(fibonacci.get(11));  // 输出 55
    }
}

在这个示例中，我们定义了一个Fibonacci类，用单链表实现了斐波那契数列中获取第n个斐波那契数的功能。

以上就是关于Java单链表的实现代码的完整攻略，包括单链表的定义、实现和使用的两个示例，希望能够对你有所帮助。