Java 链表 ListNode

一、什么是链表?

链表是一种常用的数据结构，它类似于数组，但不需要一段连续的内存空间来存储数据，而是在内存中随意分配存储空间。

链表由一系列结点组成，每个结点包含数据和一个指向下一个结点的指针。首节点没有前驱节点，尾节点没有后继节点。

Java中链表的实现是List接口的一个子类，即链表ListNode。

二、链表的操作

1、创建链表

ListNode l = new ListNode(val);

创建一个节点，值为val。

2、获取链表的值

l.val;

获取节点的值。

3、获取链表的下一个节点

l.next;

获取节点的下一个节点。

4、遍历链表

ListNode p = l;
while(p != null) {
    System.out.print(p.val + " ");
    p = p.next;
}

遍历链表并打印节点的值。

5、链表的增删

（1）在列表头插入节点

ListNode p = new ListNode(val);
p.next = head;
head = p;

新建一个节点并将它插入链表的头部。

（2）在列表尾部插入节点

ListNode p = head;
while(p.next != null) {
    p = p.next;
}
ListNode newNode = new ListNode(val);
p.next = newNode;

从头结点开始遍历链表，找到链表的尾结点，新建一个节点并将它插入链表的尾部。

（3）在列表中间插入节点

ListNode prev = head;
for(int i = 0; i < index - 1; i++) {
    prev = prev.next;
}
ListNode p = prev.next;
ListNode newNode = new ListNode(val);
prev.next = newNode;
newNode.next = p;

在链表的第index个位置之后插入一个新节点。

（4）从列表中删除节点

if(head == null) {
    return null;
}
else if(head.val == val) {
    return head.next;
}
else {
    ListNode p = head;
    while(p.next != null) {
        if(p.next.val == val) {
            p.next = p.next.next;
            break;
        }
        p = p.next;
    }
    return head;
}

删除一个节点，并返回链表头节点。

三、链表的应用场景

1、实现队列和栈

队列和栈往往都是由链表实现的。例如，队列可以由链表实现，队列的头结点就是链表的头节点，队列的尾结点就是链表的尾节点。栈也可以由链表实现，栈的顶部就是链表的头节点。

2、递归实现算法

递归算法常使用链表数据结构，因为递归调用可以通过链表来实现。

3、LRU缓存

LRU（Least Recently Used）即最近最少使用，是一种缓存置换算法。当缓存满了之后，需要删除最近最少使用的节点。用链表来实现LRU缓存算法，可以将最近使用的节点移到链表的头部，最近最少使用的节点位于链表的尾部。

4、链表排序

链表排序是编程考试中经常涉及到的问题。链表排序的思路是：将链表分成两个部分，排好序后再合并起来。

四、小结

Java 链表 ListNode 是一种常用的数据结构，由一系列结点组成，每个结点包含数据和指针。链表的操作包括创建、获取、遍历、插入和删除。链表可以应用于队列和栈、递归实现算法、LRU缓存和链表排序等多个场景。