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

# 1. 线性表的基本概念和链式表示介绍 线性表是数据结构中的一种基本结构，它具有一组有序的元素以及元素之间的一对一的关系。线性表的数据结构有顺序存储和链式存储两种表示方式，而在本章中，我们将着重介绍线性表的链式表示方式。 ## 1.1 线性表的定义和特点 线性表是由n(n≥0)个数据元素组成的有限序列。其特点包括元素之间存在的顺序关系，表中只有唯一的首元素和末元素，以及除第一个和最后一个元素之外，每个元素都有一个前驱和一个后继。 ## 1.2 链式表示的概念及优缺点 链式表示是指通过一组任意的存储单元来存储线性表的元素，并通过存储单元之间的指针关系来表示元素之间的逻辑关系。链式表示相对于顺序表示的优点在于插入和删除操作的高效性，缺点在于需要额外的空间存储指针，并且访问元素的效率相对较低。 通过对线性表的基本概念和链式表示的介绍，我们为后续的内容打下了基础，接下来将进一步深入探讨链式表示的数据结构和基本操作。 # 2. 链式表示的数据结构 链式表示是一种常用的线性表实现方式，可以通过节点之间的连接关系来存储和操作数据。常见的链式表示结构有单链表、双链表和循环链表。 ### 2.1 单链表的结构和特点 单链表是一种链式表示的数据结构，它由多个节点组成，每个节点包含两部分信息：数据区域和指针域。数据区域用于存储具体的数据，指针域用于指向下一个节点。 单链表的特点包括： - 由于每个节点只包含一个指向下一个节点的指针，所以插入和删除操作的时间复杂度为O(1)，适合频繁的插入和删除操作。 - 由于节点之间的连接是单向的，所以查找节点需要遍历整个链表，时间复杂度为O(n)，不适合频繁的查找操作。 ```python 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)，适合频繁的查找操作。 ```java 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)，适合频繁的插入和删除操作。 - 与单链表相比，循环链表可以无限次遍历，适合用于需要循环访问的场景。 ```javascript 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