队列/栈基本原理
本文介绍栈和队列的基本原理。二者均为操作受限的数据结构:队列仅能在队尾入队、队头出队,遵循“先进先出”(FIFO);栈则只允许在栈顶进行插入和删除,遵循“先进后出”(FILO)。底层多用数组或链表实现。
用链表实现队列/栈
本文介绍如何用链表实现栈和队列,利用双链表头尾操作均为O(1)的特性,高效实现栈(push/pop)和队列(入队/出队)。代码简洁,逻辑清晰,适用于理解底层数据结构与ADT的关系。
链表(链式存储)基本原理
本文深入讲解链表数据结构,对比力扣中的单链表与编程语言标准库中的双链表差异,涵盖泛型支持与双向指针特性。剖析链表内存分散存储、动态扩容的优势及索引访问的局限性,并通过代码详解单/双链表的增删查改操作,引入虚拟头结点优化边界处理,帮助读者掌握链表核心原理与实现技巧。
用数组实现队列/栈
使用数组实现栈时,可将动态数组尾部作为栈顶,利用ArrayList的add和remove方法实现O(1)时间复杂度的入栈、出栈操作。若以头部为栈顶,则需借助环形数组(如CycleArray)实现高效操作。同样,基于环形数组还可轻松实现队列,通过addLast入队、removeFirst出队,满足队列先进先出特性,所有操作均保持O(1)时间复杂度。
数组(顺序存储)基本原理
本章讲解数组的底层原理,区分静态数组与动态数组。静态数组是连续内存空间,支持O(1)随机访问,但增删效率低,需搬移数据;通过手动实现动态数组,理解其扩容、插入、删除等操作的实现逻辑与时间复杂度,为后续数据结构打下基础。
时间空间复杂度入门
本文介绍时间与空间复杂度入门知识,用Big O表示法(如O(1)、O(n)、O(n²))估算算法性能。复杂度关注最坏情况,越小越好。时间复杂度常由循环嵌套层数决定,空间复杂度看额外内存占用。结合多个代码示例,帮助初学者快速理解算法效率评估基础。
链表(链式存储)基本原理
链表是一种通过指针串联节点的线性结构,无需连续内存,支持高效增删。单链表仅有next指针,双链表增加prev指针以支持双向遍历。相比数组,链表插入删除灵活,无扩容负担,但不支持随机访问,查找需从头遍历。实际开发中常用双链表,配合虚拟头结点简化操作。
时间空间复杂度入门
本文介绍时间与空间复杂度入门知识,使用Big O表示法(如O(1)、O(n)、O(n²)),强调估算而非精确计算,保留最高次项。时间复杂度常由循环嵌套层数决定,空间复杂度看额外内存占用。分析以最坏情况为主,越小越好。结合多个代码示例,帮助初学者理解复杂度分析的基本方法与常见误区。
时间空间复杂度入门
初学者只需掌握:用Big O表示时空复杂度,保留最高次项;时间复杂度看循环嵌套层数,空间复杂度看额外内存占用;通常分析最坏情况,越小越好。n指输入规模,如数组长度。
动态数组代码实现
本文详解动态数组的底层实现,涵盖自动扩缩容、索引越界检查与内存泄漏防范三大关键点,结合Java代码演示增删查改操作及扩容机制,帮助理解数据结构设计原理。