第二章 磨刀霍霍，有备无患
2.1 数据结构
数据结构，是历年来笔试面试考试热点之一，至少会有2、3个数据结构的大题。
数据结构包括线性结构和非线性结构两种。线性结构中的线性表、栈、队列、串和非线性结构中二叉树是考试热点。本章备考知识点为考生总结归纳了需要熟练掌握的要点，并在最后一节提供了大量数据结构方面的面试题、解题方法思路供考生参考。
2.1.1 线性表
1．线性表的两种存储结构及其特点
2．线性链表基本操作：新增、删除
3．链表逆序等算法
线性表分两种存储结构：顺序存储和链式存储，分别如图2.1和图2.2所示。
图2.1 线性表的顺序存储结构
图2.2 线性表的链式存储结构
顺序存储结构的特点如下。
（1）前后两个元素的存储空间是紧邻的。
（2）空间利用率高，但实现要预估容量。
（3）查找操作时间复杂度为O(n)，读取操作为O(1)。
（4）新增节点，需要移动n-i+1个元素，删除节点需要移动n-i个元素。
链表存储结构的特点如下。
（1）可以连续，也可以不连续。
（2）需要格外控件存放后续节点的地址，动态申请空间。
（3）查找操作时间复杂度为O(n)，读取操作为O(n)。
（4）新增和删除操作简单，仅需变化两次指针。
链表的新增节点的过程：（1）新增节点指向下一节点。（2）上一节点指向新增节点。流程如图2.3所示。
图2.3 新增节点过程
链表删除节点的过程：上一节点指向下一节点。此流程较简单，就不画示意图。
顺序链表的逆序如图2.4所示。
图2.4 链表逆序的过程
链表反转过程如下。
（1）设置3个辅助指针，分别指向头3个节点。
（2）头两个指针指向的节点反转。
（3）3个辅助指针后移两个位置，循环过程2，直到链表结尾。
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
