数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也
是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊
的结构在不同的应用场景中往往会带来不一样的处理效率。
常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链
表、栈、队列等,非线性结构包括树、图等。数据结构种类繁多,本文将通过图解的方式对
常用的数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构的基本知识。
本文提纲:
1 数组
数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据,可通过数组名
和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的,同时在内存中也
是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型
的大小。
2 链表
链表相较于数组,除了数据域,还增加了指针域用于构建链式的存储数据。链表中每一个节
点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的
查找和访问,使得链表的自由度更高。
这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其
它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多
余空间的使用。
一般常见的是有头有尾的单链表,对指针域进行反向链接,还可以形成双向链表或者循环链
表。
链表和数组对比
链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是
面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。
3 跳表
从上面的对比中可以看出,链表虽然通过增加指针域提升了自由度,但是却导致数据的查询
效率恶化。特别是当链表长度很长的时候,对数据的查询还得从头依次查询,这样的效率会