数据结构学习笔记

1. 数组 (Array)

定义

数组是一种线性数据结构，用于存储固定大小的相同类型元素集合。每个元素都有一个索引，用于快速访问。

特点

优点：访问速度快，通过索引直接访问O(1)时间复杂度。
缺点：大小固定，插入和删除元素效率低（需移动后续元素）。插入元素的时间复杂度为O(n)，删除元素的时间复杂度同样为O(n)。

应用场景

适合于元素数量固定且频繁查询的场景，如排序数组、查找表等。多维数组常用于表示矩阵、图像、游戏地图等需要多个维度来描述的数据结构。

2. 链表 (Linked List)

定义

链表是一种由节点组成的数据结构，每个节点包含存储数据的部分以及指向下一个节点的指针。通过节点之间的指针连接，形成了链表的结构。链表可以分为单链表、双向链表和循环链表等不同类型，它们各自具有特定的特点和应用场景。

数据元素：节点存储的实际数据。数据可以是任意类型，例如整数、字符、字符串、对象等。
指针（或引用）：指向下一个节点的指针。它存储了下一个节点在内存中的地址，通过这个指针可以找到链表的下一个节点。

类型

单向链表

单链表是最简单的链表类型，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的尾节点指针为空，表示链表的结束。单链表的插入、删除操作相对简单高效，但随机访问的效率较低。

单向链表的特点

非连续存储：单链表中的节点在内存中可以是任意位置，不要求连续存储。每个节点通过指针指向下一个节点，从而将它们连在一起。
动态性：相较于数组，单链表的长度可以动态地增减，不需要预先分配内存空间。这使得单链表在需要频繁插入和删除节点的场景中更加灵活。
搜索效率相对较低：由于单链表的节点只能通过指针一个一个地遍历，因此搜索某个特定的节点需要遍历整个链表，时间复杂度为O(n)，其中n是链表的长度。相比之下，数组可以使用索引直接访问元素，搜索效率更高。
内存空间的额外开销：单链表中的每个节点除了存储数据外，还需要存储下一个节点的指针，这导致了额外的内存开销。
插入和删除效率较高：相对于数组，单链表在插入和删除节点时效率较高。插入一个节点只需要改变相邻节点的指针，而删除一个节点只需要改变前一个节点的指针指向下一个节点，不需要移动其他元素。
灵活性：单链表可以方便地进行节点的插入和删除操作，可以根据实际需要进行自由调整。

双向链表

每个节点包含数据、指向前一个节点和指向下一个节点的指针。

双向链表的特点

支持双向遍历：相对于单向链表，双向链表支持双向遍历，可以从前往后、从后往前遍历链表。
插入、删除节点效率更高：相较于单向链表，双向链表在插入和删除某个节点时，只需要改变相邻两个节点的指向，效率更高，尤其是在删除链表中某个元素时更加便捷。
需要更多的内存空间：相比单向链表，双向链表需要更多的内存空间来存储额外的指针，增加了额外的空间开销。
内存存储不连续：相对于数组，链表中节点的内存存储位置不连续，需要使用指针进行串联，这可以更加灵活地进行插入、删除和移动节点的操作。
操作复杂度较高：插入、删除、移动等操作，需要修改前后节点的指针信息，操作比较繁琐。

循环链表

链表的最后一个节点指向链表的第一个节点，形成闭环。

循环链表特点

首位相连：循环链表的最后一个节点指向链表的第一个节点，使得链表成为一个环形结构。这样，链表的结束节点与开始节点相连，可以实现无限循环，更加灵活和方便。
操作始终成立：由于循环链表始终是一个环形的结构，因此操作（例如插入、删除、查找等）始终处于链表中，这也保证了操作始终能够完成。
遍历循环：与单向链表相比，在遍历时需要注意指针不要陷入死循环。否则会导致遍历永远无法结束。
内存空间的额外开销：与单向链表相比，循环链表需要多一个指向头部节点的指针，增加了额外的空间开销。
插入和删除效率较高：相对于数组，循环链表在插入和删除节点时效率比较高。插入一个节点时只需要修改相邻节点的指针即可，而删除一个节点时只需要改变前一个节点的指针指向下一个节点即可。

优缺点

优点：动态分配内存，插入和删除操作快（O(1)，只需改变指针）。
缺点：访问速度慢，需从头节点遍历（最坏情况下O(n)）。

应用场景

适用于频繁插入和删除操作的场景，如实现堆栈、队列等。

3. 栈 (Stack)

定义

栈是一种特殊的线性结构，遵循后进先出（LIFO, Last In First Out）原则。只允许在一端（栈顶）进行插入和删除操作。

操作

压栈（Push）：在栈顶添加元素。
弹栈（Pop）：移除栈顶元素。
栈的插入和删除操作只能在栈顶进行，因此栈是一个只能从一端访问的数据结构。

应用场景

回溯算法、函数调用栈、括号匹配等。

4. 队列 (Queue)

定义

队列是一种线性结构，遵循先进先出（FIFO, First In First Out）原则。一端添加元素（队尾），另一端移除元素（队头）。

操作

入队（Enqueue）：在队尾添加元素。
出队（Dequeue）：从队头移除元素。

应用场景

任务调度、缓冲区管理等。

栈和队列的对比：

结构：栈和队列都是线性结构，但栈只有一个入口（栈顶）和一个出口（栈顶），而队列有一个入口（队尾）和一个出口（队头）。
插入和删除操作：栈的插入和删除操作只能在栈顶进行，而队列的插入操作在队尾进行，删除操作在队头进行。
访问顺序：栈按照后进先出的顺序访问元素，而队列按照先进先出的顺序访问元素。
应用场景：栈常用于函数调用、表达式求值、回溯算法等场景，而队列常用于任务调度、消息传递、缓冲区管理等场景。