Рубрики

Двойной круговой связанный список | Комплект 1 (Введение и вставка)

Условие : двусвязный список, круговой связный список

Круговой двусвязный список имеет свойства как двусвязного списка, так и циклического связанного списка, в котором два последовательных элемента связаны или связаны предыдущим и следующим указателем, а последний узел указывает на первый узел следующим указателем, а также первый узел указывает на последний узел предыдущий указатель

Ниже приводится представление узла кругового двусвязного списка в C / C ++:

// Structure of the node 
struct node
{
    int data;
    struct node *next; // Pointer to next node
    struct node *prev; // Pointer to previous node
};

Вставка в круговой двусвязный список

  1. Вставка в конец списка или в пустой список
    • Пустой список (start = NULL): узел (Say N) вставляется с data = 5, поэтому предыдущий указатель N указывает на N, а следующий указатель N также указывает на N. Но теперь начальный указатель указывает на первый узел списка ,

    • Список изначально содержит несколько узлов, начальные точки указывают на первый узел списка: узел (скажем, M) вставляется с data = 7, поэтому предыдущий указатель M указывает на последний узел, следующий указатель M указывает на первый узел и следующий узел последует указатель указывает на этот узел М, а предыдущий указатель первого узла указывает на этот узел М.

      // Функция для вставки в конце

      void insertEnd(struct Node** start, int value)

      {

          // Если список пуст, создать отдельный узел

          // круговой и двойной список

          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;

          }

        

          // Если список не пуст

        

          / * Найти последний узел * /

          Node *last = (*start)->prev;

        

          // Создать узел динамически

          struct Node* new_node = new Node;

          new_node->data = value;

        

          // Начало будет следующим из new_node

          new_node->next = *start;

        

          // Сделать новый узел предшествующим началу

          (*start)->prev = new_node;

        

          // Сделать последний предшествующий новый узел

          new_node->prev = last;

        

          // Сделать новый узел следующим за старым последним

          last->next = new_node;

      }

  2. Вставка в начале списка: Чтобы вставить узел в начало списка, создайте узел (скажем, T) с data = 5, T следующий указатель указывает на первый узел списка, T предыдущий указатель указывает на последний узел list, следующий указатель последнего узла указывает на этот T-узел, предыдущий указатель первого узла также указывает на этот T-узел и, наконец, не забудьте переместить указатель «Start» на этот T-узел.

    // Функция для вставки узла в начале
    // списка,

    void insertBegin(struct Node** start, int value)

    {

        // Указатель указывает на последний узел

        struct Node *last = (*start)->prev;

      

        struct Node* new_node = new Node;

        new_node->data = value;   // Вставка данных

      

        // настройка предыдущего и следующего нового узла

        new_node->next = *start;

        new_node->prev = last;

      

        // Обновляем следующий и предыдущий указатели запуска

        // и последний

        last->next = (*start)->prev = new_node;

      

        // Обновить стартовый указатель

        *start = new_node;

    }

  3. Вставка между узлами списка : для вставки узла между списками требуются два значения данных: одно, после которого будет вставлен новый узел, а другое — данные нового узла.

    // Функция для вставки узла со значением в качестве значения1.
    // Новый узел вставляется после узла с
    // со значением2

    void insertAfter(struct Node** start, int value1,

                                          int value2)

    {

        struct Node* new_node = new Node;

        new_node->data = value1; // Вставка данных

      

        // Найти узел, имеющий значение2, и следующий его узел

        struct Node *temp = *start;

        while (temp->data != value2)

            temp = temp->next;

        struct Node *next = temp->next;

      

        // вставить new_node между temp и next.

        temp->next = new_node;

        new_node->prev = temp;

        new_node->next = next;

        next->prev = new_node;

    }

Ниже приводится полная программа, которая использует все вышеперечисленные методы для создания кругового двусвязного списка.

C ++

// C ++ программа для иллюстрации вставки узла в
// Двухсторонний список Cicular в начале, конец
// и середина
#include <bits/stdc++.h>

using namespace std;

  
// Структура узла

struct Node

{

    int data;

    struct Node *next;

    struct Node *prev;

};

  
// Функция для вставки в конце

void insertEnd(struct Node** start, int value)

