Java链表实现

一、链表介绍

链表是计算机科学中常见的数据结构之一，用于存储有序的数据集合，常用于实现栈、队列等数据结构。链表和数组一样，可用于存储一个线性结构的元素，但是链表允许插入和删除任意位置的元素，而无需移动其他元素的位置。链表由若干个结点组成，每个结点包含数据元素和指向下一个结点的指针。

二、链表的分类

链表可以根据结点间的关系来分类，可以分为单向链表、双向链表和循环链表。

三、Java实现链表

Java中可以通过定义一个链表的结点类来实现链表。

1. 链表结点类的定义

public class Node {
    int data;
    Node next;
    public Node(int dataValue) {
        data = dataValue;
        next = null;
    }
    public void setData(int dataValue) {
        data = dataValue;
    }
    public int getData() {
        return data;
    }
    public void setNext(Node nextValue) {
        next = nextValue;
    }
    public Node getNext() {
        return next;
    }
}

2. 单向链表的实现

单向链表是指只允许从前往后遍历，每个结点只包含一个指向下一个结点的指针。单向链表的尾结点的指针指向null。

public class LinkedList {
    private Node head;
    public void insertFirst(int dataValue) {
        Node newNode = new Node(dataValue);
        newNode.next = head;
        head = newNode;
    }
    public void deleteFirst() {
        if (head == null)
            return;
        head = head.next;
    }
    public void displayList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        LinkedList theList = new LinkedList();
        theList.insertFirst(1);
        theList.insertFirst(2);
        theList.insertFirst(3);
        theList.deleteFirst();
        theList.displayList();
    }
}

3. 双向链表的实现

双向链表是指每个结点中除了指向下一个结点的指针外，还包含一个指向前一个结点的指针。这种结构允许从前往后以及从后往前遍历，对于某些应用场景如LRU缓存，可以大幅提高效率。

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    public void insertFirst(int dataValue) {
        Node newNode = new Node(dataValue);
        if (head == null)
            tail = newNode;
        else
            head.prev = newNode;
        newNode.next = head;
        head = newNode;
    }
    public void insertLast(int dataValue) {
        Node newNode = new Node(dataValue);
        if (tail == null)
            head = newNode;
        else
            tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }
    public void deleteFirst() {
        if (head == null)
            return;
        head = head.next;
        if (head == null)
            tail = null;
        else
            head.prev = null;
    }
    public void deleteLast() {
        if (tail == null)
            return;
        tail = tail.prev;
        if (tail == null)
            head = null;
        else
            tail.next = null;
    }
    public void displayForward() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    public void displayBackward() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        DoublyLinkedList theList = new DoublyLinkedList();
        theList.insertFirst(1);
        theList.insertFirst(2);
        theList.insertLast(3);
        theList.deleteFirst();
        theList.displayForward();
        theList.displayBackward();
    }
}

4. 循环链表的实现

循环链表是一种特殊的链表，最后一个结点的指针指向第一个结点，形成一个环状结构。循环链表的遍历可以从任何一个结点开始。

public class CircularLinkedList {
    private Node current;
    public void insert(int dataValue) {
        Node newNode = new Node(dataValue);
        if (current == null) {
            current = newNode;
            current.next = current;
        } else {
            newNode.next = current.next;
            current.next = newNode;
            current = newNode;
        }
    }
    public void delete() {
        if (current == null)
            return;
        current.next = current.next.next;
    }
    public void display() {
        if (current == null)
            return;
        Node start = current.next;
        System.out.print(start.data + " ");
        while (start != current) {
            start = start.next;
            System.out.print(start.data + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        CircularLinkedList theList = new CircularLinkedList();
        theList.insert(1);
        theList.insert(2);
        theList.insert(3);
        theList.delete();
        theList.display();
    }
}

四、总结

链表是一种常用的数据结构，能够快速地插入和删除元素，但是其中的每一个结点需要使用一个额外的指针来指向下一个结点，增加了额外的内存开销。Java语言中可以通过定义一个链表结点类来实现链表的相关操作，具有良好的可读性和可扩展性。