先决条件： 双链表， 循环链表 循环双链表具有双链表和循环链表的特性，其中两个连续元素通过上一个和下一个指针链接或连接，最后一个节点通过下一个指针指向第一个节点，第一个节点通过上一个指针指向最后一个节点。
null
以下是C/C++中循环双链表节点的表示：
// Structure of the node struct node{ int data; struct node *next; // Pointer to next node struct node *prev; // Pointer to previous node};
循环双链表中的插入
循环双链表中的插入
- 在列表末尾或空列表中插入
- 空列表（start=NULL）： 插入一个节点（比如N）时，数据=5，所以N的前一个指针指向N，N的下一个指针也指向N。但现在开始指针指向列表中的第一个节点。
- 列表最初包含一些节点，从起点到列表的第一个节点： 插入一个节点（比如M）时，数据=7，所以M的上一个指针指向最后一个节点，M的下一个指针指向第一个节点，最后一个节点的下一个指针指向这M个节点，第一个节点的上一个指针指向这M个节点。
C++
// Function to insert at the end void insertEnd( struct Node** start, int value) { // If the list is empty, create a single node // circular and doubly list if (*start == NULL) { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return ; } // If list is not empty /* Find last node */ Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = new Node; new_node->data = value; // Start is going to be next of new_node new_node->next = *start; // Make new node previous of start (*start)->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node; } |
JAVA
// Function to insert at the end static void insertEnd( int value) { // If the list is empty, create a single // node circular and doubly list if (start == null ) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty // Find last node Node last = (start).prev; // Create Node dynamically Node new_node = new Node(); new_node.data = value; // Start is going to be // next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // This code is contributed by rutvik_56 |
Python3
# Function to insert at the end def insertEnd(value) : global start # If the list is empty, create a # single node circular and doubly list if (start = = None ) : new_node = Node( 0 ) new_node.data = value new_node. next = new_node.prev = new_node start = new_node return # If list is not empty # Find last node */ last = (start).prev # Create Node dynamically new_node = Node( 0 ) new_node.data = value # Start is going to be next of new_node new_node. next = start # Make new node previous of start (start).prev = new_node # Make last previous of new node new_node.prev = last # Make new node next of old last last. next = new_node # This code is contributed by shivanisinghss2110 |
C#
// Function to insert at the end static void insertEnd( int value) { Node new_node; // If the list is empty, create a single node // circular and doubly list if (start == null ) { new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty /* Find last node */ Node last = (start).prev; // Create Node dynamically new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // This code is contributed by Pratham76 |
Javascript
<script> // Function to insert at the end function insertEnd(value) { // If the list is empty, create a single // node circular and doubly list if (start == null ) { var new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty // Find last node var last = (start).prev; // Create Node dynamically var new_node = new Node(); new_node.data = value; // Start is going to be // next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // This code contributed by aashish1995 </script> |
- 在列表开头插入： 要在列表的开头插入一个节点，请创建一个数据为5的节点（例如T），T next pointer指向列表的第一个节点，T next pointer指向列表的最后一个节点，最后一个节点的next pointer指向这个T节点，第一个节点的next pointer也指向这个T节点，最后不要忘记将“Start”指针移到这个T节点。
C++
// Function to insert Node at the beginning // of the List, void insertBegin( struct Node** start, int value) { // Pointer points to last Node struct Node *last = (*start)->prev; struct Node* new_node = new Node; new_node->data = value; // Inserting the data // setting up previous and next of new node new_node->next = *start; new_node->prev = last; // Update next and previous pointers of start // and last. last->next = (*start)->prev = new_node; // Update start pointer *start = new_node; } |
JAVA
// Function to insert Node at the beginning // of the List, static void insertBegin( int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = (start).prev = new_node; // Update start pointer start = new_node; } // this code is contributed by shivanisinghss2110 |
Python3
# Function to insert Node at the beginning # of the List, def insertBegin( value) : global start # Pointer points to last Node last = (start).prev new_node = Node( 0 ) new_node.data = value # Inserting the data # setting up previous and # next of new node new_node. next = start new_node.prev = last # Update next and previous pointers # of start and last. last. next = (start).prev = new_node # Update start pointer start = new_node # This code is contributed by shivanisinghss2110 |
C#
// Function to insert Node at the beginning // of the List, static void insertBegin( int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = (start).prev = new_node; // Update start pointer start = new_node; } // This code is contributed by shivanisinghss2110 |
Javascript
// Function to insert Node at the beginning // of the List, function insertBegin(value) { // Pointer points to last Node var last = start.prev; var new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = start.prev = new_node; // Update start pointer start = new_node; } // This code is contributed by shivanisinghss2110 |
- 在列表的节点之间插入 ：要在列表之间插入节点，需要两个数据值，一个是插入新节点后的数据值，另一个是新节点的数据值。
C++
// Function to insert node with value as value1. // The new node is inserted after the node with // with value2 void insertAfter( struct Node** start, int value1, int value2) { struct Node* new_node = new Node; new_node->data = value1; // Inserting the data // Find node having value2 and next node of it struct Node *temp = *start; while (temp->data != value2) temp = temp->next; struct Node *next = temp->next; // insert new_node between temp and next. temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } |
JAVA
// Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter( int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; Node next = temp.next; // insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } // this code is contributed by shivanisinghss2110 |
Python3
# Function to insert node with value as value1. # The new node is inserted after the node with # with value2 def insertAfter(value1, value2) : global start new_node = Node( 0 ) new_node.data = value1 # Inserting the data # Find node having value2 and # next node of it temp = start while (temp.data ! = value2) : temp = temp. next next = temp. next # insert new_node between temp and next. temp. next = new_node new_node.prev = temp new_node. next = next next .prev = new_node # this code is contributed by shivanisinghss2110 |
C#
// Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter( int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; Node next = temp.next; // insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } // this code is contributed by shivanisinghss2110 |
Javascript
<script> // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 function insertAfter(value1, value2) { var new_node = new Node(); // Inserting the data new_node.data = value1; // Find node having value2 and // next node of it var temp = start; while (temp.data != value2) temp = temp.next; var next = temp.next; // Insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } // This code is contributed by shivanisinghss2110 </script> |
下面是一个完整的程序，它使用上述所有方法创建一个循环双链表。
C++
// C++ program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle #include <bits/stdc++.h> using namespace std; // Structure of a Node struct Node { int data; struct Node *next; struct Node *prev; }; // Function to insert at the end void insertEnd( struct Node** start, int value) { // If the list is empty, create a single node // circular and doubly list if (*start == NULL) { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return ; } // If list is not empty /* Find last node */ Node *last = (*start)->prev; // Create Node dynamically struct Node* new_node = new Node; new_node->data = value; // Start is going to be next of new_node new_node->next = *start; // Make new node previous of start (*start)->prev = new_node; // Make last previous of new node new_node->prev = last; // Make new node next of old last last->next = new_node; } // Function to insert Node at the beginning // of the List, void insertBegin( struct Node** start, int value) { // Pointer points to last Node struct Node *last = (*start)->prev; struct Node* new_node = new Node; new_node->data = value; // Inserting the data // setting up previous and next of new node new_node->next = *start; new_node->prev = last; // Update next and previous pointers of start // and last. last->next = (*start)->prev = new_node; // Update start pointer *start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 void insertAfter( struct Node** start, int value1, int value2) { struct Node* new_node = new Node; new_node->data = value1; // Inserting the data // Find node having value2 and next node of it struct Node *temp = *start; while (temp->data != value2) temp = temp->next; struct Node *next = temp->next; // insert new_node between temp and next. temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } void display( struct Node* start) { struct Node *temp = start; printf ( "Traversal in forward direction " ); while (temp->next != start) { printf ( "%d " , temp->data); temp = temp->next; } printf ( "%d " , temp->data); printf ( "Traversal in reverse direction " ); Node *last = start->prev; temp = last; while (temp->prev != last) { printf ( "%d " , temp->data); temp = temp->prev; } printf ( "%d " , temp->data); } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* start = NULL; // Insert 5. So linked list becomes 5->NULL insertEnd(&start, 5); // Insert 4 at the beginning. So linked // list becomes 4->5 insertBegin(&start, 4); // Insert 7 at the end. So linked list // becomes 4->5->7 insertEnd(&start, 7); // Insert 8 at the end. So linked list // becomes 4->5->7->8 insertEnd(&start, 8); // Insert 6, after 5. So linked list // becomes 4->5->6->7->8 insertAfter(&start, 6, 5); printf ( "Created circular doubly linked list is: " ); display(start); return 0; } |
JAVA
// Java program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle import java.util.*; class GFG { static Node start; // Structure of a Node static class Node { int data; Node next; Node prev; }; // Function to insert at the end static void insertEnd( int value) { // If the list is empty, create a single node // circular and doubly list if (start == null ) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty /* Find last node */ Node last = (start).prev; // Create Node dynamically Node new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // Function to insert Node at the beginning // of the List, static void insertBegin( int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = (start).prev = new_node; // Update start pointer start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter( int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; Node next = temp.next; // insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } static void display() { Node temp = start; System.out.printf( "Traversal in forward direction " ); while (temp.next != start) { System.out.printf( "%d " , temp.data); temp = temp.next; } System.out.printf( "%d " , temp.data); System.out.printf( "Traversal in reverse direction " ); Node last = start.prev; temp = last; while (temp.prev != last) { System.out.printf( "%d " , temp.data); temp = temp.prev; } System.out.printf( "%d " , temp.data); } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node start = null ; // Insert 5. So linked list becomes 5.null insertEnd( 5 ); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin( 4 ); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd( 7 ); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd( 8 ); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter( 6 , 5 ); System.out.printf( "Created circular doubly linked list is: " ); display(); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to illustrate inserting # a Node in a Circular Doubly Linked list # in begging, end and middle start = None # Structure of a Node class Node: def __init__( self , data): self .data = data self . next = None self .prev = None # Function to insert at the end def insertEnd(value) : global start # If the list is empty, create a # single node circular and doubly list if (start = = None ) : new_node = Node( 0 ) new_node.data = value new_node. next = new_node.prev = new_node start = new_node return # If list is not empty # Find last node */ last = (start).prev # Create Node dynamically new_node = Node( 0 ) new_node.data = value # Start is going to be next of new_node new_node. next = start # Make new node previous of start (start).prev = new_node # Make last previous of new node new_node.prev = last # Make new node next of old last last. next = new_node # Function to insert Node at the beginning # of the List, def insertBegin( value) : global start # Pointer points to last Node last = (start).prev new_node = Node( 0 ) new_node.data = value # Inserting the data # setting up previous and # next of new node new_node. next = start new_node.prev = last # Update next and previous pointers # of start and last. last. next = (start).prev = new_node # Update start pointer start = new_node # Function to insert node with value as value1. # The new node is inserted after the node with # with value2 def insertAfter(value1, value2) : global start new_node = Node( 0 ) new_node.data = value1 # Inserting the data # Find node having value2 and # next node of it temp = start while (temp.data ! = value2) : temp = temp. next next = temp. next # insert new_node between temp and next. temp. next = new_node new_node.prev = temp new_node. next = next next .prev = new_node def display() : global start temp = start print ( "Traversal in forward direction:" ) while (temp. next ! = start) : print (temp.data, end = " " ) temp = temp. next print (temp.data) print ( "Traversal in reverse direction:" ) last = start.prev temp = last while (temp.prev ! = last) : print (temp.data, end = " " ) temp = temp.prev print (temp.data) # Driver Code if __name__ = = '__main__' : global start # Start with the empty list start = None # Insert 5. So linked list becomes 5.None insertEnd( 5 ) # Insert 4 at the beginning. So linked # list becomes 4.5 insertBegin( 4 ) # Insert 7 at the end. So linked list # becomes 4.5.7 insertEnd( 7 ) # Insert 8 at the end. So linked list # becomes 4.5.7.8 insertEnd( 8 ) # Insert 6, after 5. So linked list # becomes 4.5.6.7.8 insertAfter( 6 , 5 ) print ( "Created circular doubly linked list is: " ) display() # This code is contributed by Arnab kundu |
C#
// C# program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle using System; using System.Collections.Generic; class GFG { static Node start; // Structure of a Node public class Node { public int data; public Node next; public Node prev; }; // Function to insert at the end static void insertEnd( int value) { Node new_node; // If the list is empty, create a single node // circular and doubly list if (start == null ) { new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty /* Find last node */ Node last = (start).prev; // Create Node dynamically new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start (start).prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // Function to insert Node at the beginning // of the List, static void insertBegin( int value) { // Pointer points to last Node Node last = (start).prev; Node new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = (start).prev = new_node; // Update start pointer start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 static void insertAfter( int value1, int value2) { Node new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it Node temp = start; while (temp.data != value2) temp = temp.next; Node next = temp.next; // insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } static void display() { Node temp = start; Console.Write( "Traversal in forward direction " ); while (temp.next != start) { Console.Write( "{0} " , temp.data); temp = temp.next; } Console.Write( "{0} " , temp.data); Console.Write( "Traversal in reverse direction " ); Node last = start.prev; temp = last; while (temp.prev != last) { Console.Write( "{0} " , temp.data); temp = temp.prev; } Console.Write( "{0} " , temp.data); } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node start = null ; // Insert 5. So linked list becomes 5.null insertEnd(5); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin(4); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd(7); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd(8); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter(6, 5); Console.Write( "Created circular doubly linked list is: " ); display(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to illustrate inserting a Node in // a Circular Doubly Linked list in begging, end // and middle var start = null ; // Structure of a Node class Node { constructor() { this .data = 0; this .next = null ; this .prev = null ; } } // Function to insert at the end function insertEnd(value) { var new_node; // If the list is empty, create a single node // circular and doubly list if (start == null ) { new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return ; } // If list is not empty /* Find last node */ var last = start.prev; // Create Node dynamically new_node = new Node(); new_node.data = value; // Start is going to be next of new_node new_node.next = start; // Make new node previous of start start.prev = new_node; // Make last previous of new node new_node.prev = last; // Make new node next of old last last.next = new_node; } // Function to insert Node at the beginning // of the List, function insertBegin(value) { // Pointer points to last Node var last = start.prev; var new_node = new Node(); new_node.data = value; // Inserting the data // setting up previous and next of new node new_node.next = start; new_node.prev = last; // Update next and previous pointers of start // and last. last.next = start.prev = new_node; // Update start pointer start = new_node; } // Function to insert node with value as value1. // The new node is inserted after the node with // with value2 function insertAfter(value1, value2) { var new_node = new Node(); new_node.data = value1; // Inserting the data // Find node having value2 and next node of it var temp = start; while (temp.data != value2) temp = temp.next; var next = temp.next; // insert new_node between temp and next. temp.next = new_node; new_node.prev = temp; new_node.next = next; next.prev = new_node; } function display() { var temp = start; document.write( "<br>Traversal in forward direction <br>" ); while (temp.next != start) { document.write(temp.data + " " ); temp = temp.next; } document.write(temp.data); document.write( "<br>Traversal in reverse direction <br>" ); var last = start.prev; temp = last; while (temp.prev != last) { document.write(temp.data + " " ); temp = temp.prev; } document.write(temp.data); } /* Driver code*/ /* Start with the empty list */ var start = null ; // Insert 5. So linked list becomes 5.null insertEnd(5); // Insert 4 at the beginning. So linked // list becomes 4.5 insertBegin(4); // Insert 7 at the end. So linked list // becomes 4.5.7 insertEnd(7); // Insert 8 at the end. So linked list // becomes 4.5.7.8 insertEnd(8); // Insert 6, after 5. So linked list // becomes 4.5.6.7.8 insertAfter(6, 5); document.write( "Created circular doubly linked list is: " ); display(); </script> |
输出：
Created circular doubly linked list is: Traversal in forward direction 4 5 6 7 8 Traversal in reverse direction 8 7 6 5 4
以下是循环双链接列表的优点和缺点：
优势：
- 列表可以从两个方向进行遍历，即从头部到尾部或从尾部到头部。
- 从头到尾或从尾到头的跳跃是在恒定时间O（1）内完成的。
- 循环双链表用于实现高级数据结构，如 斐波那契堆 .
缺点
- 每个节点都需要略微额外的内存来容纳上一个指针。
- 在列表上实现或执行操作时会涉及很多指针。因此，应该小心处理指针，否则列表中的数据可能会丢失。
循环双链表的应用
- 在媒体播放器应用程序中管理歌曲播放列表。
- 管理在线购物中的购物车。
本文由 阿卡什·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
