Šajā rakstā mēs uzzināsim par saistītā saraksta ieviešanu Python . Lai ieviestu saistīto sarakstu Python, mēs izmantosim nodarbības Python valodā . Tagad mēs zinām, ka saistītais saraksts sastāv no mezgliem, un mezgliem ir divi elementi, t.i., dati un atsauce uz citu mezglu. Vispirms ieviesīsim mezglu.
Kas ir saistītais saraksts Python
Saistīts saraksts ir lineāras datu struktūras veids, kas līdzīgs masīviem. Tā ir mezglu kolekcija, kas ir savstarpēji saistīti. Mezglā ir divas lietas, pirmkārt, dati un, otrkārt, saite, kas to savieno ar citu mezglu. Tālāk ir sniegts piemērs saistītam sarakstam ar četriem mezgliem, un katrs mezgls satur rakstzīmju datus un saiti uz citu mezglu. Mūsu pirmais mezgls ir kur galvu punktiem, un mēs varam piekļūt visiem saistītā saraksta elementiem, izmantojot galvu.
Saistītais saraksts
Saistītā saraksta izveide programmā Python
Šajā LinkedList klasē mēs izmantosim klasi Node, lai izveidotu saistīto sarakstu. Šajā klasē mums ir __karsts__ metode, kas inicializē saistīto sarakstu ar tukšu galvu. Tālāk mēs esam izveidojuši insertAtBegin() metode, lai ievietotu mezglu saistītā saraksta sākumā, an insertAtIndex() metode, lai ievietotu mezglu norādītajā saistītā saraksta rādītājā, un insertAtEnd() metode ievieto mezglu saistītā saraksta beigās. Pēc tam mums ir Remove_node() metode, kas izmanto datus kā argumentu šī mezgla dzēšanai. Iekš Remove_node() metode mēs šķērsojam saistīto sarakstu, ja mezgls ir vienāds ar datiem, tad mēs izdzēšam šo mezglu no saistītā saraksta. Tad mums ir izmērsOfLL() metode, lai iegūtu saistītā saraksta pašreizējo izmēru, un pēdējā LinkedList klases metode ir printLL() kas šķērso saistīto sarakstu un izdrukā katra mezgla datus.
Mezglu klases izveide
Mēs esam izveidojuši Node klasi, kurā esam definējuši a __karsts__ funkcija, lai inicializētu mezglu ar datiem, kas nodoti kā arguments un atsauce ar None, jo, ja mums ir tikai viens mezgls, tā atsaucē nav nekā.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Ievietošana saistītajā sarakstā
Ievietošana saistītā saraksta sākumā
Šī metode ievieto mezglu saistītā saraksta sākumā. Ar šo metodi mēs izveidojam a jauns_mezgls ar doto datus un pārbaudiet, vai galva ir tukšs mezgls vai nav, ja galva ir tukša, tad mēs izveidojam jauns_mezgls kā galvu un atgriezties citādi mēs ievietojam galvu nākamajā jauns_mezgls un izveidojiet galvu vienāds ar jauns_mezgls.
Python3
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> |
>
>
Ievietojiet mezglu noteiktā pozīcijā saistītajā sarakstā
Ar šo metodi saistītajā sarakstā tiek ievietots mezgls norādītajā indeksā. Ar šo metodi mēs izveidojam a jauns_mezgls ar dotajiem datiem , strāvas_mezgls, kas ir vienāds ar galvu, un skaitītājs 'pozīcija' inicializē ar 0. Tagad, ja indekss ir vienāds ar nulli, tas nozīmē, ka mezgls ir jāievieto sākumā, tāpēc mēs to saucām metodi insertAtBegin(). citādi mēs palaižam kamēr cilpa līdz pašreizējais_mezgls nav vienāds ar Nav vai (pozīcija+1) nav vienāds ar indeksu, kas mums ir jāievieto vienā pozīcijā atpakaļ, lai ievietotu noteiktā pozīcijā, lai izveidotu mezglu sasaisti, un katrā iterācijā mēs palielinām pozīciju par 1 un izveidojam pašreizējais_mezgls blakus tam. Kad cilpa pārtrūkst un ja pašreizējais_mezgls nav vienāds ar Nav mēs ievietojam new_node at after uz pašreizējais_mezgls. Ja pašreizējais_mezgls ir vienāds ar Nav tas nozīmē, ka indeksa sarakstā nav, un mēs drukājam Indekss nav pieejams.
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'>)> |
>
>
Ievietošana saistītajā sarakstā beigās
Šī metode ievieto mezglu saistītā saraksta beigās. Ar šo metodi mēs izveidojam a jauns_mezgls ar dotajiem datiem un pārbaudiet, vai galvu ir tukšs mezgls vai nav, ja galvu ir tukšs, tad mēs izgatavojam jauns_mezgls kā galvu un atgriezties cits mēs izgatavojam a pašreizējais_mezgls vienāds uz galva šķērsot līdz pēdējam mezgls no saistītā saraksta un kad mēs to saņemsim Nav pēc current_node cilpa while pārtraukumi un ievietojiet jauns_mezgls nākamajā no pašreizējais_mezgls kas ir saistītajā saraksta pēdējais mezgls.
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> |
>
>
Atjauniniet saistītā saraksta mezglu
Šis kods definē metodi, ko sauc par updateNode saistītā saraksta klasē. To izmanto, lai atjauninātu mezgla vērtību noteiktā pozīcijā saistītajā sarakstā.
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'>)> |
>
>
Dzēst mezglu saistītajā sarakstā
Noņemiet pirmo mezglu no saistīto saraksta
Šī metode noņem saistīto saraksta pirmo mezglu, vienkārši izveidojot otro mezglu galvu no saistītā saraksta.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
Noņemiet pēdējo mezglu no saistīto saraksta
Izmantojot šo metodi, mēs izdzēsīsim pēdējo mezglu. Pirmkārt, mēs pārejam uz otro pēdējo mezglu, izmantojot while cilpu, un pēc tam izveidojam nākamo no šī mezgla Nav un pēdējais mezgls tiks noņemts.
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> |
>
>
Dzēsiet saistītā saraksta mezglu noteiktā pozīcijā
Izmantojot šo metodi, mēs noņemsim mezglu dotajā indeksā, šī metode ir līdzīga uz insert_at_inded() metodi. Izmantojot šo metodi, ja galvu ir Nav mēs vienkārši atgriezties citādi mēs inicializējam a pašreizējais_mezgls ar sevi.galva un pozīciju ar 0. Ja pozīcija ir vienāda ar indeksu, ko mēs saucam par remove_first_node() cita metode mēs pārejam uz vienu mezglu, pirms kuru vēlamies noņemt, izmantojot while cilpu. Pēc tam, kad izejam no while cilpas, mēs pārbaudām ka pašreizējais_mezgls ir vienāds ar Nav ja nē, tad mēs padarām nākamo no pašreizējais_node vienādu ar nākamo mezglu, kuru vēlamies noņemt, pretējā gadījumā mēs izdrukājam ziņojumu Indekss nav pieejams jo pašreizējais_mezgls ir vienāds ar Nav.
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'>)> |
ja vēl java
>
>
Dzēst norādīto datu saistītā saraksta mezglu
Šī metode no saistītā saraksta noņem mezglu ar norādītajiem datiem. Izmantojot šo metodi, vispirms mēs izveidojām a pašreizējais_mezgls vienāds ar galvu un palaist a kamēr cilpa lai šķērsotu saistīto sarakstu. Šī kamēr cilpa pārtrūkst, kad pašreizējais_mezgls kļūst Nav vai dati blakus pašreizējam mezglam ir vienādi ar argumentā norādītajiem datiem. Tagad, pēc iznākšanas no cilpas, ja pašreizējais_mezgls ir vienāds ar Nav tas nozīmē, ka mezgls nav klāt datos, un mēs vienkārši atgriezīsimies, un, ja dati blakus pašreizējais_mezgls ir vienāds ar dotajiem datiem, tad mēs noņemam šo mezglu, pārveidojot nākamo no noņemtā_mezgla par nākamo no pašreizējā_mezgla. Un tas tiek īstenots, izmantojot nosacījumu if else.
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> |
>
>
Saistītā saraksta šķērsošana Python
Šī metode šķērso saistīto sarakstu un izdrukā katra mezgla datus. Ar šo metodi mēs izgatavojām a pašreizējais_mezgls vienāds ar galvu un atkārtojiet saistīto sarakstu, izmantojot a kamēr cilpa līdz pašreizējais_mezgls kļūstiet par Nav un izdrukājiet datus no pašreizējais_mezgls katrā iterācijā un izveidojiet pašreizējais_mezgls tai blakus.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Iegūstiet saistītā saraksta garumu programmā Python
Šī metode atgriež saistītā saraksta lielumu. Izmantojot šo metodi, mēs esam inicializējuši skaitītāju 'Izmērs' ar 0, un tad, ja galva nav vienāda ar Nav, mēs šķērsojam saistīto sarakstu, izmantojot a kamēr cilpa un palieliniet Izmērs ar 1 katrā iterācijā un atgriezt izmēru, kad pašreizējais_mezgls kļūst Neviens cits mēs atgriežam 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> |
>
>
Saistītā saraksta piemērs programmā Python
Šajā piemērā pēc Node un LinkedList klases definēšanas esam izveidojuši saistīto sarakstu ar nosaukumu saraksts izmantojot saistītā saraksta klasi un pēc tam ievietojiet četrus mezglus ar rakstzīmju datiem 'a', 'b', 'c', 'd' un 'g' saistītajā sarakstā, tad mēs izdrukājam saistīto sarakstu, izmantojot printLL() ar metodi saistītā saraksta klase pēc tam esam noņēmuši dažus mezglus, izmantojot noņemšanas metodes un pēc tam vēlreiz izdrukājiet saistīto sarakstu, un izvadā mēs varam redzēt, ka mezgls ir veiksmīgi izdzēsts. Pēc tam mēs arī izdrukājam saistītā saraksta izmēru.
Python3
# 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())> |
>
>Izvade
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>