目录
- 概要
- 单链表
- 双向链表
- 头插入
- 尾插入
- 中间插入
- 删除
- 查找
- 小结
概要
链表
简单说明,链表有单链表,双向链表,循环链表(本篇文章以UE c++代码说明)。链表的操作,插入,删除,查找。插入,删除效率高,O(1),查找效率低,O(n)。看过python写的,这篇看下UE C++ 怎么实现的。重在学习思想。
单链表
单链表是最简单的链表的数据结构,操作有插入,删除,查找
单链表的结构,如下图
相对于数组来说,复杂点,占得内存大点,进行一些复杂的操作效率高点。
双向链表
双向链表是一个比单链表复杂的数据结构
双向链表比单链表复杂,有2个指针,一个指向前驱结点,一个指向后驱结点。这里先不多说,来看下它在UE里的数据结构,如下图:
头插入
看下它的头插入操作,如下图:
尾插入
再看看尾插入的操作,如下图:
中间插入
中间插入比较复杂,可以看下,如下图:
删除
直接看下删除操作的核心代码吧,如下图:
查找
耗时少的操作看过了,来看个耗时多的操作吧,如下图:
,看到while循环,就知道时间都浪费在哪了。
小结
还是ue比较熟悉点,很多优秀的代码可以很快的找到,拿出来,给大家分享。如果是python,就要自己去写一些了。这些挺浪费时间的。不过,还是要坚持下去,继续分享不一样的内容。