Java 中的链表实现

2025年8月17日 | 阅读 10 分钟

这是一种存储项目列表的方式，但这些项目在内存中并不相邻存储。相反，每个项目都链接到下一个项目，形成一个链。这种设置使得在列表的任何位置添加或删除项目变得非常容易，而无需移动其他所有内容，这对于数组等其他类型的列表来说可能是一个缓慢的过程。此列表中的每个项目都称为节点。

链表元素

节点 (Node): 链表构建块的概念。每个节点通常包含两部分

数据 (Data): 存储在节点中的实际值或信息。

指针 (Pointer): 指向序列中下一个节点的引用。

头 (Head) 或前端 (Front): 指向链表第一个节点的引用。当列表为空时，头为 null。

尾 (Tail) 或末端 (Rear): 指向链表最后一个节点的引用。

它是如何工作的？

链表的工作原理是将每个项目存储在其单独的容器中，称为节点。与数组不同，这些节点不并排放在内存中。相反，每个节点都包含数据和它的地址。

示例

在供应链系统中，添加或删除项目非常有效。如果我们向中间插入一个新项目，只需要更新几个指针。插入点之前的节点指向新节点，新节点指向插入点之后原来的节点。无需移动所有后续项目，这在数组等其他数据结构中通常是必需的。

链表实现

链表可以通过以下两种方式实现

手动使用类实现
使用内置 Java 类

使用类手动实现

这种方法可以帮助你理解单向链表的内部结构。

示例

public class Main {
	Node head; // head of list
	static class Node {
		int data;
		Node next;
		Node(int d) {
			data = d;
			next = null;
		}
	}
	// Insert a new node at the end
	public static Main insert(Main list, int data) {
		Node new_node = new Node(data);
		if (list.head == null) {
			list.head = new_node;
		} else {
			Node last = list.head;
			while (last.next != null) {
				last = last.next;
			}
			last.next = new_node;
		}
		return list;
	}
	// Print the LinkedList
	public static void printList(Main list) {
		Node currNode = list.head;
		System.out.print("LinkedList: ");
		while (currNode != null) {
			System.out.print(currNode.data + " ");
			currNode = currNode.next;
		}
	}
	public static void main(String[] args) {
		Main list = new Main();
		list = insert(list, 1);
		list = insert(list, 2);
		list = insert(list, 3);
		list = insert(list, 4);
		printList(list);
	}
}

编译并运行

输出

LinkedList: 1 2 3 4

使用内置类

Java 提供了内置的 LinkedList 类来实现链表。LinkedList 类属于 java.util 包。

阅读更多 Java 链表

示例

import java.util.LinkedList;
public class Main {
	public static void main(String[] args) {
		LinkedList<String> animals = new LinkedList<>();
		animals.add("Dog");
		animals.addFirst("Cat");
		animals.addLast("Horse");
		System.out.println("LinkedList: " + animals);
		System.out.println("First Element: " + animals.getFirst());
		System.out.println("Last Element: " + animals.getLast());
	}
}

编译并运行

输出

LinkedList: [Cat, Dog, Horse]
First Element: Cat
Last Element: Horse

链表的常见操作

以下是对链表执行的关键操作

插入

在头部/前端：在列表的开头添加新节点。
在尾部/末端：在列表的末尾添加新节点。
在特定位置：在任意索引处添加新节点。

删除

从头部删除：删除第一个节点。
从尾部删除：删除最后一个节点。
从特定位置删除：在任意索引处删除节点。
按值删除：删除具有特定数据值的第一个匹配节点。

遍历 (Traversal): 从头到尾访问列表中的每个节点以执行操作。

搜索 (Search): 查找具有特定数据值的节点。这通常涉及遍历列表直到找到该值或到达列表末尾。

获取 (Get/Access): 检索特定索引处节点的數據。

示例：链表插入操作

示例

