6. 线性表的链式表示和实现方式

# 1. 线性表的基本概念和链式表示介绍

线性表是数据结构中的一种基本结构，它具有一组有序的元素以及元素之间的一对一的关系。线性表的数据结构有顺序存储和链式存储两种表示方式，而在本章中，我们将着重介绍线性表的链式表示方式。

## 1.1 线性表的定义和特点
线性表是由n(n≥0)个数据元素组成的有限序列。其特点包括元素之间存在的顺序关系，表中只有唯一的首元素和末元素，以及除第一个和最后一个元素之外，每个元素都有一个前驱和一个后继。

## 1.2 链式表示的概念及优缺点
链式表示是指通过一组任意的存储单元来存储线性表的元素，并通过存储单元之间的指针关系来表示元素之间的逻辑关系。链式表示相对于顺序表示的优点在于插入和删除操作的高效性，缺点在于需要额外的空间存储指针，并且访问元素的效率相对较低。

通过对线性表的基本概念和链式表示的介绍，我们为后续的内容打下了基础，接下来将进一步深入探讨链式表示的数据结构和基本操作。

# 2. 链式表示的数据结构

链式表示是一种常用的线性表实现方式，可以通过节点之间的连接关系来存储和操作数据。常见的链式表示结构有单链表、双链表和循环链表。

### 2.1 单链表的结构和特点

单链表是一种链式表示的数据结构，它由多个节点组成，每个节点包含两部分信息：数据区域和指针域。数据区域用于存储具体的数据，指针域用于指向下一个节点。

单链表的特点包括：
- 由于每个节点只包含一个指向下一个节点的指针，所以插入和删除操作的时间复杂度为O(1)，适合频繁的插入和删除操作。
- 由于节点之间的连接是单向的，所以查找节点需要遍历整个链表，时间复杂度为O(n)，不适合频繁的查找操作。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# 示例代码
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list()

**代码说明：**
上述代码实现了一个简单的单链表，其中`Node`类表示链表中的节点，具有`data`数据和`next`指向下一个节点的指针。`LinkedList`类表示链表，具有`head`头节点。`append`方法用于在链表末尾添加节点，`print_list`方法用于打印链表中的所有节点。

**结果说明：**
运行上述代码，输出结果为：

1
2
3

表示成功创建了一个包含3个节点的单链表，并按顺序打印链表中的数据。

### 2.2 双链表的结构和特点

双链表是一种链式表示的数据结构，它与单链表类似，每个节点包含两个指针域，分别指向前一个节点和后一个节点。

双链表的特点包括：
- 由于每个节点同时包含指向前一个节点和后一个节点的指针，所以插入和删除操作的时间复杂度为O(1)，适合频繁的插入和删除操作。
- 与单链表相比，双链表可以从前向后和从后向前遍历，查找节点的时间复杂度为O(n/2)，适合频繁的查找操作。

public class Node {
    public int data;
    public Node prev;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void append(int data) {
        Node new_node = new Node(data);
        if (this.head == null) {
            this.head = new_node;
            this.tail = new_node;
        } else {
            new_node.prev = this.tail;
            this.tail.next = new_node;
            this.tail = new_node;
        }
    }

    public void printList() {
        Node current = this.head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }
}

// 示例代码
DoublyLinkedList linkedList = new DoublyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.printList();

**代码说明：**
上述代码实现了一个简单的双链表，其中`Node`类表示链表中的节点，具有`data`数据、`prev`指向前一个节点的指针和`next`指向下一个节点的指针。`DoublyLinkedList`类表示双链表，具有`head`头节点和`tail`尾节点。`append`方法用于在链表末尾添加节点，`printList`方法用于打印链表中的所有节点。

**结果说明：**
运行上述代码，输出结果为：

1
2
3

表示成功创建了一个包含3个节点的双链表，并按顺序打印链表中的数据。

### 2.3 循环链表的结构和特点

循环链表是一种链式表示的数据结构，其尾节点指向头节点，形成一个环形结构。

循环链表的特点包括：
- 由于尾节点指向头节点，所以插入和删除操作的时间复杂度为O(1)，适合频繁的插入和删除操作。
- 与单链表相比，循环链表可以无限次遍历，适合用于需要循环访问的场景。

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class CircularLinkedList {
    constructor() {
        this.head = null;
    }

    append(data) {
        const new_node = new Node(data);
        if (!this.head) {
            this.head = new_node;
            new_node.next = this.head;
        } else {
            let current = this.head;
            while (current.next !== this.head) {
                current = current.next;
            }
            current.next = new_node;
            new_node.next = this.head;
        }
    }

    printList() {
        if (!this.head) {
            console.log("List is empty");
            return;
        }
        let current = this.head;
        do {
            console.log(current.data);
            current = current.next;
        } while (current !== this.head);
    }
}

// 示例代码
const linked_list = new CircularLinkedList();
linked_list.append(1);
linked_list.append(2);
linked_list.append(3);
linked_list.printList();

**代码说明：**
上述代码实现了一个简单的循环链表，其中`Node