java如何实现链表（java实现链表结构）

## Java 实现链表### 简介链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的节点可以分散在内存中，通过指针链接在一起，因此可以灵活地插入和删除节点。### 一、单链表#### 1.1 节点定义```java class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;} } ```#### 1.2 链表类```java class SinglyLinkedList {private Node head;public SinglyLinkedList() {this.head = null;}// 插入节点到链表头部public void insertAtBeginning(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;}// 插入节点到链表末尾public void insertAtEnd(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}// 删除链表头部节点public void deleteAtBeginning() {if (head == null) {return;}head = head.next;}// 删除链表中指定值的节点public void deleteByValue(int data) {if (head == null) {return;}if (head.data == data) {head = head.next;return;}Node current = head;while (current.next != null) {if (current.next.data == data) {current.next = current.next.next;return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();} } ```### 二、双链表#### 2.1 节点定义```java class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;} } ```#### 2.2 链表类```java class DoublyLinkedList {private Node head;public DoublyLinkedList() {this.head = null;}// 插入节点到链表头部public void insertAtBeginning(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}newNode.next = head;head.prev = newNode;head = newNode;}// 插入节点到链表末尾public void insertAtEnd(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;newNode.prev = current;}// 删除链表头部节点public void deleteAtBeginning() {if (head == null) {return;}if (head.next == null) {head = null;return;}head = head.next;head.prev = null;}// 删除链表中指定值的节点public void deleteByValue(int data) {if (head == null) {return;}if (head.data == data) {head = head.next;if (head != null) {head.prev = null;}return;}Node current = head;while (current.next != null) {if (current.next.data == data) {current.next = current.next.next;if (current.next != null) {current.next.prev = current;}return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();} } ```### 三、使用示例```java public class Main {public static void main(String[] args) {// 单链表SinglyLinkedList singleList = new SinglyLinkedList();singleList.insertAtEnd(1);singleList.insertAtEnd(2);singleList.insertAtBeginning(3);singleList.printList(); // 输出 3 1 2singleList.deleteAtBeginning();singleList.printList(); // 输出 1 2singleList.deleteByValue(2);singleList.printList(); // 输出 1// 双链表DoublyLinkedList doubleList = new DoublyLinkedList();doubleList.insertAtEnd(1);doubleList.insertAtEnd(2);doubleList.insertAtBeginning(3);doubleList.printList(); // 输出 3 1 2doubleList.deleteAtBeginning();doubleList.printList(); // 输出 1 2doubleList.deleteByValue(1);doubleList.printList(); // 输出 2} } ```### 四、总结链表是一种灵活的数据结构，可以高效地进行插入和删除操作。单链表只能从头到尾遍历，而双链表则可以双向遍历，在某些场景下效率更高。选择哪种链表取决于具体的应用需求。

Java 实现链表

简介链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的节点可以分散在内存中，通过指针链接在一起，因此可以灵活地插入和删除节点。

一、单链表

1.1 节点定义```java class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;} } ```

1.2 链表类```java class SinglyLinkedList {private Node head;public SinglyLinkedList() {this.head = null;}// 插入节点到链表头部public void insertAtBeginning(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;}// 插入节点到链表末尾public void insertAtEnd(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}// 删除链表头部节点public void deleteAtBeginning() {if (head == null) {return;}head = head.next;}// 删除链表中指定值的节点public void deleteByValue(int data) {if (head == null) {return;}if (head.data == data) {head = head.next;return;}Node current = head;while (current.next != null) {if (current.next.data == data) {current.next = current.next.next;return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();} } ```

二、双链表

2.1 节点定义```java class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;} } ```

2.2 链表类```java class DoublyLinkedList {private Node head;public DoublyLinkedList() {this.head = null;}// 插入节点到链表头部public void insertAtBeginning(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}newNode.next = head;head.prev = newNode;head = newNode;}// 插入节点到链表末尾public void insertAtEnd(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;return;}Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;newNode.prev = current;}// 删除链表头部节点public void deleteAtBeginning() {if (head == null) {return;}if (head.next == null) {head = null;return;}head = head.next;head.prev = null;}// 删除链表中指定值的节点public void deleteByValue(int data) {if (head == null) {return;}if (head.data == data) {head = head.next;if (head != null) {head.prev = null;}return;}Node current = head;while (current.next != null) {if (current.next.data == data) {current.next = current.next.next;if (current.next != null) {current.next.prev = current;}return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();} } ```

三、使用示例```java public class Main {public static void main(String[] args) {// 单链表SinglyLinkedList singleList = new SinglyLinkedList();singleList.insertAtEnd(1);singleList.insertAtEnd(2);singleList.insertAtBeginning(3);singleList.printList(); // 输出 3 1 2singleList.deleteAtBeginning();singleList.printList(); // 输出 1 2singleList.deleteByValue(2);singleList.printList(); // 输出 1// 双链表DoublyLinkedList doubleList = new DoublyLinkedList();doubleList.insertAtEnd(1);doubleList.insertAtEnd(2);doubleList.insertAtBeginning(3);doubleList.printList(); // 输出 3 1 2doubleList.deleteAtBeginning();doubleList.printList(); // 输出 1 2doubleList.deleteByValue(1);doubleList.printList(); // 输出 2} } ```

四、总结链表是一种灵活的数据结构，可以高效地进行插入和删除操作。单链表只能从头到尾遍历，而双链表则可以双向遍历，在某些场景下效率更高。选择哪种链表取决于具体的应用需求。