Java链表怎么实现

# Java链表怎么实现

链表（Linked List）是计算机科学中最基础的数据结构之一，与数组不同，它通过节点间的引用实现动态内存分配。本文将详细介绍如何在Java中实现单链表、双向链表及环形链表，并提供完整的代码示例。

## 一、链表基础概念

### 1.1 链表的特点
- **动态数据结构**：无需预先知道数据规模
- **非连续存储**：节点通过指针/引用连接
- **基础操作时间复杂度**：
  - 插入/删除：O(1)（已知位置时）
  - 随机访问：O(n)

### 1.2 常见链表类型
| 类型        | 特点                          |
|-------------|-------------------------------|
| 单链表      | 只有next指针                  |
| 双向链表    | 包含next和prev指针            |
| 环形链表    | 尾节点指向头节点              |

## 二、单链表实现

### 2.1 节点类定义
```java
class ListNode {
    int val;
    ListNode next;
    
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

2.2 单链表基本操作

public class SinglyLinkedList {
    private ListNode head;
    
    // 头插法
    public void insertAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
    }
    
    // 删除节点
    public void delete(int val) {
        if (head == null) return;
        
        if (head.val == val) {
            head = head.next;
            return;
        }
        
        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
    
    // 遍历打印
    public void display() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }
}

三、双向链表实现

3.1 节点类增强

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    
    public DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

3.2 双向链表操作特点

public class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;
    
    // 尾部插入
    public void insertAtTail(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }
    
    // 双向删除更高效
    public void delete(int val) {
        DoublyListNode current = head;
        while (current != null) {
            if (current.val == val) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    head = current.next;
                }
                
                if (current.next != null) {
                    current.next.prev = current.prev;
                } else {
                    tail = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }
}

四、环形链表实现

4.1 环形单链表

public class CircularLinkedList {
    private ListNode last; // 指向尾节点
    
    // 插入头部
    public void insert(int val) {
        ListNode newNode = new ListNode(val);
        if (last == null) {
            last = newNode;
            last.next = last; // 自环
        } else {
            newNode.next = last.next;
            last.next = newNode;
        }
    }
    
    // 约瑟夫问题解决方案
    public void josephus(int k) {
        ListNode current = last;
        while (current.next != current) {
            // 移动k-1步
            for (int i = 0; i < k-1; i++) {
                current = current.next;
            }
            System.out.println("淘汰: " + current.next.val);
            current.next = current.next.next;
        }
        System.out.println("幸存者: " + current.val);
    }
}

五、链表常见面试题

5.1 反转链表（迭代法）

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

5.2 检测环（快慢指针）

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

六、链表vs数组

七、最佳实践建议

1. 边界条件处理：始终检查头节点/尾节点是否为null
2. 虚拟头节点：简化头节点的特殊处理

   
   ListNode dummy = new ListNode(0);
   dummy.next = head;
   

3. 内存管理：在C++等语言中需手动释放内存，Java依靠GC
4. 多指针技巧：快慢指针、前后指针解决复杂问题

通过本文的学习，您应该已经掌握了Java中实现各类链表的方法。建议读者动手实现每个示例代码，并通过LeetCode等平台的链表专题（如LRU缓存、合并K个有序链表等）进行实战练习。 “`

注：实际使用时可根据需要调整代码示例的详细程度或增加复杂度更高的操作说明。本文结构保持Markdown格式，包含代码块、表格等标准元素，总字数约1500字。