数据结构-链表
注:图片源自极客时间的数据结构与算法之美专栏
链表的定义
与数组需要连续空间不同,链表不需要内存中连续的内存空间,而是通过指针将一组零散的内存块串联起来使用.
单链表
链表通过指针将一组零散的内存块串联在一起,其中,我们把内存块称为链表的”结点”.
单链表中有两个结点是比较特殊的,第一个结点和最后一个结点.1
2头结点用来记录链表的基地址
尾结点的next指针域指向一个空地址NULL.
链表支持数据的查找、 插入和删除操作
循环链表
一种特殊的单链表,与单链表唯一的区别就是尾结点.
单链表的尾结点指向NULL空地址,而循环链表的 尾结点指向链表的头结点.
1
与单链表相比,循环链表的可以处理具有环形结构的数据(约瑟夫环的问题).
双(向)链表
单链表只有一个方向,结点只有一个后继指针next指向后面的结点.而双向结点有两个指针,前驱指针 previous 和后继指针 next .
双向循环链表
链表与数组的性能
数组
1
2插入删除 O(n)
随机访问 O(1)链表
1
2插入删除 O(1)
随机访问 O(n)