Lista enlazada XOR: una lista doblemente enlazada eficiente en memoria | conjunto 2

En la publicación anterior , discutimos cómo se puede crear un enlace doble utilizando solo un espacio para el campo de dirección con cada Node. En esta publicación, discutiremos la implementación de la lista doblemente enlazada eficiente en memoria. Discutiremos principalmente las siguientes dos funciones simples.

  1. Una función para insertar un nuevo Node al principio.
  2. Una función para recorrer la lista en dirección hacia adelante.

En el siguiente código, la función insert() inserta un nuevo Node al principio. Necesitamos cambiar el puntero principal de la Lista enlazada, por eso se usa un puntero doble (Ver esto ). Primero analicemos algunas cosas de nuevo que se han discutido en la publicación anterior . Almacenamos XOR de los Nodes siguientes y anteriores con cada Node y lo llamamos npx, que es el único miembro de dirección que tenemos con cada Node. Cuando insertamos un nuevo Node al principio, npx del nuevo Node siempre será XOR de NULL y cabeza actual. Y npx del encabezado actual debe cambiarse a XOR del nuevo Node y el Node al lado del encabezado actual.
imprimirLista()atraviesa la lista en dirección de avance. Imprime valores de datos de cada Node. Para recorrer la lista, necesitamos obtener un puntero al siguiente Node en cada punto. Podemos obtener la dirección del siguiente Node haciendo un seguimiento del Node actual y el Node anterior. Si hacemos XOR de curr->npx y prev, obtenemos la dirección del siguiente Node. 

Complete Interview Preparation - GFG

C++

/* C++ Implementation of Memory 
efficient Doubly Linked List */
#include <bits/stdc++.h>
#include <cinttypes> 
using namespace std;
  
// Node structure of a memory 
// efficient doubly linked list 
class Node 
{ 
    public:
    int data; 
    Node* npx; /* XOR of next and previous node */
}; 
  
/* returns XORed value of the node addresses */
Node* XOR (Node *a, Node *b) 
{ 
    return reinterpret_cast<Node *>(
      reinterpret_cast<uintptr_t>(a) ^ 
      reinterpret_cast<uintptr_t>(b)); 
} 
  
/* Insert a node at the beginning of the 
XORed linked list and makes the newly 
inserted node as head */
void insert(Node **head_ref, int data) 
{ 
    // Allocate memory for new node 
    Node *new_node = new Node(); 
    new_node->data = data; 
  
    /* Since new node is being inserted at the 
    beginning, npx of new node will always be 
    XOR of current head and NULL */
    new_node->npx = *head_ref; 
  
    /* If linked list is not empty, then npx of 
    current head node will be XOR of new node 
    and node next to current head */
    if (*head_ref != NULL) 
    { 
        // *(head_ref)->npx is XOR of NULL and next. 
        // So if we do XOR of it with NULL, we get next 
        (*head_ref)->npx = XOR(new_node, (*head_ref)->npx); 
    } 
  
    // Change head 
    *head_ref = new_node; 
} 
  
// prints contents of doubly linked 
// list in forward direction 
void printList (Node *head) 
{ 
    Node *curr = head; 
    Node *prev = NULL; 
    Node *next; 
  
    cout << "Following are the nodes of Linked List: \n"; 
  
    while (curr != NULL) 
    { 
        // print current node 
        cout<<curr->data<<" "; 
  
        // get address of next node: curr->npx is 
        // next^prev, so curr->npx^prev will be 
        // next^prev^prev which is next 
        next = XOR (prev, curr->npx); 
  
        // update prev and curr for next iteration 
        prev = curr; 
        curr = next; 
    } 
} 
  
// Driver code 
int main () 
{ 
    /* Create following Doubly Linked List 
    head-->40<-->30<-->20<-->10 */
    Node *head = NULL; 
    insert(&head, 10); 
    insert(&head, 20); 
    insert(&head, 30); 
    insert(&head, 40); 
  
    // print the created list 
    printList (head); 
  
    return (0); 
} 
  
// This code is contributed by rathbhupendra

C

