Estructuras de datos definidas por el usuario en Python

En informática, una estructura de datos es una forma lógica de organizar los datos en la memoria de la computadora para que puedan usarse de manera efectiva. Una estructura de datos permite agregar, eliminar, almacenar y mantener datos de manera estructurada. Python admite dos tipos de estructuras de datos:

• Tipos de datos no primitivos: Python tiene una lista, un conjunto y un diccionario como tipos de datos no primitivos que también pueden considerarse sus estructuras de datos integradas.
• Estructuras de datos definidas por el usuario : las estructuras de datos que no son compatibles con python pero que pueden programarse para reflejar la misma funcionalidad utilizando conceptos compatibles con python son estructuras de datos definidas por el usuario. Hay muchas estructuras de datos que se pueden implementar de esta manera:
  • Lista enlazada
  • Pila
  • Cola
  • Árbol
  • Grafico
  • mapa hash

Lista enlazada

Una lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas. Los elementos de una lista vinculada se vinculan mediante punteros como se muestra en la siguiente imagen:
 

Programa:

llist = ['first', 'second', 'third']
print(llist)
 
print()
 
# adding elements
llist.append('fourth')
llist.append('fifth')
llist.insert(3, 'sixth')
print(llist)
print()
 
llist.remove('second')
print(llist)
print()

Producción:

[‘primera segunda tercera’]

[‘primero’, ‘segundo’, ‘tercero’, ‘sexto’, ‘cuarto’, ‘quinto’]

[‘primero’, ‘tercero’, ‘sexto’, ‘cuarto’, ‘quinto’]

Pila

Una pila es una estructura lineal que permite que los datos se inserten y eliminen desde el mismo extremo, por lo que sigue un sistema de último en entrar, primero en salir (LIFO). La inserción y la eliminación se conocen como push() y pop() respectivamente.

Programa:

stack = ['first', 'second', 'third']
print(stack)
 
print()
 
# pushing elements
stack.append('fourth')
stack.append('fifth')
print(stack)
print()
 
# printing top
n = len(stack)
print(stack[n-1])
print()
 
# poping element
stack.pop()
print(stack)

Producción:

[‘primera segunda tercera’]

[‘primero Segundo Tercero Cuarto Quinto’]

quinto

[‘primero Segundo Tercero Cuarto’]

Cola

Una cola es una estructura lineal que permite la inserción de elementos desde un extremo y la eliminación desde el otro. Así se sigue, la metodología First In First Out (FIFO). El extremo que permite la eliminación se conoce como el frente de la cola y el otro extremo se conoce como el extremo posterior de la cola. 

Programa:

queue = ['first', 'second', 'third']
print(queue)
 
print()
 
# pushing elements
queue.append('fourth')
queue.append('fifth')
print(queue)
print()
 
# printing head
print(queue[0])
 
# printing tail
n = len(queue)
print(queue[n-1])
print()
 
# poping element
queue.remove(queue[0])
print(queue)

Producción:

[‘primera segunda tercera’]

[‘primero Segundo Tercero Cuarto Quinto’]

primero

quinto

[‘segundo’, ‘tercero’, ‘cuarto’, ‘quinto’]

Árbol

Un árbol es una estructura de datos no lineal pero jerárquica. El elemento superior se conoce como la raíz del árbol, ya que se cree que el árbol comienza desde la raíz. Los elementos al final del árbol se conocen como sus hojas. Los árboles son apropiados para almacenar datos que no están conectados linealmente entre sí, sino que forman una jerarquía. 

Programa:

class node:
    def __init__(self, ele):
        self.ele = ele
        self.left = None
        self.right = None
 
 
def preorder(self):
    if self:
        print(self.ele)
        preorder(self.left)
        preorder(self.right)
 
 
n = node('first')
n.left = node('second')
n.right = node('third')
preorder(n)

Producción:

primero

segundo

tercera

Grafico

Un gráfico es una estructura de datos no lineal que consta de Nodes y bordes. Los Nodes a veces también se conocen como vértices y los bordes son líneas o arcos que conectan dos Nodes en el gráfico. Un gráfico consta de un conjunto finito de vértices (o Nodes) y un conjunto de bordes que conectan un par de Nodes.

Programa:

class adjnode:
    def __init__(self, val):
        self.val = val
        self.next = None
 
 
class graph:
    def __init__(self, vertices):
        self.v = vertices
        self.ele = [None]*self.v
 
    def edge(self, src, dest):
        node = adjnode(dest)
        node.next = self.ele[src]
        self.ele[src] = node
 
        node = adjnode(src)
        node.next = self.ele[dest]
        self.ele[dest] = node
 
    def __repr__(self):
        for i in range(self.v):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.ele[i]
            while temp:
                print(" -> {}".format(temp.val), end="")
                temp = temp.next
 
 
g = graph(4)
g.edge(0, 2)
g.edge(1, 3)
g.edge(3, 2)
g.edge(0, 3)
g.__repr__()

Producción:

Lista de adyacencia del vértice 0

cabeza -> 3 -> 2

Lista de adyacencia del vértice 1

cabeza -> 3

Lista de adyacencia del vértice 2

cabeza -> 3 -> 0

Lista de adyacencia del vértice 3

cabeza -> 0 -> 2 -> 1

mapa hash

función hash

def printdict(d):
    for key in d:
        print(key, "->", d[key])
 
 
hm = {0: 'first', 1: 'second', 2: 'third'}
printdict(hm)
print()
 
hm[3] = 'fourth'
printdict(hm)
print()
 
hm.popitem()
printdict(hm)

Producción:

0 -> primero

1 -> segundo

2 -> tercero

0 -> primero

1 -> segundo

2 -> tercero

3 -> cuarto

0 -> primero

1 -> segundo

2 -> tercero