链表的概念和分类

# 1. 简介

## 1.1 什么是链表

链表是一种常见的数据结构，用于存储具有相同数据类型的数据元素。它由节点（Node）组成，每个节点包含数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点，从而将节点按照一定的顺序连接起来。

## 1.2 链表的基本概念

链表由若干个节点组成，每个节点包含数据和指向下一个节点的指针。链表有头节点和尾节点，头节点用来标识链表的起始位置，尾节点的指针域指向空值（NULL）。

## 1.3 链表与数组的比较

与数组相比，链表在插入和删除操作时有更好的性能，因为它不需要像数组那样进行数据的迁移。但是在查找元素时，数组由于具有连续的存储空间，通常比链表更快。

接下来，我们将依次介绍单向链表、双向链表、循环链表、带头链表，以及线性链表和非线性链表的概念、操作以及应用场景。

# 2. 单向链表

单向链表是最基本的链表形式之一，它由一系列的节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。

### 2.1 单向链表的定义

在单向链表中，每个节点都有一个指针指向下一个节点，而最后一个节点的指针则为null，表示链表的末尾。链表的头节点通常用于指向链表的第一个节点。

class Node {
    int value;  // 节点的值
    Node next;  // 指向下一个节点的指针
    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    Node head;  // 链表的头节点
    // 添加节点到链表末尾
    public void append(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    // 打印链表所有节点的值
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }
}

### 2.2 单向链表的实现和操作

创建一个单向链表需要定义一个链表的头节点，然后可以通过添加节点的方式构建链表。可以使用`append`方法将新节点添加到链表末尾。

LinkedList linkedList = new LinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);
linkedList.printList();

输出结果为: `10 20 30`

### 2.3 单向链表的优缺点

单向链表的优点是插入和删除节点的时间复杂度为O(1)，相比数组，插入和删除操作更加高效。而缺点是访问链表中的任意节点需要遍历整个链表，时间复杂度为O(n)。

在某些情况下，单向链表也可以提供快速的查找效果。例如，如果链表是有序的，可以使用二分查找算法进行快速定位。

总之，单向链表在插入和删除操作频繁的场景下是一个不错的选择，但如果需要频繁访问节点，应该考虑其他数据结构。

# 3. 双向链表

#### 3.1 双向链表的定义

双向链表（Doubly Linked List）是一种链表数据结构，每个节点除了保存了下一个节点的指针（Next），还保存了上一个节点的指针（Prev）。这样的设计使得双向链表可以实现双向遍历，即可以从头到尾或者从尾到头访问链表中的元素。

下图是一个双向链表的示意图：

// 双向链表示意图
Prev        Data        Next
NULL   ←   Node 1   →   Node 2   →   Node 3   →   NULL

#### 3.2 双向链表的实现和操作

在实现双向链表时，我们需要定义一个节点类来表示链表中的每个节点，该节点类需要包含保存数据的属性和保存上一个节点和下一个节点的指针属性。

下面是一个Java版本的双向链表的实现示例：

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

// 定义双向链表类
class DoublyLinkedList {
    private Node head;
    public DoublyLinkedList() {
        this.head = nu