logo图片
数据结构与算法

循环链表

循环链表是链表的一种变体,其中第一个元素指向最后一个元素,最后一个元素指向第一个元素。单链表和双链表都可以做成循环链表。

循环单链表

在单链表中,最后一个节点的next指针指向第一个节点。
单链表作为循环链表

双向链表循环

在双向链表中,最后一个节点的next指针指向第一个节点,第一个节点的previous指针指向最后一个节点,双向循环。
双向链表作为循环链表
根据上图,以下是需要考虑的重点。
无论是单链表还是双链表,最后一个链接的 next 都指向链表的第一个链接。 如果是双向链表,第一个链接的previous指向列表的最后一个。

基本操作

以下是循环列表支持的重要操作。
insert-在列表的开头插入一个元素。 delete-从列表的开头删除一个元素。 display-显示列表。

插入操作

以下代码演示了基于单链表的循环链表中的插入操作。

示例

insertFirst(data):
Begin
   create a new node
   node-> data := data
   if the list is empty, then
      head := node
      next of node = head
   else
      temp := head
      while next of temp is not head, do
      temp := next of temp
      done
      next of node := head
      next of temp := node
      head := node
   end if
End

删除操作

以下代码演示了基于单链表的循环链表中的删除操作。
deleteFirst():
Begin
   if head is null, then
      it is Underflow and return
   else if next of head = head, then
      head := null
      deallocate head
   else
      ptr := head
      while next of ptr is not head, do
         ptr := next of ptr
      next of ptr = next of head
      deallocate head
      head := next of ptr
   end if
End

显示列表操作

以下代码演示了循环链表中的显示列表操作。
display():
Begin
   if head is null, then
      Nothing to print and return
   else
      ptr := head
      while next of ptr is not head, do
         display data of ptr
         ptr := next of ptr
      display data of ptr
   end if
End
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4