链表

概念

链表不需要连续的内存,通过指针将零散的内存块关联起来。

数组与链表的比较

最直观的比较是数组是连续的内存块,而链表不需要连续。

img

性能比较:

img

常见分类

常见的链表有单链表,双向链表,循环链表,双向循环链表等。

单链表

顾名思义,单链表是单方向的,链表由数据结点后继指针组成。

img

特点

循环链表

img

双向链表

img

双向循环链表

img

特性

编码

实现一个简单的单链表。

样例

此处使用scala实现常见的链表样例。

LRU

回文

-------------THEEND-------------