Рубрики

Отменить двусвязный список

Напишите функцию C для обращения к заданному двусвязному списку

Смотрите ниже диаграммы для примера.

     (a) Original Doubly Linked List  

     (b) Reversed Doubly Linked List  

Вот простой метод обращения двусвязного списка. Все, что нам нужно сделать, это поменять местами указатели prev и next для всех узлов, изменить prev заголовка (или start) и изменить указатель заголовка в конце.

C ++

/ * C ++ программа для обращения к двусвязному списку * /
#include <bits/stdc++.h>

using namespace std;

  
/ * узел двусвязного списка * /

class Node 

    public:

    int data; 

    Node *next; 

    Node *prev; 

}; 

  
/ * Функция для обращения к двусвязному списку * /

void reverse(Node **head_ref) 

    Node *temp = NULL; 

    Node *current = *head_ref; 

      

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

    двусвязный список * /

    while (current != NULL) 

    

        temp = current->prev; 

        current->prev = current->next; 

        current->next = temp;             

        current = current->prev; 

    

      

    / * Прежде чем менять голову, проверьте, нет ли пустых случаев

        список и список только с одним узлом * /

    if(temp != NULL ) 

        *head_ref = temp->prev; 

  

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в
составление двусвязного списка * /

void push(Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

      

    / * так как мы добавляем в начале,

    prev всегда NULL * /

    new_node->prev = NULL; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);     

  

    / * изменить prev головного узла на новый узел * /

    if((*head_ref) != NULL) 

    (*head_ref)->prev = new_node ; 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Функция для печати узлов в заданном двусвязном списке
Эта функция аналогична printList () односвязного списка * /

void printList(Node *node) 

    while(node != NULL) 

    

        cout << node->data << " "

        node = node->next; 

    

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

int main() 

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

    Node* head = NULL; 

      

    / * Давайте создадим отсортированный связанный список для проверки функций

    Созданный связанный список будет 10-> 8-> 4-> 2 * /

    push(&head, 2); 

    push(&head, 4); 

    push(&head, 8); 

    push(&head, 10); 

      

    cout << "Original Linked list" << endl; 

    printList(head); 

      

    / * Перевернуть двусвязный список * /

    reverse(&head); 

      

    cout << "\nReversed Linked list" << endl; 

    printList(head);         

      

    return 0;

  
// Этот код предоставлен rathbhupendra

С

/ * Программа для реверсирования двусвязного списка * /
#include <stdio.h>
#include <stdlib.h>

  
/ * узел двусвязного списка * /

struct Node

{

  int data;

  struct Node *next;

  struct Node *prev;    

};

  
/ * Функция для обращения к двусвязному списку * /

void reverse(struct Node **head_ref)

{

     struct Node *temp = NULL;  

     struct Node *current = *head_ref;

       

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

       двусвязный список * /

     while (current !=  NULL)

     {

       temp = current->prev;

       current->prev = current->next;

       current->next = temp;              

       current = current->prev;

     }      

       

     / * Прежде чем менять голову, проверьте, нет ли пустых случаев

        список и список только с одним узлом * /

     if(temp != NULL )

        *head_ref = temp->prev;

}     

  

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла при создании двусвязного списка * /

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

            (struct Node*) malloc(sizeof(struct Node));

   

    / * вставить данные * /

    new_node->data  = new_data;

      

    / * так как мы добавляем в начале,

      prev всегда NULL * /

    new_node->prev = NULL;

   

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);    

  

    / * изменить prev головного узла на новый узел * /

    if((*head_ref) !=  NULL)

      (*head_ref)->prev = new_node ;    

   

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref)    = new_node;

}

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

   Эта функция аналогична printList () односвязного списка * /

void printList(struct Node *node)

