本文概述

• C++
• Java
• Python3
• C#

先决条件:

• 插入元素循环双链表.
• 将数组转换为循环双链表。

鉴于开始指向循环双链表的开始的指针, 元件和一个位置。任务是插入元件在指定的位置在给定的循环双链表中。

文章图片
这个想法是计算列表中元素的总数。检查指定的位置是否有效, 即位置在计数之内。
如果位置有效：

1. 在内存中创建一个newNode。
2. 使用临时指针遍历列表(温度)直到节点刚好在需要插入新节点的给定位置之前。
3. 通过执行以下操作来插入新节点：
   • 分配newNode-> next = temp-> next
   • 将newNode-> prev分配为temp-> next
   • 将temp-> next分配为newNode
   • 假设(temp-> next)-> prev as newNode-> next

以下是上述想法的实现：
C++

//CPP program to convert insert an element at a specific //position in a circular doubly linked list#include < bits/stdc++.h> using namespace std; //Doubly linked list node struct node { int data; struct node* next; struct node* prev; }; //Utility function to create a node in memory struct node* getNode() { return (( struct node*) malloc ( sizeof ( struct node))); }//Function to display the list int displayList( struct node* temp) { struct node* t = temp; if (temp == NULL) return 0; else { cout < < "The list is: " ; while (temp-> next != t) { cout < < temp-> data < < " " ; temp = temp-> next; }cout < < temp-> data < < endl; return 1; } }//Function to count nunmber of //elements in the list int countList( struct node* start) { //Declare temp pointer to //traverse the list struct node* temp = start; //Variable to store the count int count = 0; //Iterate the list and increment the count while (temp-> next != start) { temp = temp-> next; count++; }//As the list is circular, increment the //counter at last count++; return count; }//Function to insert a node at a given position //in the circular doubly linked list bool insertAtLocation( struct node* start, int data, int loc) { //Declare two pointers struct node *temp, *newNode; int i, count; //Create a new node in memory newNode = getNode(); //Point temp to start temp = start; //count of total elements in the list count = countList(start); //If list is empty or the position is //not valid, return false if (temp == NULL || count < loc) return false ; else { //Assign the data newNode-> data = https://www.lsbin.com/data; //Iterate till the loc for (i = 1; i < loc - 1; i++) { temp = temp-> next; }//See in Image, circle 1 newNode-> next = temp-> next; //See in Image, Circle 2 (temp-> next)-> prev = newNode; //See in Image, Circle 3 temp-> next = newNode; //See in Image, Circle 4 newNode-> prev = temp; return true ; }return false ; }//Function to create circular doubly linked list //from array elements void createList( int arr[], int n, struct node** start) { //Declare newNode and temporary pointer struct node *newNode, *temp; int i; //Iterate the loop until array length for (i = 0; i < n; i++) { //Create new node newNode = getNode(); //Assign the array data newNode-> data = arr[i]; //If it is first element //Put that node prev and next as start //as it is circular if (i == 0) { *start = newNode; newNode-> prev = *start; newNode-> next = *start; }else { //Find the last node temp = (*start)-> prev; //Add the last node to make them //in circular fashion temp-> next = newNode; newNode-> next = *start; newNode-> prev = temp; temp = *start; temp-> prev = newNode; } } }//Driver Code int main() { //Array elements to create //circular doubly linked list int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) /sizeof (arr[0]); //Start Pointer struct node* start = NULL; //Create the List createList(arr, n, & start); //Display the list before insertion displayList(start); //Inserting 8 at 3rd position insertAtLocation(start, 8, 3); //Display the list after insertion displayList(start); return 0; }

Java

