Python - Elenchi collegati

Un elenco collegato è una sequenza di elementi di dati, che sono collegati tra loro tramite collegamenti. Ogni elemento di dati contiene una connessione a un altro elemento di dati sotto forma di un puntatore. Python non ha elenchi collegati nella sua libreria standard. Implementiamo il concetto di liste concatenate usando il concetto di nodi come discusso nel capitolo precedente. Abbiamo già visto come creiamo una classe nodo e come attraversare gli elementi di un nodo. In questo capitolo studieremo i tipi di elenchi concatenati noti come elenchi concatenati singolarmente. In questo tipo di struttura dati esiste un solo collegamento tra due elementi dati. Creiamo tale elenco e creiamo metodi aggiuntivi per inserire, aggiornare e rimuovere elementi dall'elenco.

Creazione di un elenco collegato

Viene creato un elenco collegato utilizzando la classe dei nodi che abbiamo studiato nell'ultimo capitolo. Creiamo un oggetto Node e creiamo un'altra classe per utilizzare questo oggetto ode. Passiamo i valori appropriati attraverso l'oggetto nodo per puntare ai successivi elementi di dati. Il programma seguente crea l'elenco collegato con tre elementi di dati. Nella prossima sezione vedremo come attraversare la lista collegata.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Attraversare un elenco collegato

Gli elenchi collegati singolarmente possono essere attraversati solo in direzione forwrad a partire dal primo elemento di dati. Stampiamo semplicemente il valore del prossimo elemento dati assegnando il puntatore del nodo successivo all'elemento dati corrente.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Quando il codice precedente viene eseguito, produce il seguente risultato:

Mon
Tue
Wed

Inserimento in un elenco collegato

L'inserimento di un elemento nell'elenco collegato implica la riassegnazione dei puntatori dai nodi esistenti al nodo appena inserito. A seconda che il nuovo elemento di dati venga inserito all'inizio o al centro o alla fine dell'elenco collegato, abbiamo gli scenari seguenti.

Inserimento all'inizio dell'elenco collegato

Ciò implica il puntamento del puntatore successivo del nuovo nodo di dati all'inizio dell'elenco collegato. Quindi il capo corrente dell'elenco collegato diventa il secondo elemento di dati e il nuovo nodo diventa il capo dell'elenco collegato.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

Quando il codice precedente viene eseguito, produce il seguente risultato:

Sun
Mon
Tue
Wed

Inserimento alla fine dell'elenco collegato

Ciò implica puntare il puntatore successivo dell'ultimo nodo corrente dell'elenco collegato al nuovo nodo dati. Quindi l'ultimo nodo corrente dell'elenco collegato diventa il penultimo nodo di dati e il nuovo nodo diventa l'ultimo nodo dell'elenco collegato.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Quando il codice precedente viene eseguito, produce il seguente risultato:

Mon
Tue
Wed
Thu

Inserimento tra due nodi di dati

Ciò comporta lo chaging del puntatore di un nodo specifico per puntare al nuovo nodo. Ciò è possibile passando sia il nuovo nodo che il nodo esistente dopodiché verrà inserito il nuovo nodo. Quindi definiamo una classe aggiuntiva che cambierà il puntatore successivo del nuovo nodo al puntatore successivo del nodo centrale. Quindi assegna il nuovo nodo al puntatore successivo del nodo centrale.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Quando il codice precedente viene eseguito, produce il seguente risultato:

Mon
Tue
Fri
Thu

Rimozione di un elemento da un elenco di preferiti

Possiamo rimuovere un nodo esistente usando la chiave per quel nodo. Nel programma sottostante individuiamo il nodo precedente del nodo che deve essere cancellato. Quindi punta il puntatore successivo di questo nodo al nodo successivo del nodo da eliminare.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class SLinkedList:
    def __init__(self):
        self.head = None

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Quando il codice precedente viene eseguito, produce il seguente risultato:

Thu
Wed
Mon