Java链表（Linked List）基本原理与实现方法入门示例

下面是Java链表（Linked List）基本原理与实现方法入门示例的完整攻略。

什么是链表

链表是一种线性的数据结构，由一系列节点组成。每个节点都包含了数据和指向下一个节点的指针。

相比于数组，链表的一个主要优点是在插入、删除元素时不需要移动其他元素，因为每个节点都有指向下一个节点的指针。但是，链表的缺点是不能像数组一样随机访问，只能从头部开始遍历。

实现方法

Java实现单向链表

Java实现单向链表需要定义一个Node类，用于表示链表中的节点。定义一个链表类LinkedList，拥有添加节点方法（addNode）、删除节点方法（deleteNode）、遍历节点方法（traverseNodes）、清空链表方法等方法。

例如，以下为Java实现单向链表的示例代码：

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

public class LinkedList {
    Node head;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void deleteNode(int data) {
        Node current = head;
        Node previous = null;
        while (current != null && current.data != data) {
            previous = current;
            current = current.next;
        }
        if (current != null) {
            if (previous == null) {
                head = current.next;
            } else {
                previous.next = current.next;
            }
        }
    }

    public void traverseNodes() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public void clearList() {
        head = null;
    }
}

Java实现双向链表

Java实现双向链表需要在Node类中再添加前驱节点（previous）的指针，链表类中添加反向遍历节点方法（reverseTraverseNodes），其他方法和单向链表的实现类似。

例如，以下为Java实现双向链表的示例代码：

public class Node {
    int data;
    Node next;
    Node previous;

    public Node(int data) {
        this.data = data;
    }
}

public class DoublyLinkedList {
    Node head;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.previous = current;
        }
    }

    public void deleteNode(int data) {
        Node current = head;
        while (current != null && current.data != data) {
            current = current.next;
        }
        if (current != null) {
            if (current.previous == null) {
                head = current.next;
                if (head != null) {
                    head.previous = null;
                }
            } else {
                current.previous.next = current.next;
                if (current.next != null) {
                    current.next.previous = current.previous;
                }
            }
        }
    }

    public void traverseNodes() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public void reverseTraverseNodes() {
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        while (current != null) {
            System.out.println(current.data);
            current = current.previous;
        }
    }

    public void clearList() {
        head = null;
    }
}

示例说明

以下为使用单向链表实现LIFO（后进先出）栈的示例代码：

public class Stack {
    LinkedList list;

    public Stack() {
        list = new LinkedList();
    }

    public void push(int data) {
        list.addNode(data);
    }

    public int pop() {
        Node current = list.head;
        if (current == null) {
            throw new NoSuchElementException();
        } else if (current.next == null) {
            list.head = null;
            return current.data;
        } else {
            while (current.next.next != null) {
                current = current.next;
            }
            int data = current.next.data;
            current.next = null;
            return data;
        }
    }

    public void printStack() {
        list.traverseNodes();
    }
}

使用方式：

Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);  // 栈中元素为 3 -> 2 -> 1
stack.pop();    // 弹出元素3，栈中元素为 2 -> 1
stack.push(4);  // 栈中元素为 4 -> 2 -> 1
stack.printStack();  // 输出 4 2 1

以下为使用双向链表实现LIFO（后进先出）队列的示例代码：

public class Queue {
    DoublyLinkedList list;

    public Queue() {
        list = new DoublyLinkedList();
    }

    public void enqueue(int data) {
        list.addNode(data);
    }

    public int dequeue() {
        Node current = list.head;
        if (current == null) {
            throw new NoSuchElementException();
        } else if (current.next == null) {
            list.head = null;
            return current.data;
        } else {
            list.head = current.next;
            current.next.previous = null;
            return current.data;
        }
    }

    public void printQueue() {
        list.traverseNodes();
    }
}