//Java program to convert insert //an element at a specific position //in a circular doubly linked listing, //end and middle class GFG {//Doubly linked list node static class node { int data; node next; node prev; }; //Utility function to create a node in memory static node getNode() { return new node(); } //Function to display the list static int displayList( node temp) { node t = temp; if (temp == null ) return 0 ; else { System.out.println( "The list is: " ); while (temp.next != t) { System.out.print( temp.data + " " ); temp = temp.next; } System.out.println( temp.data ); return 1 ; } } //Function to count nunmber of //elements in the list static int countList( node start) { //Declare temp pointer to //traverse the list node temp = start; //Variable to store the count int count = 0 ; //Iterate the list and //increment the count while (temp.next != start) { temp = temp.next; count++; } //As the list is circular, increment //the counter at last count++; return count; } //Function to insert a node at //a given position in the //circular doubly linked list static node insertAtLocation( node start, int data, int loc) { //Declare two pointers node temp, newNode; int i, count; //Create a new node in memory newNode = getNode(); //Point temp to start temp = start; //count of total elements in the list count = countList(start); //If list is empty or the position is //not valid, return false if (temp == null || count < loc) return start; else { //Assign the data newNode.data = https://www.lsbin.com/data; //Iterate till the loc for (i = 1 ; i < loc - 1 ; i++) { temp = temp.next; } //See in Image, circle 1 newNode.next = temp.next; //See in Image, Circle 2 (temp.next).prev = newNode; //See in Image, Circle 3 temp.next = newNode; //See in Image, Circle 4 newNode.prev = temp; return start; } } //Function to create circular doubly //linked list from array elements static node createList( int arr[], int n, node start) { //Declare newNode and temporary pointer node newNode, temp; int i; //Iterate the loop until array length for (i = 0 ; i < n; i++) { //Create new node newNode = getNode(); //Assign the array data newNode.data = arr[i]; //If it is first element //Put that node prev and next as start //as it is circular if (i == 0 ) { start = newNode; newNode.prev = start; newNode.next = start; } else { //Find the last node temp = (start).prev; //Add the last node to make them //in circular fashion temp.next = newNode; newNode.next = start; newNode.prev = temp; temp = start; temp.prev = newNode; } } return start; } //Driver Code public static void main(String args[]) { //Array elements to create //circular doubly linked list int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int n = arr.length; //Start Pointer node start = null ; //Create the List start = createList(arr, n, start); //Display the list before insertion displayList(start); //Inserting 8 at 3rd position start = insertAtLocation(start, 8 , 3 ); //Display the list after insertion displayList(start); } }//This code is contributed by Arnab Kundu

Python3

# Python3 program to insert an element # at a specific position in a # circular doubly linked list# Node of the doubly linked list class Node: def __init__( self , data): self .data = https://www.lsbin.com/data self .prev = None self . next = None# Utility function to create # a node in memory def getNode():return (Node( 0 ))# Function to display the list def displayList(temp):t = temp if (temp = = None ): return 0 else : print ("The list is: " , end = " " )while (temp. next ! = t): print ( temp.data, end = " " ) temp = temp. nextprint (temp.data )return 1# Function to count nunmber of # elements in the list def countList( start):# Declare temp pointer to # traverse the list temp = start# Variable to store the count count = 0# Iterate the list and increment the count while (temp. next ! = start) : temp = temp. next count = count + 1# As the list is circular, increment the # counter at last count = count + 1return count# Function to insert a node at a given position # in the circular doubly linked list def insertAtLocation(start, data, loc):# Declare two pointers temp = None newNode = None i = 0 count = 0# Create a new node in memory newNode = getNode()# Point temp to start temp = start# count of total elements in the list count = countList(start)# If list is empty or the position is # not valid, return False if (temp = = None or count < loc): return startelse :# Assign the data newNode.data = https://www.lsbin.com/data# Iterate till the loc i = 1 ; while (i < loc - 1 ) : temp = temp. next i = i + 1# See in Image, circle 1 newNode. next = temp. next# See in Image, Circle 2 (temp. next ).prev = newNode# See in Image, Circle 3 temp. next = newNode# See in Image, Circle 4 newNode.prev = tempreturn startreturn start# Function to create circular # doubly linked list from array elements def createList(arr, n, start):# Declare newNode and temporary pointer newNode = None temp = None i = 0# Iterate the loop until array length while (i < n) :# Create new node newNode = getNode()# Assign the array data newNode.data = arr[i]# If it is first element # Put that node prev and next as start # as it is circular if (i = = 0 ) : start = newNode newNode.prev = start newNode. next = startelse :# Find the last node temp = (start).prev# Add the last node to make them # in circular fashion temp. next = newNode newNode. next = start newNode.prev = temp temp = start temp.prev = newNode i = i + 1 ; return start# Driver Code if __name__ = ="__main__" : # Array elements to create # circular doubly linked list arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr)# Start Pointer start = None# Create the List start = createList(arr, n, start)# Display the list before insertion displayList(start)# Inserting 8 at 3rd position start = insertAtLocation(start, 8 , 3 )# Display the list after insertion displayList(start)# This code is contributed by Arnab Kundu

C#

