Java 与数据结构（2）：链表

绝地灬酷狼 2024-03-22 17:13 71阅读 0赞

## 一、链表 ##

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。链表中的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向 NULL。

相比于数组，链表的优点是可以动态地分配内存，不需要预先知道存储元素的个数，而且插入和删除操作的时间复杂度为 O(1)。

链表常见的类型有单向链表、双向链表和循环链表。单向链表每个节点只包含一个指向下一个节点的指针，而双向链表每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。循环链表的尾节点的指针指向头节点，形成一个环。

链表的缺点是访问元素的时间复杂度为 O(n)，因为需要从头节点开始遍历整个链表。另外，链表的存储空间比数组更大，因为每个节点需要额外的指针空间。

以下是一些链表的常见操作：

1.  遍历链表：从头节点开始，依次访问每个节点，直到尾节点。
2.  插入节点：将新节点插入到链表中的指定位置，需要修改相应节点的指针。
3.  删除节点：将指定节点从链表中删除，需要修改相应节点的指针。
4.  反转链表：将链表中的节点顺序翻转，需要修改相应节点的指针。
5.  合并链表：将两个有序链表合并成一个有序链表，需要比较节点的值来确定插入顺序。

## 二、Java 示例 ##

在 Java 中，可以使用自定义类来实现链表数据结构。一般情况下，链表由节点组成，每个节点包含元素值和指向下一个节点的指针。以下是一个简单的单向链表的 Java 代码示例：

public class ListNode {
        
        int val;
        ListNode next;
    
        public ListNode(int val) {
        
            this.val = val;
            this.next = null;
        }
    }
    
    public class LinkedList {
        
        private ListNode head;
    
        public LinkedList() {
        
            this.head = null;
        }
    
        public void addNode(int val) {
        
            ListNode newNode = new ListNode(val);
            if (head == null) {
        
                head = newNode;
            } else {
        
                ListNode curr = head;
                while (curr.next != null) {
        
                    curr = curr.next;
                }
                curr.next = newNode;
            }
        }
    
        public void deleteNode(int val) {
        
            if (head == null) {
        
                return;
            }
            if (head.val == val) {
        
                head = head.next;
                return;
            }
            ListNode curr = head;
            while (curr.next != null) {
        
                if (curr.next.val == val) {
        
                    curr.next = curr.next.next;
                    return;
                }
                curr = curr.next;
            }
        }
    
        public void printList() {
        
            ListNode curr = head;
            while (curr != null) {
        
                System.out.print(curr.val + " ");
                curr = curr.next;
            }
            System.out.println();
        }
    }
    
    public class Main {
        
        public static void main(String[] args) {
        
            LinkedList list = new LinkedList();
            list.addNode(1);
            list.addNode(2);
            list.addNode(3);
            list.printList(); // 输出：1 2 3
            list.deleteNode(2);
            list.printList(); // 输出：1 3
        }
    }

这个示例中，`ListNode` 表示链表中的节点，包含一个整数值和一个指向下一个节点的指针；`LinkedList` 表示单向链表，包含一个头节点和一些操作方法，如添加节点、删除节点和遍历链表；`Main` 类是程序的入口，创建了一个链表对象，添加了三个节点，然后删除了一个节点，最后输出链表中剩余节点的值。

## 三、使用场景 ##

在 Java 中，链表通常用于需要频繁插入和删除元素的场景，因为链表的插入和删除操作的时间复杂度为 O(1)，而数组的插入和删除操作的时间复杂度为 O(n)。以下是一些常见的使用场景：

1.  实现队列和栈：队列和栈都是基于链表实现的，因为它们需要频繁地插入和删除元素。
2.  实现 LRU 缓存：LRU 缓存是一种常用的缓存策略，它需要在缓存满时删除最近最少使用的元素，而链表可以很方便地实现 LRU 缓存。
3.  处理大数据集：当需要处理大量数据时，链表可以帮助我们节省内存空间，因为链表可以动态地分配内存，不需要预先知道存储元素的个数。
4.  排序算法：链表可以用于实现一些排序算法，如归并排序和快速排序等。

总之，当需要频繁插入和删除元素时，链表是一个非常有用的数据结构。