松散链表(Unrolled Linked List)

松散链表是链表的一个变体,和数组和链表一样,它也是线性数据结构。它和链表不同的是:传统链表中的每个节点存储一个元素,而松散链表的每个节点存储一个数组。松散链表组合了数组和链表的优点。松散链表的结构如下图:

松散链表(Unrolled Linked List)-C

特点:

  • 松散链表比传统链表节省内存,尤其在数据量大时
  • 更快的插入、删除和遍历操作
  • 这种数据结构可以更有效的利用系统Cache机制

插入数据:找一个节点,插入其数组。如果节点固定长度的数组已满,则在周围新建一个节点,将原来节点中一半的数据移到新节点。

删除数据:找到节点和数组的相应下标,将数据从数组中删除。如果节点中的数据太少,将当前节点与周围的节点合并。

更多详细内容,参考:https://en.wikipedia.org/wiki/Unrolled_linked_list

发表评论

电子邮件地址不会被公开。 必填项已用*标注