Java链表的实现与应用

链表是一种常见的数据结构，可以有效地实现数据的插入和删除操作。在Java中，链表可用于实现各种数据结构，如队列、栈等。本文将从多个方面详细介绍Java链表的实现与应用，以帮助读者更好地理解和使用链表。

一、链表的定义和操作

链表是由一组节点组成的数据结构，每个节点包含一个数据元素和指向下一个节点的指针。链表可以是单向的，每个节点只有一个指向下一个节点的指针；也可以是双向的，每个节点既有指向下一个节点的指针，也有指向上一个节点的指针。

1. 链表的创建

public class ListNode{
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public ListNode createLinkedList(int[] nums) {
    ListNode head = new ListNode(nums[0]);
    ListNode cur = head;
    for (int i = 1; i < nums.length; i++) {
        cur.next = new ListNode(nums[i]);
        cur = cur.next;
    }
    return head;
}

2. 链表的遍历

public void traverseLinkedList(ListNode head) {
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

3. 链表的插入

public void insertNode(ListNode head, int index, int val) {
    ListNode newNode = new ListNode(val);
    ListNode cur = head;
    for (int i = 0; i < index - 1; i++) {
        cur = cur.next;
    }
    newNode.next = cur.next;
    cur.next = newNode;
}

4. 链表的删除

public void deleteNode(ListNode head, int index) {
    ListNode cur = head;
    for (int i = 0; i < index - 1; i++) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
}

二、链表的应用

1. 链表实现栈

栈是一种后进先出（LIFO）的数据结构，链表可以很方便地实现栈。具体实现如下：

public class LinkedListStack {
    private ListNode top;

    public LinkedListStack() {
        top = null;
    }

    public void push(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty!");
        }
        int val = top.val;
        top = top.next;
        return val;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

2. 链表实现队列

队列是一种先进先出（FIFO）的数据结构，链表同样可以很方便地实现队列。具体实现如下：

public class LinkedListQueue {
    private ListNode front, rear;

    public LinkedListQueue() {
        front = rear = null;
    }

    public void enqueue(int val) {
        ListNode newNode = new ListNode(val);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        int val = front.val;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return val;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

3. 链表实现LRU缓存

LRU（Least Recently Used）是一种常见的缓存淘汰策略，即缓存中最近最少使用的数据应当被淘汰。链表可以很方便地实现LRU缓存。

public class LRUCache {
    private Map<Integer, ListNode> map;
    private ListNode head;
    private ListNode tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        ListNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        ListNode node = map.get(key);
        if (node == null) {
            node = new ListNode(value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                removeTail();
            }
        } else {
            node.val = value;
            moveToHead(node);
        }
    }

    private void addToHead(ListNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(ListNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeTail() {
        ListNode node = tail.prev;
        removeNode(node);
        map.remove(node.val);
    }
}

三、总结

Java链表作为一种基础数据结构，非常灵活，可以实现各种高级数据结构。掌握链表的基本操作和应用场景，有助于提高Java程序设计的能力。