Lista vinculada XOR: elimina el primer Node de la lista vinculada

Dada una lista enlazada XOR , la tarea es eliminar el primer Node de la lista enlazada XOR.

Ejemplos:

Entrada: XLL = 4 < – > 7 < – > 9 < – > 7
Salida: 7 < – > 9 < – > 7
Explicación:
Eliminar el primer Node de la lista enlazada XOR modifica XLL a 7 < – > 9 < – > 7

Entrada: XLL = NULL
Salida: La lista está vacía

Enfoque: la idea es actualizar el Node principal de la lista vinculada XOR al segundo Node de la lista vinculada XOR y eliminar la memoria asignada para el primer Node. Siga los pasos a continuación para resolver el problema:

  • Compruebe si la lista enlazada XOR está vacía o no. Si se encuentra que es cierto, imprima «La lista está vacía» .
  • De lo contrario, actualice el Node principal de la lista vinculada XOR al segundo Node de la lista vinculada.
  • Elimine el primer Node de la memoria.

A continuación se muestra la implementación del enfoque anterior:

C

// C program to implement
// the above approach
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
  
// Structure of a node
// in XOR linked list
struct Node {
  
    // Stores data value
    // of a node
    int data;
  
    // Stores XOR of previous
    // pointer and next pointer
    struct Node* nxp;
};
  
// Function to find the XOR
// of address two nodes
struct Node* XOR(struct Node* a,
                 struct Node* b)
{
    return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
  
// Function to insert a node with
// given value at given position
struct Node* insert(struct Node** head,
                    int value)
{
  
    // Check If XOR linked list
    // is empty
    if (*head == NULL) {
  
        // Initialize a new Node
        struct Node* node
            = (struct Node*)malloc(sizeof(struct Node));
  
        // Stores data value in
        // the node
        node->data = value;
  
        // Stores XOR of previous
        // and next pointer
        node->nxp = XOR(NULL, NULL);
  
        // Update pointer of head node
        *head = node;
    }
  
    // If the XOR linked list
    // is not empty
    else {
  
        // Stores the address
        // of current node
        struct Node* curr = *head;
  
        // Stores the address
        // of previous node
        struct Node* prev = NULL;
  
        // Initialize a new Node
        struct Node* node
            = (struct Node*)malloc(
                sizeof(struct Node));
  
        // Update curr node address
        curr->nxp = XOR(node,
                        XOR(NULL, curr->nxp));
  
        // Update new node address
        node->nxp = XOR(NULL, curr);
  
        // Update head
        *head = node;
  
        // Update data value of
        // current node
        node->data = value;
    }
    return *head;
}
  
// Function to print elements of
// the XOR Linked List
void printList(struct Node** head)
{
  
    // Stores XOR pointer
    // in current node
    struct Node* curr = *head;
  
    // Stores XOR pointer of
    // in previous Node
    struct Node* prev = NULL;
  
    // Stores XOR pointer of
    // in next node
    struct Node* next;
  
    // Traverse XOR linked list
    while (curr != NULL) {
  
        // Print current node
        printf("%d ", curr->data);
  
        // Forward traversal
        next = XOR(prev, curr->nxp);
  
        // Update prev
        prev = curr;
  
        // Update curr
        curr = next;
    }
}
  
// Function to remove the first node form
// the given linked list
struct Node* delBeginning(struct Node** head)
{
  
    // If list is empty
    if (*head == NULL)
        printf("List Is Empty");
    else {
  
        // Store the node to be deleted
        struct Node* temp = *head;
  
        // Update the head pointer
        *head = XOR(NULL, temp->nxp);
  
        // When the linked list
        // contains only one node
        if (*head != NULL) {
  
            // Update head node address
            (*head)->nxp
                = XOR(NULL, XOR(temp,
                                (*head)->nxp));
        }
  
        free(temp);
    }
    return *head;
}
  
// Driver Code
int main()
{
  
    /* Create following XOR Linked List
    head-->40<-->30<-->20<-->10 */
    struct Node* head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
  
    // Delete the first node
    delBeginning(&head);
  
    /* Print the following XOR Linked List
    head-->30<-->20<-->10 */
    printList(&head);
  
    return (0);
}
Producción:

30 20 10

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por debarpan_bose_chowdhury 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 *