I denne artikkelen vil vi lære om implementeringen av en koblet liste i Python . For å implementere den koblede listen i Python, vil vi bruke klasser i Python . Nå vet vi at en koblet liste består av noder og noder har to elementer, dvs. data og en referanse til en annen node. La oss implementere noden først.
Hva er Linked List i Python
En koblet liste er en type lineær datastruktur som ligner på matriser. Det er en samling av noder som er knyttet til hverandre. En node inneholder to ting, først er data, og for det andre er en kobling som forbinder den med en annen node. Nedenfor er et eksempel på en koblet liste med fire noder og hver node inneholder tegndata og en lenke til en annen node. Vår første node er hvor hode poeng, og vi kan få tilgang til alle elementene i den koblede listen ved å bruke hode.
Koblet liste
Opprette en koblet liste i Python
I denne LinkedList-klassen vil vi bruke Node-klassen til å lage en koblet liste. I denne klassen har vi en __varmt__ metode som initialiserer den koblede listen med et tomt hode. Deretter har vi laget en insertAtBegin() metode for å sette inn en node på begynnelsen av den koblede listen, en insertAtIndex() metode for å sette inn en node ved den gitte indeksen til den koblede listen, og insertAtEnd() metoden setter inn en node på slutten av den koblede listen. Etter det har vi remove_node() metode som tar dataene som et argument for å slette den noden. I remove_node() metode vi krysser den koblede listen hvis en node er tilstede lik data, så sletter vi den noden fra den koblede listen. Så har vi sizeOfLL() metode for å få gjeldende størrelse på den koblede listen og den siste metoden i LinkedList-klassen er printLL() som krysser den koblede listen og skriver ut dataene til hver node.
Opprette en nodeklasse
Vi har laget en Node-klasse der vi har definert en __varmt__ funksjon for å initialisere noden med dataene sendt som et argument og en referanse med Ingen fordi hvis vi bare har en node så er det ingenting i referansen.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Innsetting i lenket liste
Innsetting ved start i koblet liste
Denne metoden setter inn noden i begynnelsen av den koblede listen. I denne metoden lager vi en ny_node med det gitte data og sjekk om hodet er en tom node eller ikke hvis hodet er tomt så lager vi ny_node som hode og komme tilbake ellers setter vi inn hodet ved neste ny_node og lage hode lik ny_node.
Python3
mylivecricket
def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> |
>
>
Sett inn en node på en bestemt posisjon i en koblet liste
Denne metoden setter inn noden ved den gitte indeksen i den koblede listen. I denne metoden lager vi en ny_node med gitte data , en current_node som er lik hodet, og en teller 'posisjon' initialiseres med 0. Nå, hvis indeksen er lik null, betyr det at noden skal settes inn i begynnelsen, så vi kalte insertAtBegin()-metoden ellers kjører vi en stund løkke til gjeldende_node er ikke lik Ingen eller (posisjon+1) er ikke lik indeksen vi må på den ene posisjonen tilbake for å sette inn på en gitt posisjon for å gjøre koblingen av noder, og i hver iterasjon øker vi posisjonen med 1 og gjør gjeldende_node neste av det. Når sløyfen ryker og hvis gjeldende_node er ikke lik Ingen vi setter inn ny_node ved etter til gjeldende_node. Hvis gjeldende_node er lik Ingen det betyr at indeksen ikke er til stede i listen og vi skriver ut Indeks ikke til stede.
Python3
# Indexing starts from 0.> def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> |
>
>
Innsetting i lenket liste på slutten
Denne metoden setter inn noden på slutten av den koblede listen. I denne metoden lager vi en ny_node med de gitte dataene og sjekk om hode er en tom node eller ikke hvis hode er tom så lager vi ny_node som hode og komme tilbake ellers vi lager en gjeldende_node lik til hodet gå til det siste node av den koblede listen og når vi får Ingen etter current_node bryter while-løkken og sett inn ny_node i neste av gjeldende_node som er den siste noden i den koblede listen.
Python3
def> inserAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> |
>
>
Oppdater noden til en koblet liste
Denne koden definerer en metode kalt updateNode i en koblet listeklasse. Den brukes til å oppdatere verdien til en node på en gitt posisjon i den koblede listen.
Python3
# Update node of a linked list> # at given position> def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> |
>
>
Slett node i en koblet liste
Fjern første node fra koblet liste
Denne metoden fjerner den første noden av den koblede listen ganske enkelt ved å lage den andre noden hode av den tilknyttede listen.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
innkapslingsprogram
>
Fjern siste node fra koblet liste
I denne metoden vil vi slette den siste noden. Først går vi til den nest siste noden ved å bruke while-løkken, og deretter lager vi den neste av den noden Ingen og siste node vil bli fjernet.
Python3
def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> |
>
>
Slett en koblet listenode på en gitt posisjon
I denne metoden vil vi fjerne noden ved den gitte indeksen, denne metoden ligner på de insert_at_inded() metode. I denne metoden, hvis hode er Ingen vi rett og slett komme tilbake ellers initialiserer vi en gjeldende_node med selv.hode og posisjon med 0. Hvis posisjonen er lik indeksen kalte vi remove_first_node() metoden ellers går vi til den ene noden før som vi ønsker å fjerne ved å bruke while-løkken. Etter det når vi er ute av while-løkken sjekker vi den aktuelle_noden er lik Ingen hvis ikke, gjør vi den neste av gjeldende_node lik den neste av noden som vi ønsker å fjerne, ellers skriver vi ut meldingen Indeks ikke til stede fordi gjeldende_node er lik Ingen.
Python3
# Method to remove at given index> def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> |
>
>
Slett en koblet listenode for en gitt data
Denne metoden fjerner noden med de gitte dataene fra den koblede listen. I denne metoden laget vi først en gjeldende_node lik hode og løp en mens loop for å gå gjennom den koblede listen. Dette mens loop bryter når gjeldende_node blir Ingen eller dataene ved siden av gjeldende node er lik dataene gitt i argumentet. Nå, etter å ha kommet ut av loopen hvis gjeldende_node er lik Ingen det betyr at noden ikke er tilstede i dataene, og vi kommer bare tilbake, og hvis dataene ved siden av gjeldende_node er lik dataene som er gitt, fjerner vi den noden ved å gjøre neste av den fjernet_noden til den neste av gjeldende_node. Og dette implementeres ved å bruke if else-betingelsen.
Python3
def> remove_node(>self>, data):> >current_node>=> self>.head> ># Check if the head node contains the specified data> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while> current_node>is> not> None> and> current_node.>next>.data !>=> data:> >current_node>=> current_node.>next> >if> current_node>is> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> |
>
>
Linked List Traversal i Python
Denne metoden går gjennom den koblede listen og skriver ut dataene til hver node. I denne metoden laget vi en gjeldende_node lik hode og gjenta gjennom den koblede listen ved å bruke en mens loop til gjeldende_node bli Ingen og skriv ut dataene til gjeldende_node i hver iterasjon og gjør gjeldende_node ved siden av det.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Få lengden på en koblet liste i Python
Denne metoden returnerer størrelsen på den koblede listen. I denne metoden har vi initialisert en teller 'størrelse' med 0, og hvis hodet ikke er lik Ingen, krysser vi den koblede listen ved å bruke en mens loop og øke størrelse med 1 i hver iterasjon og returner størrelsen når gjeldende_node blir Ingen andre vi returnerer 0.
Python3
def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> |
>
>
Eksempel på den koblede listen i Python
I dette eksemplet, etter å ha definert klassen Node og LinkedList, har vi opprettet en koblet liste med navn lliste ved å bruke den koblede listeklassen og sett inn fire noder med tegndata 'a', 'b', 'c', 'd' og 'g' i den koblede listen så skriver vi ut den koblede listen ved hjelp av printLL() metodelenket listeklasse etter det har vi fjernet noen noder ved å bruke fjernmetoder og skriv deretter ut den koblede listen igjen, og vi kan se i utdataene at noden er slettet. Etter det skriver vi også ut størrelsen på den koblede listen.
Python3
string.replaceall i java
# Create a Node class to create a node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> # Create a LinkedList class> class> LinkedList:> >def> __init__(>self>):> >self>.head>=> None> ># Method to add a node at begin of LL> >def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> ># Method to add a node at any index> ># Indexing starts from 0.> >def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> ># Method to add a node at the end of LL> >def> insertAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> ># Update node of a linked list> ># at given position> >def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> ># Method to remove first node of linked list> >def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> >self>.head>=> self>.head.>next> ># Method to remove last node of linked list> >def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> ># Method to remove at given index> >def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> ># Method to remove a node from linked list> >def> remove_node(>self>, data):> >current_node>=> self>.head> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while>(current_node !>=> None> and> current_node.>next>.data !>=> data):> >current_node>=> current_node.>next> >if> current_node>=>=> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> ># Print the size of linked list> >def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> ># print method for the linked list> >def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> # create a new linked list> llist>=> LinkedList()> # add nodes to the linked list> llist.insertAtEnd(>'a'>)> llist.insertAtEnd(>'b'>)> llist.insertAtBegin(>'c'>)> llist.insertAtEnd(>'d'>)> llist.insertAtIndex(>'g'>,>2>)> # print the linked list> print>(>'Node Data'>)> llist.printLL()> # remove a nodes from the linked list> print>(>'
Remove First Node'>)> llist.remove_first_node()> print>(>'Remove Last Node'>)> llist.remove_last_node()> print>(>'Remove Node at Index 1'>)> llist.remove_at_index(>1>)> # print the linked list again> print>(>'
Linked list after removing a node:'>)> llist.printLL()> print>(>'
Update node Value'>)> llist.updateNode(>'z'>,>0>)> llist.printLL()> print>(>'
Size of linked list :'>, end>=>' '>)> print>(llist.sizeOfLL())> |
>
>Produksjon
Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2>