class Main {
	// Node class
	static class Node {
		int data;
		Node next;
		Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	Node head = null;
	// Insert at beginning
	void insertAtBeginning(int data) {
		Node newNode = new Node(data);
		newNode.next = head;
		head = newNode;
	}
	// Insert at end
	void insertAtEnd(int data) {
		Node newNode = new Node(data);
		if (head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}
	// Insert at specific position (0-based index)
	void insertAtPosition(int data, int position) {
		if (position < 0) {
			System.out.println("Invalid position");
			return;
		}
		Node newNode = new Node(data);
		if (position == 0) {
			newNode.next = head;
			head = newNode;
			return;
		}
		Node temp = head;
		for (int i = 0; temp != null && i < position - 1; i++) {
			temp = temp.next;
		}
		if (temp == null) {
			System.out.println("Position out of bounds");
			return;
		}
		newNode.next = temp.next;
		temp.next = newNode;
	}
	// Display the list
	void display() {
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.data + " -> ");
			temp = temp.next;
		}
		System.out.println("null");
	}
	// Main method to test
	public static void main(String[] args) {
		Main list = new Main();
		list.insertAtEnd(10);
		list.insertAtBeginning(5);
		list.insertAtEnd(15);
		list.insertAtPosition(12, 2);
		System.out.println("Linked List after insertions:");
		list.display();
	}
}

编译并运行

输出

Linked List after insertions:
5 -> 10 -> 12 -> 15 -> null

示例：链表删除操作

示例

class Main {
	static class Node {
		int data;
		Node next;
		Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	Node head = null;
	// Insert at end (for setup)
	void insertAtEnd(int data) {
		Node newNode = new Node(data);
		if (head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}
	// Delete from beginning
	void deleteFromBeginning() {
		if (head == null) {
			System.out.println("List is empty");
			return;
		}
		head = head.next;
	}

	// Delete from end
	void deleteFromEnd() {
		if (head == null) {
			System.out.println("List is empty");
			return;
		}
		if (head.next == null) {
			head = null;
			return;
		}
		Node temp = head;
		while (temp.next.next != null) {
			temp = temp.next;
		}
		temp.next = null;
	}
	// Delete at specific position (0-based index)
	void deleteAtPosition(int position) {
		if (position < 0 || head == null) {
			System.out.println("Invalid position or empty list");
			return;
		}
		if (position == 0) {
			head = head.next;
			return;
		}
		Node temp = head;
		for (int i = 0; temp != null && i < position - 1; i++) {
			temp = temp.next;
		}
		if (temp == null || temp.next == null) {
			System.out.println("Position out of bounds");
			return;
		}
		temp.next = temp.next.next;
	}
	// Delete by value (first occurrence)
	void deleteByValue(int value) {
		if (head == null) {
			System.out.println("List is empty");
			return;
		}
		if (head.data == value) {
			head = head.next;
			return;
		}
		Node temp = head;
		while (temp.next != null && temp.next.data != value) {
			temp = temp.next;
		}
		if (temp.next == null) {
			System.out.println("Value not found");
			return;
		}
		temp.next = temp.next.next;
	}
	// Display the list
	void display() {
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.data + " -> ");
			temp = temp.next;
		}
		System.out.println("null");
	}
	// Main method to test
	public static void main(String[] args) {
		Main list = new Main();
		list.insertAtEnd(10);
		list.insertAtEnd(20);
		list.insertAtEnd(30);
		list.insertAtEnd(40);
		list.insertAtEnd(50);
		System.out.println("Original List:");
		list.display();
		list.deleteFromBeginning();
		list.deleteFromEnd();
		list.deleteAtPosition(1);
		list.deleteByValue(30);
		System.out.println("List after deletions:");
		list.display();
	}
}

编译并运行

输出

Original List:
10 -> 20 -> 30 -> 40 -> 50 -> null
Value not found
List after deletions:
20 -> 40 -> null

示例：遍历链表

示例