{

  while(node!=NULL)

  {

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

   node = node->next;

  }

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

int main()

{

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

  struct Node* head = NULL;

   

  / * Давайте создадим отсортированный связанный список для проверки функций

   Созданный связанный список будет 10-> 8-> 4-> 2 * /

  push(&head, 2);

  push(&head, 4);

  push(&head, 8);

  push(&head, 10);

   

  printf("\n Original Linked list ");

  printList(head);

   

  / * Перевернуть двусвязный список * /

  reverse(&head);

   

  printf("\n Reversed Linked list ");

  printList(head);           

   

  getchar();

}

Джава

// Java-программа для обращения к двусвязному списку

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next, prev;

  

        Node(int d) {

            data = d;

            next = prev = null;

        }

    }

  

    / * Функция для обращения к двусвязному списку * /

    void reverse() {

        Node temp = null;

        Node current = head;

  

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

         двусвязный список * /

        while (current != null) {

            temp = current.prev;

            current.prev = current.next;

            current.next = temp;

            current = current.prev;

        }

  

        / * Прежде чем менять голову, проверьте, нет ли пустых случаев

         список и список только с одним узлом * /

        if (temp != null) {

            head = temp.prev;

        }

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    / * Функция для вставки узла в начало двусвязного списка * /

    void push(int new_data) {

        / * выделить узел * /

        Node new_node = new Node(new_data);

  

        / * так как мы добавляем в начале,

         prev всегда NULL * /

        new_node.prev = null;

  

        / * связать старый список с новым узлом * /

        new_node.next = head;

  

        / * изменить prev головного узла на новый узел * /

        if (head != null) {

            head.prev = new_node;

        }

  

        / * переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

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

     Эта функция аналогична printList () односвязного списка * /

    void printList(Node node) {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

  

        / * Давайте создадим отсортированный связанный список для проверки функций

         Созданный связанный список будет 10-> 8-> 4-> 2 * /

        list.push(2);

        list.push(4);

        list.push(8);

        list.push(10);

  

        System.out.println("Original linked list ");

        list.printList(head);

  

        list.reverse();

        System.out.println("");

        System.out.println("The reversed Linked List is ");

        list.printList(head);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

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

  
# Узел двусвязного списка

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.next = None

        self.prev = None

  

class DoublyLinkedList:

     # Конструктор для пустого двусвязного списка

    def __init__(self):

        self.head = None

   

    # Функция обратного двусвязного списка

    def reverse(self):

        temp = None

        current = self.head

          

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

        # двусвязный список

        while current is not None:

            temp = current.prev 

            current.prev = current.next

            current.next = temp

            current = current.prev

  

        # Прежде чем менять голову, проверьте на случаи, как

        # пустой список и список только с одним узлом

        if temp is not None:

            self.head = temp.prev

          

    # Учитывая ссылку на заголовок списка и

    # integer вставляет новый узел в начало списка

    def push(self, new_data):

   

        # 1. Распределяет узел

        # 2. Поместите в него данные

        new_node = Node(new_data)

   

        # 3. Сделать следующий из нового узла в качестве головы и

        # предыдущий как None (уже None)

        new_node.next = self.head

   

        # 4. измените prev главного узла на new_node

        if self.head is not None:

            self.head.prev = new_node

   

        # 5. переместить голову, чтобы указать на новый узел

        self.head = new_node

  

  

    def printList(self, node):

        while(node is not None):

            print node.data,

            node = node.next

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

dll = DoublyLinkedList()

dll.push(2);

dll.push(4);

dll.push(8);

dll.push(10);

  

print "\nOriginal Linked List"

dll.printList(dll.head)

  
# Перевернуть двусвязный список
dll.reverse()

  

print "\n Reversed Linked List"

dll.printList(dll.head)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// AC # программа для обращения к двусвязному списку

using System; 

  

public class LinkedList

  

    static Node head; 

  

    class Node

    

  

        public int data; 

        public Node next, prev; 

  

        public Node(int d) 

        

            data = d; 

            next = prev = null

        

    

  

    / * Функция для обращения к двусвязному списку * /

    void reverse() 

    

        Node temp = null

        Node current = head; 

  

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

        двусвязный список * /

        while (current != null

        

            temp = current.prev; 

            current.prev = current.next; 

            current.next = temp; 

            current = current.prev; 

        

  

        / * Прежде чем менять голову, проверьте

          случаи, такие как пустой список и

         список только с одним узлом * /

        if (temp != null)

        

            head = temp.prev; 

        

    

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    / * Функция для вставки узла в

    составление двусвязного списка * /

    void push(int new_data) 

    

          

        / * выделить узел * /

        Node new_node = new Node(new_data); 

  

        / * так как мы добавляем в начале,

        prev всегда NULL * /

        new_node.prev = null

  

        / * связать старый список с новым узлом * /

        new_node.next = head; 

  

        / * изменить prev головного узла на новый узел * /

        if (head != null

        

            head.prev = new_node; 

        

  

        / * переместить голову, чтобы указать на новый узел * /

        head = new_node; 

    

  

    / * Функция для печати узлов в данном

    двусвязный список Эта функция

    такой же как printList () односвязного lsit * /

    void printList(Node node) 

    

        while (node != null)

        

            Console.Write(node.data + " "); 

            node = node.next; 

        

    

  

    // Код драйвера

    public static void Main(String[] args)

    

        LinkedList list = new LinkedList(); 

  

        / * Давайте создадим отсортированный связанный список

        Для проверки функций созданы ссылки

        список будет 10-> 8-> 4-> 2 * /

        list.push(2); 

        list.push(4); 

        list.push(8); 

        list.push(10); 

  

        Console.WriteLine("Original linked list "); 

        list.printList(head); 

  

        list.reverse(); 

        Console.WriteLine(""); 

        Console.WriteLine("The reversed Linked List is "); 

        list.printList(head); 

    

  
// Этот код предоставлен 29AjayKumar


Выход:

Original linked list 
10 8 4 2 
The reversed Linked List is 
2 4 8 10 

Сложность времени: O (n)

Мы также можем поменять местами данные вместо указателей, чтобы полностью изменить список с двойной связью. Метод, используемый для обращения массива, может использоваться для обмена данными. Обмен данными может быть дорогостоящим по сравнению с указателями, если размер элемента (ов) данных больше.

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете лучшие способы решения той же проблемы

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

Отменить двусвязный список

0.00 (0%) 0 votes