数据结构学习心得

---

学习数据结构和算法也有段时间了， 在此记录自己学习的过程，以及心得和体会

我不是计算机专业的，没有学过对应的课程，但我知道数据结构与算法是一个编程人员的核心能力。很

长时间以来，我都因为自己不会这个而怀疑自己到底会不会编程。当然，从过往的经历来看，好像开发一个

实际的APP或者Web应用也没有用到很多相关的知识，我就一直在逃避学习，直到一次头条的面试彻底让我

清醒了过来

一、迷雾重重，被现实吊打

相比于数据结构来说，其他计算机的核心课程显然我要更熟悉一些，而且我也不觉得精通数据结构的人

学习其他知识不吃力。但是从实际的面试中，遇到数据结构我就基本是卡住了，以至于有些时候似乎觉得

面试就无法聊下去了

终于逃离了自己的舒适圈，开启一条煎熬之路，但我也很明确自己的目的，提高自己的逻辑思维和在面

试中不会因为它被卡主，至于那些搞竞赛的同学我就只能投去羡慕的眼神了

一开始，我找到了几个计算机的同学，问了一些课程的用书和一些推荐的学习资源。于是就从严蔚敏奶

奶的那本紫皮书开始了，可以说看的一脸懵逼，找到了学习高数的那种感觉。而且书里面给出的都是一些伪

算法，没有具体的实现，感觉非常的苦恼。后来，又多方打听找到了高一凡大神写的数据结构算法实现，还

有点C/C++基础的我比着人家的思路开始把一些常用的数据结构实现了一遍，当然在这个过程中，自己也在

看B站上郝斌老师的视频课程，这一段时间总算把数组和链表给搞懂了，也认识了一些像队列、栈等一些更

级的数据结构

二、初现水面，站在数组和链表上眺望远方

其实这个时候，我还只是在学习数据结构，没有一点用它们解决实际问题的意识，似乎只是一些需要记住

的知识点。但是从自己不断遇到的问题来看，如果只用数组和链表去存取数据的话，问题的解决方案会很麻烦

，但是也是可以解决的，所以应该得出第一个结论：

数组和链表是数据结构中最底层的抽象

为什么呢？数组和链表对于数据存储的结构逻辑和实际的物理逻辑是相关联的，那么后来学习到的队列、

栈、哈希表、堆、树、图都跑哪去了呢？它们都可看做是数组或者链表的上层建筑，换用计算机语言来描述

就是对数组和链表进行封装。如果你需要的话，也可以自行封装，这就是我们常说的数据结构的设计。多样

化的数据结构本质上没什么差别，都是对数组和链表的不同操作而已

很多高级的数据结构都可以用数组或链表来实现，但是具体用哪一种，就要从性能上考虑了，所以这个

时候我又学习到了两个新的名词，时间复杂度和空间复杂度，从后来学习的情况来看，它们占据了数据结构

与算法的半壁江山。那就从数组和链表的特点来引入这复杂度的两个概念。

数组在物理空间上是紧凑连续存储的，可以随机访问，通过索引很快的找到对应元素，而且数组中数据

在物理空间中的密度是比较高的。但是正是因为是连续存储的，物理上的空间必须一次给够；如果不够的

话就要考虑扩容的问题，扩容时需要将原来的数据搬家到一个新的空间，从整体来说这样是比较复杂的。

此外，如果你想要在数组中进行插入或者删除，会惊动后面的许多元素，这样也是比较费劲的

再来看看链表，似乎链表和数组是优劣互补的，比如数组元素连续，链表元素不连续，靠指针来保持自

己前后同伴的关系；数组集中存储，链表则是分散存储，见缝插针，不会存在整体扩容的问题；当改动一个

元素时只会影响前后元素，不会像数组那样大动干戈。但是相比于数组的随机访问，链表则就显得吃力了许

多，它必须一个一个地找，同时由于多存储了地址，它占用的空间会更大

所以复杂度最直观的理解就是对于数据结构的操作是否麻烦

三、拨开乌云晴天日

应该用数组还是链表取决于数据结构具体的应用场景

下面举一些典型的使用数组或者链表实现的数据结构

比如队列和栈这两种数据结构既可以使用链表、也可以使用数组实现。用数组实现，就要处理不断扩容的

问题；用链表实现，就没有这个问题，但是需要避免更多的存储节点指针；图也有两种的表示方法，邻接表

就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，但是一般比较耗费空间，邻接表比较节省空间，

但是处理效率要比邻接矩阵慢很多

散列表就是通过散列函数将键映射到一个大数组中，而对于解决散列冲突的方法，拉链法使用链表，操作比

较简单，但需要空间。线性探查法需要使用数组，连续寻址，比较省空间，但是操作复杂

树用数组实现就是堆，因为堆是一个完全的二叉树，父子节点之间有对应的关系，方便使用数组进行存储。

其他种类的树因为没有完全二叉树那种特殊的关系，所以不便于使用数组进行存储，只能使用链表，在链表树的

基础上又设计出许多巧妙的树，如二叉搜索树、AVL树、红黑树、B树、B+树等等

四、高处要胜寒

算法是用于解决特地问题的一系列步骤总和，在计算机的应用中，特指对数据结构的一系列操作总和，

可是数据结构的操作无外乎就是遍历和访问，具体就是增删查改，而且在不同的应用场景下要既可能进行

高效的增删查改。数据结构的这些特点决定了在解决特定问题时我们是有规律可寻的，也可以说是有特定

框架在，比如下面对于一些数据结构的遍历框架：

数组的遍历框架

public void traverse(int[] arr){
    for(int i = 0;i < arr.length;i++){
        //访问每一个arr[i]
    }
}

链表的遍历框架

public void traverse(ListNode head){   //线性的
    while(head != null){
        //访问head.val
        head = head.next;
    }
}

public void traverse(ListNode head){   //非线性的 递归
    //访问head.val
    traverse(head.next);
}

二叉树的遍历框架

public void traverse(TreeNode root){
    traverse(root.left);
    traverse(root.right)
}

public void traverse(TreeNode root){
    //此时访问root.val,就是前序遍历
    traverse(root.left);  
    //此时访问root.val,就是中序遍历
    traverse(root.right);
    //此时访问root.val,就是后序遍历
}

二叉树的遍历框架又可以具体扩展为N叉树的遍历框架

//基本的N叉树节点
class TreeNode{
    int val;
    TreeNode[] children;
}
public void traverse(TreeNode root){
    for(TreeNode child:root.children){
        traverse(child)
    }
}

N叉树的遍历又可以扩展为图的遍历，图可以看做是几个N叉树的结合体

所以运用框架的思想去解决一些特定场景下的问题是非常高效的，之后会以一些具体的算法题目来说明如何

使用框架解题