当前位置：首页 > Java

java如何建立链表

2026-03-23 16:25:13Java

建立链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用。与数组不同，链表在内存中不必连续存储，插入和删除操作更高效。

单链表的实现

单链表的节点类通常包含数据域和指向下一个节点的指针。以下是一个简单的单链表实现：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {
    ListNode head;

    // 在链表末尾添加节点
    public void append(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印链表
    public void printList() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

双向链表的实现

双向链表的节点包含指向前一个和后一个节点的指针，支持双向遍历：

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

public class DoublyLinkedList {
    DoublyListNode head;

    // 在末尾添加节点
    public void append(int val) {
        DoublyListNode newNode = new DoublyListNode(val);
        if (head == null) {
            head = newNode;
            return;
        }
        DoublyListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }
}

链表的常用操作

链表的常见操作包括插入、删除、查找和反转：

java如何建立链表

// 在指定位置插入节点
public void insert(int index, int val) {
    ListNode newNode = new ListNode(val);
    if (index == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }
    ListNode current = head;
    for (int i = 0; i < index - 1 && current != null; i++) {
        current = current.next;
    }
    if (current == null) return;
    newNode.next = current.next;
    current.next = 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 && current.next.val != val) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

// 反转链表
public void reverse() {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}