//C# program to convert insert //an element at a specific position //in a circular doubly linked listing, //end and middle using System; class GFG { //Doubly linked list node public class node { public int data; public node next; public node prev; }; //Utility function to create a node in memory static node getNode() { return new node(); } //Function to display the list static int displayList( node temp) { node t = temp; if (temp == null ) return 0; else { Console.WriteLine( "The list is: " ); while (temp.next != t) { Console.Write( temp.data + " " ); temp = temp.next; } Console.WriteLine( temp.data ); return 1; } } //Function to count nunmber of //elements in the list static int countList( node start) { //Declare temp pointer to //traverse the list node temp = start; //Variable to store the count int count = 0; //Iterate the list and //increment the count while (temp.next != start) { temp = temp.next; count++; } //As the list is circular, increment //the counter at last count++; return count; } //Function to insert a node at //a given position in the //circular doubly linked list static node insertAtLocation( node start, int data, int loc) { //Declare two pointers node temp, newNode; int i, count; //Create a new node in memory newNode = getNode(); //Point temp to start temp = start; //count of total elements in the list count = countList(start); //If list is empty or the position is //not valid, return false if (temp == null || count < loc) return start; else { //Assign the data newNode.data = https://www.lsbin.com/data; //Iterate till the loc for (i = 1; i < loc - 1; i++) { temp = temp.next; } //See in Image, circle 1 newNode.next = temp.next; //See in Image, Circle 2 (temp.next).prev = newNode; //See in Image, Circle 3 temp.next = newNode; //See in Image, Circle 4 newNode.prev = temp; return start; } } //Function to create circular doubly //linked list from array elements static node createList( int []arr, int n, node start) { //Declare newNode and temporary pointer node newNode, temp; int i; //Iterate the loop until array length for (i = 0; i < n; i++) { //Create new node newNode = getNode(); //Assign the array data newNode.data = arr[i]; //If it is first element //Put that node prev and next as start //as it is circular if (i == 0) { start = newNode; newNode.prev = start; newNode.next = start; } else { //Find the last node temp = (start).prev; //Add the last node to make them //in circular fashion temp.next = newNode; newNode.next = start; newNode.prev = temp; temp = start; temp.prev = newNode; } } return start; } //Driver Code public static void Main() { //Array elements to create //circular doubly linked list int []arr = { 1, 2, 3, 4, 5, 6 }; int n = arr.Length; //Start Pointer node start = null ; //Create the List start = createList(arr, n, start); //Display the list before insertion displayList(start); //Inserting 8 at 3rd position start = insertAtLocation(start, 8, 3); //Display the list after insertion displayList(start); } } /* This code contributed by PrinciRaj1992 */

输出如下：

The list is: 1 2 3 4 5 6 The list is: 1 2 8 3 4 5 6

【算法题（如何在循环双链表的特定位置进行插入（））】时间复杂度：O(n)=> 用于计数列表, O(n)=> 插入元素。因此, 总复杂度为O(n + n)= O(n)

推荐阅读

• 

  飞亚达手表回收 飞亚达机械手表价格
• 

  知心爱人付笛声任静歌词知心爱人歌曲任静,付笛声简谱
• 

  识别情绪，控制和养成情绪
• 

  脊髓再生成功 高位截瘫吧
• 

  广州积分入学小学积分后初中还要积分吗
• 

  耳朵疼是怎么回事
• 

  mysql模糊查询匹配最优 mysql多条件模糊查找
• 

  凝聚的近义词是什么词？凝聚的近义词是什么?
• 

  秦国是如何从弱小走向霸主的呢？
• 

  车辆保养多久做一次?汽车保养明细表大全 车辆保养多久做一次
• 

  浅谈《伤寒论》的辨证思维方式
• 

  描能组什么词语
• 

  医生|50岁的阿姨抽出“猪油血”，医生提醒：春节饮食要注意
• 

  爱普生打印机固件刷机
• 

  对于非法出售增值税专用发票案公安追诉标准是多少
• 

  绘本讲师训练营【31期】20/21实践原创《鳄鱼怕怕，牙医怕怕》
• 

  快速调出照片的梦幻紫色调
• 

  吃啥降低胆固醇最快 吃什么降低胆固醇最快
• 

  系统安全性分析
• 

  酸梅汤的功效与作用 夏季喝酸梅汤有啥好处

• 数据结构概述|S1（线性数据结构）
• 面向服务的架构是什么（如何理解？）
• 算法设计（最大循环子数组总和）
• 概率统计|辛普森悖论（加州大学伯克利分校的诉讼）
• 算法题（检查数字是否为回文）
• Google软件工程实习生，2019年秋季–北美
• 德里面试经验– 1年经验
• 对字母数字字符串进行排序，以使字母和数字的位置保持不变
• 缓存中的透写和回写是什么（详细介绍）