Рубрики

XOR Linked List — Двусвязный список с эффективным использованием памяти | Набор 2

В предыдущем посте мы обсуждали, как создать двусвязную связь, используя только одно пространство для поля адреса с каждым узлом. В этом посте мы обсудим реализацию эффективного использования памяти двусвязным списком. В основном мы обсудим следующие две простые функции.

1) Функция для вставки нового узла в начале.
2) Функция для перемещения по списку в прямом направлении.

В следующем коде функция insert () вставляет новый узел в начале. Нам нужно изменить указатель заголовка Linked List, поэтому используется двойной указатель (см. Это ). Давайте сначала обсудим снова несколько вещей , которые были обсуждены в предыдущем посте . Мы храним XOR следующего и предыдущего узлов с каждым узлом и называем его npx, который является единственным адресным элементом, который у нас есть с каждым узлом. Когда мы вставляем новый узел в начале, npx нового узла всегда будет XOR NULL и текущей головой. И npx текущего заголовка должен быть изменен на XOR нового узла и узла рядом с текущим заголовком.

printList () пересекает список в прямом направлении. Он печатает значения данных из каждого узла. Чтобы пройти список, нам нужно получить указатель на следующий узел в каждой точке. Мы можем получить адрес следующего узла, отслеживая текущий узел и предыдущий узел. Если мы сделаем XOR для curr-> npx и prev, мы получим адрес следующего узла.

C ++

/ * C ++ реализация памяти
эффективный двусвязный список * /
#include <bits/stdc++.h>
#include <inttypes.h> 

using namespace std;

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

class Node 

    public:

    int data; 

    Node* npx; / * XOR следующего и предыдущего узла * /

}; 

  
/ * возвращает значение XORed адресов узлов * /
Node* XOR (Node *a, Node *b) 

    return (Node*) ((uintptr_t) (a) ^ (uintptr_t) (b)); 

  
/ * Вставить узел в начале
XORed связанный список и делает новый
вставленный узел как голова * /

void insert(Node **head_ref, int data) 

    // Выделим память для нового узла

    Node *new_node = new Node(); 

    new_node->data = data; 

  

    / * Так как новый узел вставляется в

    начало, npx нового узла всегда будет

    XOR текущей головы и NULL * /

    new_node->npx = XOR(*head_ref, NULL); 

  

    / * Если связанный список не пуст, то npx из

    текущий головной узел будет XOR нового узла

    и узел рядом с текущей головой * /

    if (*head_ref != NULL) 

    

        // * (head_ref) -> npx - это XOR NULL и следующий.

        // Итак, если мы сделаем XOR с NULL, мы получим следующее

        Node* next = XOR((*head_ref)->npx, NULL); 

        (*head_ref)->npx = XOR(new_node, next); 

    

  

    // Изменить голову

    *head_ref = new_node; 

  
// печатает содержимое двусвязного
// список в прямом направлении

void printList (Node *head) 

    Node *curr = head; 

    Node *prev = NULL; 

    Node *next; 

  

    cout << "Following are the nodes of Linked List: \n"

  

    while (curr != NULL) 

    

        // напечатать текущий узел

        cout<<curr->data<<" "

  

        // получаем адрес следующего узла: curr-> npx is

        // следующий ^ пред, так что curr-> npx ^ пред будет

        // следующий ^ пред ^ пред, который следующий

        next = XOR (prev, curr->npx); 

  

        // обновляем prev и curr для следующей итерации

        prev = curr; 

        curr = next; 

    

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

int main () 

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

    голова -> 40 <-> 30 <-> 20 <-> 10 * /

    Node *head = NULL; 

    insert(&head, 10); 

    insert(&head, 20); 

    insert(&head, 30); 

    insert(&head, 40); 

  

    // распечатать созданный список

    printList (head); 

  

    return (0); 

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

С

/ * C реализация памяти

   эффективный двусвязный список * /

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

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

struct Node

{

    int data;

    struct Node* npx; / * XOR следующего и предыдущего узла * /

};

  
/ * возвращает значение XORed адресов узлов * /

struct Node* XOR (struct Node *a, struct Node *b)

{

    return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));

}

  
/ * Вставить узел в начале

   XORed связанный список и делает новый

   вставленный узел как голова * /

void insert(struct Node **head_ref, int data)

{

    // Выделим память для нового узла

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

    new_node->data = data;

  

    / * Так как новый узел вставляется в

       начало, npx нового узла всегда будет

       XOR текущей головы и NULL * /

    new_node->npx = XOR(*head_ref, NULL);

  

    / * Если связанный список не пуст, то npx из

       текущий головной узел будет XOR нового узла

       и узел рядом с текущей головой * /

    if (*head_ref != NULL)

    {

        // * (head_ref) -> npx - это XOR NULL и следующий.

        // Итак, если мы сделаем XOR с NULL, мы получим следующее

        struct Node* next = XOR((*head_ref)->npx, NULL);

        (*head_ref)->npx = XOR(new_node, next);

    }

  

    // Изменить голову

    *head_ref = new_node;

}

  
// печатает содержимое двусвязного
// список в прямом направлении

void printList (struct Node *head)

{

    struct Node *curr = head;

    struct Node *prev = NULL;

    struct Node *next;

  

    printf ("Following are the nodes of Linked List: \n");

  

    while (curr != NULL)

    {

        // напечатать текущий узел

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

  

        // получаем адрес следующего узла: curr-> npx is

        // следующий ^ пред, так что curr-> npx ^ пред будет

        // следующий ^ пред ^ пред, который следующий

        next = XOR (prev, curr->npx);

  

        // обновляем prev и curr для следующей итерации

        prev = curr;

        curr = next;

    }

}

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

int main ()

{

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

    голова -> 40 <-> 30 <-> 20 <-> 10 * /

    struct Node *head = NULL;

    insert(&head, 10);

    insert(&head, 20);

    insert(&head, 30);

    insert(&head, 40);

  

    // распечатать созданный список

    printList (head);

  

    return (0);

}


Выход:

Following are the nodes of Linked List:
40 30 20 10

Обратите внимание, что XOR указателей не определяется стандартом C / C ++. Таким образом, приведенная выше реализация может работать не на всех платформах.

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

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

XOR Linked List — Двусвязный список с эффективным использованием памяти | Набор 2

0.00 (0%) 0 votes