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程序設計的能力。