Java数据结构之链表详解

什么是链表？

链表是一种基本的动态数据结构，它的基本思想是利用指针将一些零散的内存块串联起来，形成一个逻辑上的整体。链表由一些称为节点的元素组成，每个节点保存两个部分：数据和指向下一个节点的指针。相比于数组这种静态数据结构，链表具有动态性，我们可以通过动态的增加或删除节点来改变链表的大小。

链表的分类

1. 单向链表：每个节点只有一个指向下一个节点的指针。
2. 双向链表：每个节点既有一个指向下一个节点的指针，也有一个指向前一个节点的指针。这样做可以使得链表具备双向遍历的能力。
3. 循环链表：形式上是一个环形结构的链表，也就是最后一个节点指向第一个节点，或者说第一个节点的前驱节点是最后一个节点。
4. 双向循环链表：结合前面两种链表的特点，它既可以双向遍历，也可以形成一个闭合的环形结构。

链表的基本操作

插入操作

链表插入操作可以分为两类：头插法和尾插法，它们的区别在于插入节点的位置不同。

头插法

头插法是将新增节点插入到链表的头部，即成为新的头节点。具体步骤如下：

1. 创建一个新的节点，将数据存入其中。
2. 将这个节点的next指针指向原链表的头节点。
3. 更新链表的头节点指针指向这个新节点。

代码示例如下：

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

尾插法

与头插法不同，尾插法是将新增节点插入到链表的尾部，成为链表的最后一个节点。具体步骤如下：

1. 创建一个新的节点，将数据存入其中。
2. 遍历链表，找到最后一个节点。
3. 将最后一个节点的next指针指向新节点。

代码示例如下：

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

删除操作

链表删除操作主要有两种方式：删除头节点和删除指定节点。具体操作如下：

删除头节点

1. 更新链表的头节点指针指向下一个节点。
2. 释放原头节点的空间。

代码示例如下：

public void deleteAtBeginning() {
    if (head != null) {
        Node temp = head;
        head = head.next;
        temp.next = null;
        temp = null;
    }
}

删除指定节点

1. 遍历链表，找到要删除节点的前驱节点。
2. 更新前驱节点的next指针。

代码示例如下：

public void deleteByValue(int data) {
    if (head == null) {
        return;
    }
    if (head.data == data) {
        head = head.next;
        return;
    }
    Node temp = head;
    while (temp.next != null && temp.next.data != data) {
        temp = temp.next;
    }
    if (temp.next == null) {
        return;
    }
    temp.next = temp.next.next;
}

链表的应用示例

单向链表实现栈

栈是一种先进后出（FILO）的数据结构，我们可以使用单向链表来实现栈。具体操作如下：

1. 创建一个空的单向链表，它的头节点为null。
2. 将新元素插入到链表的头部。
3. 将链表的头节点作为栈顶，返回它的数据。

代码示例如下：

public class StackByLinkedList {

    private Node head = null;

    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

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

    public int peek() {
        if (head == null) {
            throw new RuntimeException("Stack is empty");
        }
        return head.data;
    }

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

    private static class Node {
        int data;
        Node next;

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

双向循环链表实现定时器

定时器是一种常见的应用场景，我们可以使用双向循环链表来实现定时器。具体操作如下：

1. 创建一个双向循环链表，它的头节点为null。
2. 将新元素插入到链表尾部，并且根据任务定时时间排序。
3. 使用线程循环遍历链表，若发现任务到达定时时间，将该任务从链表中删除，并执行任务。

代码示例如下：

public class TimerByLinkedList {

    private TimerTask head = null;

    public synchronized void addTimerTask(TimerTask task) {
        // 略去排序逻辑
        if (head == null) {
            head = task;
            head.prev = head.next = head; // 自己构成转换素环形的节点
        } else {
            TimerTask tail = head.prev;
            tail.next = task;
            task.prev = tail;
            task.next = head;
            head.prev = task;
        }
        notify();
    }

    public synchronized void start() {
        while (true) {
            while (head == null) {
                try {
                    wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            long delay = head.executeTime - System.currentTimeMillis();
            if (delay <= 0) {
                head.run();
                head = head.next;
                if (head == head.next) {
                    head = null;
                } else {
                    head.prev.next = head; //删除已经执行的任务
                    head.prev = head.prev.prev;
                }
            }
            else {
                try {
                    wait(delay);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private static abstract class TimerTask implements Runnable, Comparable<TimerTask> {

        long executeTime;
        TimerTask prev;
        TimerTask next;

        public TimerTask(long executeTime) {
            this.executeTime = executeTime;
        }

        @Override
        public int compareTo(TimerTask o) {
            return Long.compare(executeTime, o.executeTime);
        }
    }
}

总结

链表是一种经典的动态数据结构，其应用场景非常广泛。本文介绍了链表的基本操作，以及一些常见的链表应用示例。需要注意的是，在链表插入和删除操作中要注意避免出现空指针异常，以及链表插入时要注意区分头插法和尾插法。