链表也是一种数据结构,相比较于数组,略显复杂。链表和数组都是非常基础,非常常用的数据结构。
-
<李>数组与链表的区别
从底层的存储结构上看,二者申请的内存空间不一样:李
数组需要一块连续的内存空间来存储,对内存要求较高。
链表不需要一块连续的内存空间,它通过“指针,将一组零散的内存块串联起来。
例如,当我们申请一个100 mb大小的数组,当内存空间中没有连续的,足够大的存储空间时,即便内存的剩余总可用空间大于100 mb,仍然会申请失败。但如果我们申请的是100 mb大小的链表时,就可以申请成功。
链表结构有很多种,但最常见的主要有如下三种:李
单链表
双向链表
循环链表
2.1单链表
链表通过指针将一组零散的内存块串联在一起,我们将内存块称为链表的“结”点。为了将所有的结点串联在一起,每个链表的结点除了要存储数据之外,还需要记录链上的下一个结点的地址,这个结点地址的指针叫作“后继指针下一个”。
单链表中有两个结点比较特殊,分别是第一个结点和最后一个结点。我们习惯性的把第一个结点叫作头结点,最后一个结点叫作尾结点。
头结点用来记录链表中的基地址,可以根据头结点遍历得到整个链表。
尾结点的指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点。
在链表中进行数据的插入和删除操作要比数组中高效。因为在数组中进行插入,删除操作时,为了保持内存数据的连续性,需要做大量的数据移动,时间复杂度是O (n)。而在链表中存储空间本身就不是连续的,不需要为了保持内存的连续性而移动大量的数据。
在链表的插入和删除操作中,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是O (1)。
链表中数据的插入和删除比数组高效,但当需要随机访问第k个数据时,就没有数组高效。因为链表中的数据不是连续存储的,无法像数组那样,根据首地址和下标,通过寻址公式直接计算出对应的内存地址,而是需要根据指针一个结点一个结点依次遍历,直到找到对应的结点。
2.2循环链表
循环链表的本质是一种特殊的单链表,与单链表的区别就是在尾结点。单链表中的尾结点指针指向空地址,表示这就是最后的结点。而循环链表的尾结点指针指向链表的头结点。
与单链表相比,循环链表的优点是从链尾到链头比较方便。当需要处理的数据具有环形结构特点时,就适合用循环链表处理,比如著名的“约瑟夫问题”。
2.3双向链表
单链表中只有一个方向,结点只有一个后继指针下指向后面的结点。而双向链表中,有两个方向,每个结点不仅有一个后继指针指向后面的结点,还有一个前驱指针:指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以当存储同样多的数据时,双向链表要比单链表占用更多的内存空间。
虽然双向链表中有两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。
从双向链表从结构上看,可以支持O(1)时间复杂度的情况下找到前驱结点,因此在某些情况下,双向链表的插入,删除操作比单链表更简单、高效。其实,前面说的单链表的插入,删除操作的时间复杂度是O(1)是有先决条件的。
2.4单链表与双向链表删除,插入操作比较
删除操作
从链表中删除一个数据,一般都是如下两个情况:
删除结点中“值等于某个给定值”的结点
删除给定指针指向的结点
第一种情况中:
我们需要先找到值等于给定值的结点,找到结点后,再做删除操作。
这种情况下,单链表或双向链表都需要从头结点开始一个一个依次的遍历对比,直到找到值等于给定值的结点。此时单链表和双向链表查找的时间复杂度均是O (n),删除的时间复杂度是均O(1),根据时间复杂度分析中的加法法,则删除值等于给定值的结点的对应的链表操作总的时间复杂度是O (n)。且这种情况下单链表与双向链表是同等高效。
第二种情况中:
虽然我们可以根据指针直接找到要删除的结点,但删除某个结点问需要知道它的前驱结点,而单链表中并不支持直接获取前驱结点,此时为了找到前驱结点,我们还需要从头结点开始遍历单链表,直到p→下=问才说明p是q的前驱结点。
