第二章：线性数据结构

文档摘要

第二章：线性数据结构第二章：线性数据结构线性数据结构是最基本、最常用的数据结构类型。它们以线性的方式组织数据元素，每个元素最多只有一个前驱和一个后继。本章将深入探讨五种常见的线性数据结构：数组、链表、栈、队列和哈希表。 2.1 数组数组是一种将相同类型的元素存储在连续内存位置中的数据结构。数组的元素可以通过其索引直接访问，索引通常从 0 开始。 2.1.1 静态数组静态数组的大小在编译时确定，并且在程序运行时不能更改。优点：快速的随机访问：通过索引访问元素的时间复杂度为 O(1)。内存分配简单：由于大小固定，内存分配可以在编译时完成。缺点：大小固定：一旦创建，大小不能更改。插入和删除效率低：在数组中间插入或删除元素需要移动其他元素，时间复杂度为 O(n)。