{

    // Если список пуст, создать отдельный узел

    // круговой и двойной список

    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;

    }

  

    // Если список не пуст

  

    / * Найти последний узел * /

    Node *last = (*start)->prev;

  

    // Создать узел динамически

    struct Node* new_node = new Node;

    new_node->data = value;

  

    // Начало будет следующим из new_node

    new_node->next = *start;

  

    // Сделать новый узел предшествующим началу

    (*start)->prev = new_node;

  

    // Сделать последний предшествующий новый узел

    new_node->prev = last;

  

    // Сделать новый узел следующим за старым последним

    last->next = new_node;

}

  
// Функция для вставки узла в начале
// списка,

void insertBegin(struct Node** start, int value)

{

    // Указатель указывает на последний узел

    struct Node *last = (*start)->prev;

  

    struct Node* new_node = new Node;

    new_node->data = value;   // Вставка данных

  

    // настройка предыдущего и следующего нового узла

    new_node->next = *start;

    new_node->prev = last;

  

    // Обновляем следующий и предыдущий указатели запуска

    // и последний

    last->next = (*start)->prev = new_node;

  

    // Обновить стартовый указатель

    *start = new_node;

}

  
// Функция для вставки узла со значением в качестве значения1.
// Новый узел вставляется после узла с
// со значением2

void insertAfter(struct Node** start, int value1,

                                      int value2)

{

    struct Node* new_node = new Node;

    new_node->data = value1; // Вставка данных

  

    // Найти узел, имеющий значение2, и следующий его узел

    struct Node *temp = *start;

    while (temp->data != value2)

        temp = temp->next;

    struct Node *next = temp->next;

  

    // вставить new_node между temp и 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("\nTraversal in forward direction \n");

    while (temp->next != start)

    {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("%d ", temp->data);

  

    printf("\nTraversal in reverse direction \n");

    Node *last = start->prev;

    temp = last;

    while (temp->prev != last)

    {

        printf("%d ", temp->data);

        temp = temp->prev;

    }

    printf("%d ", temp->data);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* start = NULL;

  

    // Вставляем 5. Таким образом, связанный список становится 5-> NULL

    insertEnd(&start, 5);

  

    // Вставить 4 в начале. Так связано

    // список становится 4-> 5

    insertBegin(&start, 4);

  

    // Вставить 7 в конце. Так связан список

    // становится 4-> 5-> 7

    insertEnd(&start, 7);

  

    // Вставить 8 в конце. Так связан список

    // становится 4-> 5-> 7-> 8

    insertEnd(&start, 8);

  

    // Вставляем 6, после 5. Итак, связанный список

    // становится 4-> 5-> 6-> 7-> 8

    insertAfter(&start, 6, 5);

  

    printf("Created circular doubly linked list is: ");

    display(start);

  

    return 0;

}

Джава

// Java-программа для иллюстрации вставки узла в
// Двухсторонний список Cicular в начале, конец
// и середина

import java.util.*;

  

class GFG

  

static Node start;

  
// Структура узла

static class Node 

    int data; 

    Node next; 

    Node prev; 

}; 

  
// Функция для вставки в конце

static void insertEnd(int value) 

    // Если список пуст, создать отдельный узел

    // круговой и двойной список

    if (start == null

    

        Node new_node = new Node(); 

        new_node.data = value; 

        new_node.next = new_node.prev = new_node; 

        start = new_node; 

        return

    

  

    // Если список не пуст

  

    / * Найти последний узел * /

    Node last = (start).prev; 

  

    // Создать узел динамически

    Node new_node = new Node(); 

    new_node.data = value; 

  

    // Начало будет следующим из new_node

    new_node.next = start; 

  

    // Сделать новый узел предшествующим началу

    (start).prev = new_node; 

  

    // Сделать последний предшествующий новый узел

    new_node.prev = last; 

  

    // Сделать новый узел следующим за старым последним

    last.next = new_node; 

  
// Функция для вставки узла в начале
// списка,

static void insertBegin(int value) 

    // Указатель указывает на последний узел

    Node last = (start).prev; 

  

    Node new_node = new Node(); 

    new_node.data = value; // Вставка данных

  

    // настройка предыдущего и следующего нового узла

    new_node.next = start; 

    new_node.prev = last; 

  

    // Обновляем следующий и предыдущий указатели запуска

    // и последний

    last.next = (start).prev = new_node; 

  

    // Обновить стартовый указатель

    start = new_node; 

  
// Функция для вставки узла со значением в качестве значения1.
// Новый узел вставляется после узла с
// со значением2

static void insertAfter(int value1, 

                                    int value2) 

    Node new_node = new Node(); 

    new_node.data = value1; // Вставка данных

  

    // Найти узел, имеющий значение2, и следующий его узел

    Node temp = start; 

    while (temp.data != value2) 

        temp = temp.next; 

    Node next = temp.next; 

  

    // вставить new_node между temp и 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("\nTraversal in forward direction \n"); 

    while (temp.next != start) 

    

        System.out.printf("%d ", temp.data); 

        temp = temp.next; 

    

    System.out.printf("%d ", temp.data); 

  

    System.out.printf("\nTraversal in reverse direction \n"); 

    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); 

  
