一、数据结构存储方式

数据结构的存储方式只有两种：
数组：顺序存储
链表：链式存储
这两种是[基础结构]，散列表、栈、队列、堆、树、图等等各种数据结构都是在数组或者链表上的特殊操作。

【队列】、【栈】这两种数据结构既可以用数组实现，也可以用链表实现，用数组实现就要处理扩容、缩容问题；用链表实现没有这个问题，但是需要跟多的内存空间存储节点指针。
，但是需要额外的空间存储指针。
【图】的两种表示方式，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并且可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话 比较耗空间。邻接表比较节省空间，但是很多操作上效率比不上邻接矩阵。

【散列表】就是通过散列函数把键映射到一个打数组里边。对于解决散列冲突的方法，拉链法需要链表特性，操作简单，线性探查法需要数组特性，以便连续寻址，不需要指针的存储，但是操作上复杂一些。

【树】用数组实现就是【堆】，因为堆是一个完全二叉树，用数组存储不需要节点指针，操作比较简单。用链表实现就是很常见的【树】，因为不一定是完全二叉树，所以不舍和数组存储。因此在这种链表树结构上，有衍生出各种巧妙的设计，比如二叉搜索树，AVL树，红黑树，区间树，B树等等。

综上，数据结构很多，甚至你可以发明自己的数据结构，但是底层就两种，【数组】和【链表】，二者优缺点如下：
【数组】由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间，但正因为连续存储，内存空间一次性分配够，所以说数组如果需要扩容，就要分配更大的存储空间，再把数据全部复制过去，时间复杂度O(n)；而且如果你想在数组中进行插入和删除，每次必须搬移后面的所有数据，以保持连续，时间复杂度O(n)
【链表】因为元素不连续，靠指针指向下一个位置，所以不存在数组的扩容问题，如果直到某一元素的前驱和后驱，操作指针就可以删除该元素和插入新元素，时间复杂度O(1)，但正因为存储空间不连续，你无法根据索引计算出元素对应的地址，所以不能随机访问，而且每个元素必须存储对应前后位置的指针，会消耗跟多的空间。

二、数据结构的基本操作

对于任何数据结构，其操作无非遍历+访问，具体一点：增删改查。

数据结构的种类很多，但是它们存在的目的是在不同的应用场景中，尽可能高效的增删改查
**
各种数据结构的遍历+访问，无非两种形式，线性的和非线性的。线性的就是for/while迭代为代表，非线性的就是递归为代表。具体一点，可以用一下框架总结。

数组遍历框架，典型的线性迭代结构：

  1. traverse(arr) {
  2.     for( const i = 0; i < arr.length; i++ ) {
  3.     // 迭代访问arr[i]
  4.   }
  5. }

链表遍历框架，兼具迭代和递归结构：

  1. // 基本的单链表节点
  2. class ListNode {
  3.     int val;
  4.   ListNode next;
  5. }
  7. // 迭代
  8. traverse(ListNode head) {
  9.     for ( ListNode p = head; p != null; p = p.next ) {
  10.       // 迭代访问p.val
  11.   }
  12. }
  14. // 递归
  15. traverse(ListNode head) {
  16.     // 递归访问head.val
  17.   traverse(head.next)
  18. }

二叉树遍历框架，典型的非线性递归遍历结构：

// 基本的二叉树节点
class ListNode {
    int val;
  ListNode left, right;
}

traverse(ListNode root) {
    traverse(root.left)    
  traverse(root.right)
}

二叉树遍历可以扩展为N叉树遍历框架：

class ListNode {
    int val;
  ListNode[] children;
}

traverse(ListNode root) {
  // 访问val
    for ( const child of root.children ) {
      traverse(child)
  }
}

N叉树的遍历又可以扩展为图的遍历，因为图就是好几个N叉树的结合体。

数据结构是工具，算法是通过合适的工具解决特定问题的方法