Implementación de la lista enlazada XOR en Python

Requisito previo: Lista vinculada XOR

Una lista doblemente enlazada ordinaria requiere espacio para dos campos de dirección para almacenar las direcciones de los Nodes anterior y siguiente. Se puede crear una versión con uso eficiente de la memoria de la lista doblemente enlazada usando solo un espacio para el campo de dirección con cada Node. Esta lista doblemente enlazada eficiente en memoria se denomina lista enlazada XOR o memoria eficiente, ya que la lista utiliza la operación XOR bit a bit para ahorrar espacio para una dirección. En la lista enlazada XOR, en lugar de almacenar las direcciones de memoria reales, cada Node almacena el XOR de las direcciones de los Nodes anteriores y siguientes.

La implementación de la lista enlazada XOR en Python no es de mucha utilidad porque el recolector de basura de Python no permite guardar el Node cuya dirección está siendo XOR.

Las funciones que se implementan en el siguiente programa son:

  • InsertAtStart(): Método para insertar un Node al principio.
  • InsertAtEnd(): Método para insertar un Node al final.
  • DeleteAtStart(): Método para eliminar un Node al principio.
  • DeleteAtEnd(): Método para eliminar un Node al final.
  • Print(): Método para recorrer la lista enlazada de principio a fin.
  • ReversePrint(): método para recorrer la lista enlazada desde el final hasta el principio.
  • Longitud(): Método para devolver el tamaño de la lista enlazada.
  • PrintByIndex(): Método para devolver el valor de los datos del Node de la lista enlazada especificada por un índice particular.
  • isEmpty(): Método para comprobar si la lista enlazada está vacía o no.
  • __type_cast(): Método para devolver una nueva instancia de tipo que apunta al mismo bloque de memoria.

A continuación se muestra el programa completo de Python para implementar la lista enlazada XOR con los métodos anteriores:

Python3

# import required module
import ctypes
  
  
  
# create node class
class Node:
    def __init__(self, value):
        self.value = value
        self.npx = 0
  
  
          
# create linked list class
class XorLinkedList:
  
    # constructor
    def __init__(self):
        self.head = None
        self.tail = None
        self.__nodes = []
  
    # method to insert node at beginning
    def InsertAtStart(self, value):
        node = Node(value)
        if self.head is None:  # If list is empty
            self.head = node
            self.tail = node
        else:
            self.head.npx = id(node) ^ self.head.npx
            node.npx = id(self.head)
            self.head = node
        self.__nodes.append(node)
  
    # method to insert node at end
    def InsertAtEnd(self, value):
        node = Node(value)
        if self.head is None:  # If list is empty
            self.head = node
            self.tail = node
        else:
            self.tail.npx = id(node) ^ self.tail.npx
            node.npx = id(self.tail)
            self.tail = node
        self.__nodes.append(node)
  
    # method to remove node at beginning
    def DeleteAtStart(self):
        if self.isEmpty():  # If list is empty
            return "List is empty !"
        elif self.head == self.tail:  # If list has 1 node
            self.head = self.tail = None
        elif (0 ^ self.head.npx) == id(self.tail):  # If list has 2 nodes
            self.head = self.tail
            self.head.npx = self.tail.npx = 0
        else:  # If list has more than 2 nodes
            res = self.head.value
            x = self.__type_cast(0 ^ self.head.npx)  # Address of next node
            y = (id(self.head) ^ x.npx)  # Address of next of next node
            self.head = x
            self.head.npx = 0 ^ y
            return res
  
    # method to remove node at end
    def DeleteAtEnd(self):
        if self.isEmpty():  # If list is empty
            return "List is empty !"
        elif self.head == self.tail:  # If list has 1 node
            self.head = self.tail = None
        elif self.__type_cast(0 ^ self.head.npx) == (self.tail):  # If list has 2 nodes
            self.tail = self.head
            self.head.npx = self.tail.npx = 0
        else:  # If list has more than 2 nodes
            prev_id = 0
            node = self.head
            next_id = 1
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
            res = node.value
            x = self.__type_cast(prev_id).npx ^ id(node)
            y = self.__type_cast(prev_id)
            y.npx = x ^ 0
            self.tail = y
            return res
  
    # method to traverse linked list
    def Print(self):
        """We are printing values rather than returning it bacause
        for returning we have to append all values in a list
        and it takes extra memory to save all values in a list."""
  
        if self.head != None:
            prev_id = 0
            node = self.head
            next_id = 1
            print(node.value, end=' ')
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    print(node.value, end=' ')
                else:
                    return
        else:
            print("List is empty !")
  
    # method to traverse linked list in reverse order
    def ReversePrint(self):
  
        # Print Values is reverse order.
        """We are printing values rather than returning it bacause
        for returning we have to append all values in a list
        and it takes extra memory to save all values in a list."""
  
        if self.head != None:
            prev_id = 0
            node = self.tail
            next_id = 1
            print(node.value, end=' ')
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    print(node.value, end=' ')
                else:
                    return
        else:
            print("List is empty !")
  
    # method to get length of linked list
    def Length(self):
        if not self.isEmpty():
            prev_id = 0
            node = self.head
            next_id = 1
            count = 1
            while next_id:
                next_id = prev_id ^ node.npx
                if next_id:
                    prev_id = id(node)
                    node = self.__type_cast(next_id)
                    count += 1
                else:
                    return count
        else:
            return 0
  
    # method to get node data value by index
    def PrintByIndex(self, index):
        prev_id = 0
        node = self.head
        for i in range(index):
            next_id = prev_id ^ node.npx
  
            if next_id:
                prev_id = id(node)
                node = self.__type_cast(next_id)
            else:
                return "Value dosn't found index out of range."
        return node.value
  
    # method to check if the linked list is empty or not
    def isEmpty(self):
        if self.head is None:
            return True
        return False
  
    # method to return a new instance of type
    def __type_cast(self, id):
        return ctypes.cast(id, ctypes.py_object).value
  
  
        