/ * Код водителя * /

public static void main(String[] args) 

    / * Начнем с пустого списка * /

    Node start = null

  

    // Вставляем 5. Таким образом, связанный список становится 5.null

    insertEnd(5); 

  

    // Вставить 4 в начале. Так связано

    // список становится 4.5

    insertBegin(4); 

  

    // Вставить 7 в конце. Так связан список

    // становится 4.5.7

    insertEnd(7); 

  

    // Вставить 8 в конце. Так связан список

    // становится 4.5.7.8

    insertEnd(8); 

  

    // Вставляем 6, после 5. Итак, связанный список

    // становится 4.5.6.7.8

    insertAfter(6, 5); 

  

    System.out.printf("Created circular doubly linked list is: "); 

    display(); 


  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для иллюстрации вставки
# Узел в определенном двусвязном списке
# в начале, конце и середине

start = None

  
# Структура узла

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

        self.prev = None

  
# Функция для вставки в конце

def insertEnd(value) :

    global start

      

    # Если список пуст, создайте

    # один узел круговой и двойной список

    if (start == None) :

  

        new_node = Node(0

        new_node.data = value 

        new_node.next = new_node.prev = new_node 

        start = new_node 

        return

  

    # Если список не пуст

  

    # Найти последний узел * /

    last = (start).prev 

  

    # Создать узел динамически

    new_node = Node(0

    new_node.data = value 

  

    # Начало будет следующим из new_node

    new_node.next = start 

  

    # Сделать новый узел предшествующим началу

    (start).prev = new_node 

  

    # Сделать последний предшествующий новый узел

    new_node.prev = last 

  

    # Сделать новый узел следующим за старым последним

    last.next = new_node 

  
# Функция для вставки узла в начале
№ списка,

def insertBegin( value) :

    global start

      

    # Указатель указывает на последний узел

    last = (start).prev 

  

    new_node = Node(0

    new_node.data = value # Вставка данных

  

    # настройка предыдущего и

    # следующий новый узел

    new_node.next = start 

    new_node.prev = last 

  

    # Обновление следующих и предыдущих указателей

    # начало и последний.

    last.next = (start).prev = new_node 

  

    # Обновить стартовый указатель

    start = new_node 

  
# Функция для вставки узла со значением в качестве значения1.
# Новый узел вставляется после узла с
# со значением2

def insertAfter(value1, value2) :

    global start

    new_node = Node(0

    new_node.data = value1 # Вставка данных

  

    # Найти узел, имеющий значение2 и

    # следующий узел этого

    temp = start 

    while (temp.data != value2) :

        temp = temp.next

    next = temp.next

  

    # вставить new_node между temp и 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)

  
Код водителя

if __name__ == '__main__'

    global start

      

    # Начнем с пустого списка

    start = None

      

    # Вставить 5. Таким образом, связанный список становится 5. Нет

    insertEnd(5

  

    # Вставьте 4 в начале. Так связано

    # список становится 4,5

    insertBegin(4

  

    # Вставьте 7 в конце. Так связан список

    # становится 4.5.7

    insertEnd(7

  

    # Вставьте 8 в конце. Так связан список

    # становится 4.5.7.8

    insertEnd(8

  

    # Вставить 6, после 5. Итак, связанный список

    # становится 4.5.6.7.8

    insertAfter(6, 5

  

    print ("Created circular doubly linked list is: "

    display() 

  
# Этот код предоставлен Арнаб кунду

C #

// C # программа для иллюстрации вставки узла в
// Двухсторонний список Cicular в начале, конец
// и середина

using System;

using System.Collections.Generic;

  

class GFG

static Node start;

  
// Структура узла

public class Node 

    public int data; 

    public Node next; 

    public Node prev; 

}; 

  
// Функция для вставки в конце

static void insertEnd(int value) 

    Node new_node;

      

    // Если список пуст, создать отдельный узел

    // круговой и двойной список

    if (start == null

    

        new_node = new Node(); 

        new_node.data = value; 

        new_node.next = new_node.prev = new_node; 

        start = new_node; 

        return

    

  

    // Если список не пуст

  

    / * Найти последний узел * /

    Node last = (start).prev; 

  

    // Создать узел динамически

    new_node = new Node(); 

    new_node.data = value; 

  

    // Начало будет следующим из new_node

    new_node.next = start; 

  

    // Сделать новый узел предшествующим началу

    (start).prev = new_node; 

  

    // Сделать последний предшествующий новый узел

    new_node.prev = last; 

  

    // Сделать новый узел следующим за старым последним

    last.next = new_node; 

  
// Функция для вставки узла в начале
// списка,

static void insertBegin(int value) 

    // Указатель указывает на последний узел

    Node last = (start).prev; 

  

    Node new_node = new Node(); 

    new_node.data = value; // Вставка данных

  

    // настройка предыдущего и следующего нового узла

    new_node.next = start; 

    new_node.prev = last; 

  

    // Обновляем следующий и предыдущий указатели запуска

    // и последний

    last.next = (start).prev = new_node; 

  

    // Обновить стартовый указатель

    start = new_node; 

  
// Функция для вставки узла со значением в качестве значения1.
// Новый узел вставляется после узла с
// со значением2

static void insertAfter(int value1, int value2) 

    Node new_node = new Node(); 

    new_node.data = value1; // Вставка данных

  

    // Найти узел, имеющий значение2, и следующий его узел

    Node temp = start; 

    while (temp.data != value2) 

        temp = temp.next; 

    Node next = temp.next; 

  

    // вставить new_node между temp и 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("\nTraversal in forward direction \n"); 

    while (temp.next != start) 

    

        Console.Write("{0} ", temp.data); 

        temp = temp.next; 

    

    Console.Write("{0} ", temp.data); 

  

    Console.Write("\nTraversal in reverse direction \n"); 

    Node last = start.prev; 

    temp = last; 

    while (temp.prev != last) 

    

        Console.Write("{0} ", temp.data); 

        temp = temp.prev; 

    

    Console.Write("{0} ", temp.data); 

  
/ * Код водителя * /

public static void Main(String[] args) 

    / * Начнем с пустого списка * /

    Node start = null

  

    // Вставляем 5. Таким образом, связанный список становится 5.null

    insertEnd(5); 

  

    // Вставить 4 в начале. Так связано

    // список становится 4.5

    insertBegin(4); 

  

    // Вставить 7 в конце. Так связан список

    // становится 4.5.7

    insertEnd(7); 

  

    // Вставить 8 в конце. Так связан список

    // становится 4.5.7.8

    insertEnd(8); 

  

    // Вставляем 6, после 5. Итак, связанный список

    // становится 4.5.6.7.8

    insertAfter(6, 5); 

  

    Console.Write("Created circular doubly linked list is: "); 

    display(); 


  
// Этот код предоставлен Rajput-Ji

Выход:

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).
  • Круговые двусвязные списки используются для реализации сложных структур данных, таких как куча Фибоначчи .

Недостатки

  • Для размещения предыдущего указателя требуется немного дополнительной памяти в каждом узле.
  • Множество указателей, задействованных при реализации или выполнении операций над списком. Таким образом, с указателями следует обращаться осторожно, иначе данные списка могут быть потеряны.

Приложения циркулярного двусвязного списка

  • Управление плейлистом песен в приложениях медиаплеера.
  • Управление корзиной в интернет-магазине.

Эта статья предоставлена Акашем Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Двойной круговой связанный список | Комплект 1 (Введение и вставка)

0.00 (0%) 0 votes