顺序表以及链表的应用及区别（包含OJ讲解）

前面我已经发过怎么实现链表以及顺序表，今天大概的总结一下。

顺序表：

1.能够随时的存取，比较方便。

2.插入删除时，需要挪动数据，比较麻烦，因为是连续存储。

3.存储密度相对于链表来说是比较高的（存储单个字符的时候）。

4.如果首次开辟的空间不够用，后续还要继续扩容空间。比较麻烦。

链表：

1.存储密度相比于顺序表比较低（存储单个字符时）。

2.插入删除数据时，不需要挪动数据，这个方便。

3.插入数据时，如果是尾插，则要遍历整个链表，比较麻烦。也就是不支持随机访问。

4.不存在空间不够的情况，只要插入数据就申请空间，不存在浪费空间。

综上所述：

如果题目要求的是频繁的插入数据或是删除数据，我们应该要选择链表，而如果题目要的是频繁的查找数据，我们则要的是顺序表。根据他们的优缺点来进行取舍。

应用：

它们应用的地方在数据结构中很广泛，比如后面的串，队列，栈等等都会运用到。所以，个人认为这个是学数据结构的基础。

栈：其实栈以用链表表示，也可以用顺序表表示，但是我们知道栈的使用规则是先使用高地址，后使用低地址，而且还是先进后出的（也是后进先出，表示方法：LIFO或FILO）。也就是说，可栈顶的元素是先出的，所以这样就行了我们所说的压栈，所以，再用链表表示时，我们只能用头插法和头删法，这样的是不用遍历链表的，时间复杂度是O(1).此种情况是不带头节点不循环的单链表。所以，我们选择顺序表来表示栈更好一点。直接用尾插，既不用遍历数组，也不用挪动数据，使用起来更加方便。

队列：队列是先进先出的，也就是FIFO。他其实也可以用这两种方法分别表示，如果用链表来表示的话，适合用尾插法，头删法，这样就可以保证FIFO。插入和删除的时间复杂度都是O(1)。复合队列的规则。如果用顺序表的话，不考虑循环队列，删除数据时，要把挪动数据，相对于链表来说是比较麻烦的（也可以不用挪动数据，但是这样就必须要挪动队列的头）。所以个人认为不是循环队列的话，还是用链表比较好。

串：

串的话个人认为两个表示方法没有什么区别，因为保存的是字符，所以用链表表示的话存储密度低，如果用顺序表的话，七朵多种用顺序表表示的方法，具体还是得看自己选哪一个，具体的哪几种方法就不想细说了，感兴趣的可以私聊我，共同探讨一下。

所以，综上所述：在链表和顺序表中如何选择，就看那个比较好，方便满足条件。

上面总结了顺序表和链表的应用，下面说说栈的应用：不用说其实大家首先想到应该就是递归了，因为递归很容易导致栈溢出，所以，首当其冲的就是递归了。其次就是上次我说的那个前/后缀表达式计算，下来就是中缀表达式如何转后/前缀表达式，都是可以运用栈思想的。还有就是括号的匹配，让我们看看下面的题：

就是匹配，核心思想就是创建栈，遇见左括号就压入栈中，直到遇见右括号就停止，然后是取出栈中的元素，跟这个右括号匹配，匹配成功就继续，不成功就输出false。下面是实现的代码：

 

总体实现的代码在上，有更好的方法希望大家评论区指出，这道题我用顺序表实现的栈，如果用链表也可以，不过此时就要写一个申请节点空间的函数，每次压栈的时候，都要调用次函数来申请节点，所以我就用了静态的顺序表来实现，直接一次性开劈大点 （浪费了很多空间）。

最后的总结：

链表的核心思想就是插入删除查找等，方法都是一样的。顺序表就更不用说了，大部分题型都可以用数组的方法来做。

最后，如果本篇文章对你有帮助的话就点一下赞，支持一下吧！！！！！