【Java数据结构】链表(Linked List)-单向链表

一、什么是链表(Linked List)

链表(Linked List)是一种常见的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的引用。链表可以用于实现栈、队列等数据结构。相比数组，链表的优点在于可以高效地进行插入和删除操作，因为不需要移动大量元素。

1、链表的概念

链表由一系列节点（Node）组成，每个节点包含了一个数据元素和一个指向下一个节点的指针。链表的头节点（Head）指向第一个节点，尾节点（Tail）指向最后一个节点，最后一个节点指针指向null。

链表可以分为单向链表、双向链表和循环链表等不同类型。单向链表中每个节点只有一个指针指向下一个节点，而双向链表中每个节点有两个指针，分别指向上一个节点和下一个节点。循环链表的尾节点指针指向头节点，形成一个闭环。

2、链表的实现

链表的实现通常包括以下几个部分：

• 定义节点类：定义节点类包含数据元素和指向下一个节点的指针。
• 定义链表类：定义链表类包含头节点和节点数量等属性，以及插入、删除、查找等方法。
• 实现节点插入：新建节点并将其插入到链表中。
• 实现节点删除：找到要删除的节点并将其从链表中删除。
• 实现节点查找：遍历链表找到指定元素。

二、实现一个单向链表

Java中可以使用类来表示链表节点和链表，以下是一个基本的教程来实现一个单向链表。

1、定义链表节点类

链表节点类包含两个成员变量：节点值和指向下一个节点的引用。

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

2、实现链表类

链表类包含两个成员变量：链表头指针和链表长度。其中，链表头指针指向第一个节点。

class LinkedList {ListNode head;int size;public LinkedList() {this.head = null;this.size = 0;}public void add(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;}size++;}public int get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException();}ListNode curr = head;for (int i = 0; i < index; i++) {curr = curr.next;}return curr.val;}
}

3、测试链表类

public class Main {public static void main(String[] args) {LinkedList list = new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println(list.get(0)); System.out.println(list.get(1)); System.out.println(list.get(2)); }
}

以上是一个简单的链表实现，可以通过添加其他方法来进行更多操作。这个实现只包含了单向链表，如果需要实现双向链表或循环链表，需要在节点类中添加相应的成员变量，并在链表类中修改对应的方法。

链表的优点是可以快速添加、删除元素，但其缺点是访问任意位置元素的时间复杂度为O(n)，因此不适合用于需要频繁随机访问元素的场合。