JAVA实现链表面试题

下面是“JAVA实现链表面试题”的完整攻略：

什么是链表？

链表是一种常见的数据结构，由若干个节点（Node）组成的一个序列。每个节点包含两个信息：数据（Data）和指向下一个节点的地址（Next）。

怎样用JAVA实现链表？

1. 定义节点类

public class Node {
    public int data; // 节点中存放的数据
    public Node next; // 指向下一个节点的地址
    // 构造函数
    public Node(int data) {
        this.data = data;
    }
}

2. 实现链表类

public class LinkedList {
    private Node head; // 链表的头节点
    // 添加节点操作
    public void addNode(int data) {
        // 创建新的节点
        Node newNode = new Node(data);

        // 如果链表为空，则添加的节点为头节点
        if (head == null) {
            head = newNode;
            return;
        }

        // 遍历链表，找到最后一个节点
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }

        // 将新节点添加到链表的最后
        lastNode.next = newNode;
    }

    // 遍历链表并打印所有节点
    public void printAllNodes() {
        Node currentNode = head;
        while (currentNode != null) {
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.next;
        }
    }
}

3. 测试链表

public class Main {
    public static void main(String[] args) {
        LinkedList myLinkedList = new LinkedList();
        myLinkedList.addNode(1);
        myLinkedList.addNode(2);
        myLinkedList.addNode(3);
        myLinkedList.addNode(4);
        myLinkedList.printAllNodes(); // 输出：1 2 3 4
    }
}

示例说明

示例一

我们需要实现一个链表来存储一些整数，然后遍历链表将所有整数打印出来。

LinkedList myLinkedList = new LinkedList();
myLinkedList.addNode(1);
myLinkedList.addNode(2);
myLinkedList.addNode(3);
myLinkedList.addNode(4);
myLinkedList.printAllNodes(); // 输出：1 2 3 4

对于这个需求，我们需要先创建一个LinkedList对象，然后调用addNode(int data)方法向链表中添加数据，最后调用printAllNodes()方法遍历链表并打印所有整数。

示例二

现在我们需要实现一个双向链表来存储一些字符串，然后遍历链表将所有字符串倒序打印出来。

public class DoubleLinkedList {
    private Node head; // 链表的头节点
    private Node tail; // 链表的尾节点
    // 添加节点操作
    public void addNode(String data) {
        // 创建新的节点
        Node newNode = new Node(data);

        // 如果链表为空，则添加的节点为头节点和尾节点
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }

        // 将新节点添加到链表的最后
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    // 遍历链表并打印所有节点（倒序）
    public void printAllNodes() {
        Node currentNode = tail;
        while (currentNode != null) {
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.prev;
        }
    }
}

对于这个需求，我们需要实现一个双向链表类及其相关操作。节点类需要增加一个指向前一个节点的地址。添加节点操作需要同时更新尾节点的指向，并将新节点的前驱指向当前尾节点。遍历链表并打印所有节点需要从尾节点开始往前遍历。