# Driver Code
  
# create object
obj = XorLinkedList()
  
# insert nodes
obj.InsertAtEnd(2)
obj.InsertAtEnd(3)
obj.InsertAtEnd(4)
obj.InsertAtStart(0)
obj.InsertAtStart(6)
obj.InsertAtEnd(55)
  
# display length
print("\nLength:", obj.Length())
  
# traverse
print("\nTraverse linked list:")
obj.Print()
  
print("\nTraverse in reverse order:")
obj.ReversePrint()
  
# display data values by index
print('\nNodes:')
for i in range(obj.Length()):
    print("Data value at index", i, 'is', obj.PrintByIndex(i))
  
# removing nodes
print("\nDelete Last Node: ", obj.DeleteAtEnd())
print("\nDelete First Node: ", obj.DeleteAtStart())
  
# new length
print("\nUpdated length:", obj.Length())
  
# display data values by index
print('\nNodes:')
for i in range(obj.Length()):
    print("Data value at index", i, 'is', obj.PrintByIndex(i))
  
# traverse
print("\nTraverse linked list:")
obj.Print()
  
print("\nTraverse in reverse order:")
obj.ReversePrint()
Producción:

Length: 6

Traverse linked list:
6 0 2 3 4 55 
Traverse in reverse order:
55 4 3 2 0 6 
Nodes:
Data value at index 0 is 6
Data value at index 1 is 0
Data value at index 2 is 2
Data value at index 3 is 3
Data value at index 4 is 4
Data value at index 5 is 55

Delete Last Node:  55

Delete First Node:  6

Updated length: 4

Nodes:
Data value at index 0 is 0
Data value at index 1 is 2
Data value at index 2 is 3
Data value at index 3 is 4

Traverse linked list:
0 2 3 4 
Traverse in reverse order:
4 3 2 0

En el recolector de basura de Python, recopila Nodes y disminuye el recuento de referencias del objeto de un Node cuando el objeto del Node tiene XOR, Python cree que no hay forma de acceder al Node, por lo que usamos el __en el que almacenamos objetos del Node solo para prevenir que se convierta en basura.

Publicación traducida automáticamente

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