class Main {
	static class Node {
		int data;
		Node next;
		Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	Node head = null;
	// Insert at end (for setup)
	void insertAtEnd(int data) {
		Node newNode = new Node(data);
		if (head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}
	// Traverse and print elements
	void traverse() {
		if (head == null) {
			System.out.println("List is empty");
			return;
		}
		Node temp = head;
		System.out.print("Linked List: ");
		while (temp != null) {
			System.out.print(temp.data + " -> ");
			temp = temp.next;
		}
		System.out.println("null");
	}
	// Count nodes
	int countNodes() {
		int count = 0;
		Node temp = head;
		while (temp != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}
	// Sum of all node values
	int sumOfNodes() {
		int sum = 0;
		Node temp = head;
		while (temp != null) {
			sum += temp.data;
			temp = temp.next;
		}
		return sum;
	}
	// Main method to test
	public static void main(String[] args) {
		Main list = new Main();
		list.insertAtEnd(5);
		list.insertAtEnd(15);
		list.insertAtEnd(25);
		list.insertAtEnd(35);
		list.traverse();
		System.out.println("Total nodes: " + list.countNodes());
		System.out.println("Sum of node values: " + list.sumOfNodes());
	}
}

编译并运行

输出

Linked List: 5 -> 15 -> 25 -> 35 -> null
Total nodes: 4
Sum of node values: 80

示例：搜索链表

示例

class Main {
	static class Node {
		int data;
		Node next;
		Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	Node head = null;
	// Insert at end (for setup)
	void insertAtEnd(int data) {
		Node newNode = new Node(data);
		if (head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}
	// Iterative search
	boolean searchIterative(int key) {
		Node temp = head;
		while (temp != null) {
			if (temp.data == key) {
				return true;
			}
			temp = temp.next;
		}
		return false;
	}
	// Recursive search
	boolean searchRecursive(Node node, int key) {
		if (node == null)
			return false;
		if (node.data == key)
			return true;
		return searchRecursive(node.next, key);
	}

	// Display the list
	void display() {
		Node temp = head;
		System.out.print("Linked List: ");
		while (temp != null) {
			System.out.print(temp.data + " -> ");
			temp = temp.next;
		}
		System.out.println("null");
	}
	// Main method to test
	public static void main(String[] args) {
		Main list = new Main();
		list.insertAtEnd(10);
		list.insertAtEnd(20);
		list.insertAtEnd(30);
		list.insertAtEnd(40);
		list.display();
		int key = 30;
		System.out.println("Searching for " + key + " (Iterative): " + list.searchIterative(key));
		System.out.println("Searching for " + key + " (Recursive): " + list.searchRecursive(list.head, key));
		key = 99;
		System.out.println("Searching for " + key + " (Iterative): " + list.searchIterative(key));
		System.out.println("Searching for " + key + " (Recursive): " + list.searchRecursive(list.head, key));
	}
}

编译并运行

输出

Linked List: 10 -> 20 -> 30 -> 40 -> null
Searching for 30 (Iterative): true
Searching for 30 (Recursive): true
Searching for 99 (Iterative): false
Searching for 99 (Recursive): false

示例：检索特定索引处节点的数据

示例

class Main {
	static class Node {
		int data;
		Node next;
		Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	Node head = null;
	// Insert at end (for setup)
	void insertAtEnd(int data) {
		Node newNode = new Node(data);
		if (head == null) {
			head = newNode;
			return;
		}
		Node temp = head;
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}
	// Get data at specific index (iterative)
	Integer getDataAtIndex(int index) {
		if (index < 0)
			return null;
		Node temp = head;
		int count = 0;
		while (temp != null) {
			if (count == index)
				return temp.data;
			temp = temp.next;
			count++;
		}
		return null; // Index out of bounds
	}
	// Get data at index (recursive)
	Integer getDataAtIndexRecursive(Node node, int index) {
		if (node == null || index < 0)
			return null;
		if (index == 0)
			return node.data;
		return getDataAtIndexRecursive(node.next, index - 1);
	}
	// Display the list
	void display() {
		Node temp = head;
		System.out.print("Linked List: ");
		while (temp != null) {
			System.out.print(temp.data + " -> ");
			temp = temp.next;
		}
		System.out.println("null");
	}
	// Main method to test
	public static void main(String[] args) {
		Main list = new Main();
		list.insertAtEnd(100);
		list.insertAtEnd(200);
		list.insertAtEnd(300);
		list.insertAtEnd(400);
		list.display();
		int index = 2;
		System.out.println("Data at index " + index + " (Iterative): " + list.getDataAtIndex(index));
		System.out.println("Data at index " + index + " (Recursive): " + list.getDataAtIndexRecursive(list.head, index));
		index = 5;
		System.out.println("Data at index " + index + ": " + list.getDataAtIndex(index)); // Should return null
	}
}

编译并运行

输出

Linked List: 100 -> 200 -> 300 -> 400 -> null
Data at index 2 (Iterative): 300
Data at index 2 (Recursive): 300
Data at index 5: null

优点

动态大小：与固定大小的数组不同，它可以根据需要在运行时增长或收缩。
高效的插入和删除：添加或删除元素非常高效，因为它只涉及更改几个指针。如果已知位置，则在链表中添加或删除元素是高效的。如果需要搜索位置，可以使用特定方法。
无内存浪费：仅在创建新节点时分配内存，避免了预先分配未使用的空间。

缺点

更多的内存开销：每个节点除了数据外，还需要额外的内存来存储指针。
无随机访问：要访问特定索引处的元素，我们必须从头开始遍历列表（时间复杂度为 O(n)）。这与数组不同，数组可以通过其索引直接访问元素（O(1)）。

应用

音乐播放列表和图像浏览器：需要顺序访问项目的应用程序，如音乐播放器或图像浏览器，通常依赖于双向链表。它允许轻松地在曲目或图像之间导航（下一个和上一个）。
实现堆栈和队列：链表是构建其他抽象数据类型（如堆栈（后进先出）和队列（先进先出））的自然选择。例如，您可以使用单向链表通过在一端添加或删除节点来同时实现堆栈或队列。
应用程序中的撤销功能：操作存储在列表中，通过向后遍历，可以撤销操作。

结论

链表是计算机科学中一种基本且通用的数据结构。与数组不同，它们的非连续内存分配允许高效的插入和删除，使其成为需要动态大小和频繁修改的场景的理想选择。

即使存在指针带来的轻微内存开销和无随机访问的缺点，它们在处理顺序数据方面的灵活性以及在构建堆栈和队列等抽象数据类型方面的关键作用，使其在从系统编程到复杂算法的各种应用中都不可或缺。

理解链表是掌握更高级数据结构和优化动态数据处理代码的基石。

下一主题Java 中的哈希技术

Java 中的链表实现

链表元素

它是如何工作的？

示例

链表实现

使用类手动实现

示例

使用内置类

示例

链表的常见操作

示例：链表插入操作

示例

示例：链表删除操作

示例

示例：遍历链表

示例

示例：搜索链表

示例

示例：检索特定索引处节点的数据

示例

优点

缺点

应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的链表实现

链表元素

它是如何工作的？

示例

链表实现

使用类手动实现

示例

使用内置类

示例

链表的常见操作

示例：链表插入操作

示例

示例：链表删除操作

示例

示例：遍历链表

示例

示例：搜索链表

示例

示例：检索特定索引处节点的数据

示例

优点

缺点

应用

结论

相关帖子

Java 12

Java 中的 XOR 和 XNOR 运算符

Difference between Error and Exception in Java

How to Split a String in Java with Delimiter

Java 中多线程的缺点

Sum of Prime Numbers in Java

Java 中的方法绑定

Java 中的内置异常

Reverse Level Order Traversal in Spiral Form in Java

Java 中两层架构和三层架构的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器