/* C Implementation of Memory 
   efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
  
// Node structure of a memory 
// efficient doubly linked list
struct Node
{
    int data;
    struct Node* npx; /* XOR of next and previous node */
};
  
/* returns XORed value of the node addresses */
struct Node* XOR (struct Node *a, struct Node *b)
{
    return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
  
/* Insert a node at the beginning of the 
   XORed linked list and makes the newly
   inserted node as head */
void insert(struct Node **head_ref, int data)
{
    // Allocate memory for new node
    struct Node *new_node = (struct Node *) malloc (sizeof (struct Node) );
    new_node->data = data;
  
    /* Since new node is being inserted at the 
       beginning, npx of new node will always be
       XOR of current head and NULL */
    new_node->npx = *head_ref;
  
    /* If linked list is not empty, then npx of 
       current head node will be XOR of new node
       and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. 
        // So if we do XOR of it with NULL, we get next
        (*head_ref)->npx = XOR(new_node, (*head_ref)->npx);
    }
  
    // Change head
    *head_ref = new_node;
}
  
// prints contents of doubly linked
// list in forward direction
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)
    {
        // print current node
        printf ("%d ", curr->data);
  
        // get address of next node: curr->npx is 
        // next^prev, so curr->npx^prev will be
        // next^prev^prev which is next
        next = XOR (prev, curr->npx);
  
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
  
// Driver program to test above functions
int main ()
{
    /* Create following Doubly Linked List
    head-->40<-->30<-->20<-->10 */
    struct Node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
  
    // print the created list
    printList (head);
  
    return (0);
}

Python3

# Python3 implementation of Memory
# efficient Doubly Linked List
  
# library for providing C 
# compatible data types
import ctypes
  
# Node class for memory
# efficient doubly linked list
class Node:
      
    def __init__(self, data):
          
        self.data = data
          
        # XOR of next and previous node
        self.npx = 0  
  
class XorLinkedList:
      
    def __init__(self):
          
        self.head = None
        self.__nodes = []
          
    # Returns XORed value of the node addresses
    def XOR(self, a, b):
          
        return a ^ b
        
    # Insert a node at the beginning of the
    # XORed linked list and makes the newly
    # inserted node as head
    def insert(self, data):
          
        # New node
        node = Node(data)
  
        # Since new node is being inserted at 
        # the beginning, npx of new node will
        # always be XOR of current head and NULL
        node.npx = id(self.head)
  
        # If linked list is not empty, then
        # npx of current head node will be 
        # XOR of new node and node next to
        # current head
        if self.head is not None:
              
            # head.npx is XOR of None and next.
            # So if we do XOR of it with None, 
            # we get next
            self.head.npx = self.XOR(id(node), 
                                     self.head.npx)
  
        self.__nodes.append(node)
          
        # Change head
        self.head = node
  
    # Prints contents of doubly linked
    # list in forward direction
    def printList(self):
        
        if self.head != None:
            prev_id = 0
            curr = self.head
            next_id = 1
              
            print("Following are the nodes "
                  "of Linked List:")
              
            while curr is not None:
                  
                # Print current node
                print(curr.data, end = ' ')
                  
                # Get address of next node: curr.npx is
                # next^prev, so curr.npx^prev will be
                # next^prev^prev which is next
                next_id = self.XOR(prev_id, curr.npx)
                  
                # Update prev and curr for next iteration
                prev_id = id(curr)
                curr = self.__type_cast(next_id)
  
    # Method to return a new instance of type
    # which points to the same memory block.
    def __type_cast(self, id):
          
        return ctypes.cast(id, ctypes.py_object).value
  
# Driver code
if __name__ == '__main__':
      
    obj = XorLinkedList()
      
    # Create following Doubly Linked List
    # head-->40<-->30<-->20<-->10
    obj.insert(10)
    obj.insert(20)
    obj.insert(30)
    obj.insert(40)
  
    # Print the created list
    obj.printList()
  
# This code is contributed by MuskanKalra1
Producción

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

Tenga en cuenta que XOR de punteros no está definido por el estándar C/C++. Por lo tanto, es posible que la implementación anterior no funcione en todas las plataformas.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *