第2章线性数据结构

线性数据结构是最基础的数据组织形式，其中的元素按照顺序排列，每个元素最多有一个前驱和一个后继。本章将详细介绍数组、链表、栈和队列这四种基本的线性数据结构。

2.1 数组

数组是最简单的线性数据结构，它在内存中开辟一块连续的空间来存储相同类型的元素。数组的特点是通过下标可以快速访问任意位置的元素，时间复杂度为。但插入和删除操作需要移动元素，时间复杂度为。

数组内存布局

# 第2章 数组的基本操作实现  
class Array:  
    def __init__(self, size):  
        self.size = size  
        self.data = [None] * size  
        self.length = 0  
      
    def __getitem__(self, index):  
        if0 <= index < self.length:  
            return self.data[index]  
        raise IndexError("数组索引越界")  
      
    def append(self, value):  
        if self.length >= self.size:  
            raise OverflowError("数组已满")  
        self.data[self.length] = value  
        self.length += 1

在Python中，列表(list)是一种动态数组，可以自动扩容。我们通过实现一个固定大小的数组来理解其原理。

2.2 链表

链表是另一种线性数据结构，它通过指针将不连续的内存块连接起来。每个节点包含数据和指向下一个节点的指针。链表的优势在于插入和删除操作不需要移动元素，只需要修改指针即可，时间复杂度为。但访问任意位置的元素需要从头开始遍历，时间复杂度为。

链表结构

# 第2章 单向链表的实现  
class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None  

class LinkedList:  
    def __init__(self):  
        self.head = None  
        self.length = 0  
      
    def append(self, data):  
        new_node = Node(data)  
        ifnot self.head:  
            self.head = new_node  
        else:  
            current = self.head  
            while current.next:  
                current = current.next  
            current.next = new_node  
        self.length += 1

2.3 栈

栈是一种后进先出(LIFO)的线性数据结构。想象一摞盘子，最后放上去的盘子最先被拿走。栈的主要操作包括压栈(push)和弹栈(pop)，都只在栈顶进行，时间复杂度都是。

栈操作示意

# 第2章 栈的实现与应用  
class Stack:  
    def __init__(self):  
        self.items = []  
      
    def push(self, item):  
        self.items.append(item)  
      
    def pop(self):  
        if self.is_empty():  
            raise IndexError("栈为空")  
        return self.items.pop()  
      
    def is_empty(self):  
        return len(self.items) == 0

2.4 队列

队列是一种先进先出(FIFO)的线性数据结构。就像排队买票，先来的人先买票。队列的主要操作包括入队(enqueue)和出队(dequeue)，分别在对尾和队头进行，时间复杂度都是。

队列操作示意

# 第2章 队列的实现  
class Queue:  
    def __init__(self):  
        self.items = []  
      
    def enqueue(self, item):  
        self.items.append(item)  
      
    def dequeue(self):  
        if self.is_empty():  
            raise IndexError("队列为空")  
        return self.items.pop(0)  
      
    def is_empty(self):  
        return len(self.items) == 0

2.5 双端队列

双端队列是一种两端都可以进行插入和删除操作的线性数据结构。它结合了栈和队列的特点，既可以作为栈使用，也可以作为队列使用。

双端队列操作

# 第2章 双端队列的实现  
class Deque:  
    def __init__(self):  
        self.items = []  
      
    def add_front(self, item):  
        self.items.insert(0, item)  
      
    def add_rear(self, item):  
        self.items.append(item)  
      
    def remove_front(self):  
        if self.is_empty():  
            raise IndexError("双端队列为空")  
        return self.items.pop(0)  
      
    def remove_rear(self):  
        if self.is_empty():  
            raise IndexError("双端队列为空")  
        return self.items.pop()  
      
    def is_empty(self):  
        return len(self.items) == 0

本章我们学习了四种基本的线性数据结构。数组支持随机访问，适合读多写少的场景。链表支持高效插入删除，适合动态变化的数据。栈和队列作为操作受限的线性结构，在特定场景下有重要应用。下一章我们将学习树形结构，包括二叉树、堆和树遍历算法。

预览时标签不可点

第2章 线性数据结构