Datu struktūrām ir galvenā loma programmēšanas pasaulē. Tie palīdz mums sakārtot mūsu datus tā, lai tos varētu efektīvi izmantot.
Šajā apmācībā mēs uzzināsim par atsevišķi saistīto sarakstu un divkārši saistīto sarakstu.
Saistītais saraksts ir lineāra datu struktūra. Tas neuzglabā datus blakus esošās atmiņas vietās, piemēram, masīvos. Un katrs saistītais elements tiek saukts par mezglu, un tie ir savienoti, izmantojot rādītājus. Pirmais mezgls saistītajā sarakstā tiek saukts par galvu.
Saistītā saraksta lielums ir dinamisks. Tātad mums var būt jebkurš mezglu skaits, cik vien vēlamies, ja vien ierīcē nav pieejama krātuve.
Ir divu veidu saistītie saraksti. Apskatīsim detalizētu pamācību par tiem pa vienam.
#1. Atsevišķi saistītais saraksts
Atsevišķi saistītajā sarakstā ir viens rādītājs, kas savienots ar nākamo saistītā saraksta mezglu. Mums ir jāsaglabā dati un rādītājs katram mezglam saistītajā sarakstā.
Saistītā saraksta pēdējais mezgls satur nulli kā nākamo rādītāju, kas attēlo saistītā saraksta beigas.
Tālāk ir norādīta saite ilustrācija.
Tagad mums ir pilnīga izpratne par atsevišķi saistīto sarakstu. Apskatīsim darbības, lai to ieviestu Python.
Atsevišķi saistīto sarakstu ieviešana
1. Pirmais solis ir izveidot saistītā saraksta mezglu.
Kā to izveidot?
Python mēs varam viegli izveidot mezglu, izmantojot klasi. Klase satur datus un rādītāju nākamajam mezglam.
Apskatiet mezgla kodu.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Mēs varam izveidot mezglu ar jebkura veida datiem, izmantojot iepriekš minēto klasi. Pēc brīža redzēsim.
Tagad mezgls ir ar mums. Tālāk mums ir jāizveido saistīts saraksts ar vairākiem mezgliem. Izveidosim citu klasi saistītajam sarakstam.
2. Izveidojiet klasi ar nosaukumu LinkedList ar inicializētu nosaukumu Nav. Skatiet zemāk esošo kodu.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Mums ir Node un LinkedList klases. Kā saistītajā sarakstā ievietot jaunu mezglu? Vienkārša atbilde varētu būt LinkedList klases metodes izmantošana. Jā, tas būtu jauki. Ierakstīsim metodi, kā saistītajā sarakstā ievietot jaunu mezglu.
Lai saistītajā sarakstā ievietotu jaunu mezglu, mums ir jāveic noteiktas darbības.
Apskatīsim viņus.
- Pārbaudiet, vai galva ir tukša.
- Ja galva ir tukša, piešķiriet galvai jauno mezglu.
- Ja galva nav tukša, iegūstiet saistītā saraksta pēdējo mezglu.
- Piešķiriet jauno mezglu pēdējam mezgla nākamajam rādītājam.
Apskatīsim kodu jauna mezgla ievietošanai saistītajā sarakstā.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
Urā! esam pabeiguši metodi, lai saistītajā sarakstā ievietotu jaunu mezglu. Kā mēs varam piekļūt mezglu datiem no saistītā saraksta?
Lai piekļūtu datiem no saistītā saraksta, mums ir jāatkārto saistītais, izmantojot nākamo rādītāju, kā mēs to darām, lai iegūtu ievietošanas metodes pēdējo mezglu. Ierakstīsim metodi LinkedList klasē visu mezglu datu drukāšanai saistītajā sarakstā.
4. Izpildiet tālāk norādītās darbības, lai izdrukātu visus saistīto sarakstā esošo mezglu datus.
- Inicializējiet mainīgo ar galvu.
- Uzrakstiet cilpu, kas atkārtojas, līdz sasniedzam saistītā saraksta beigas.
- Drukājiet mezgla datus.
- Pārvietojiet nākamo rādītāju
Apskatīsim kodu.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
Fu! mēs pabeidzām izveidot saistīto ar nepieciešamajām metodēm. Pārbaudīsim saistīto sarakstu, izveidojot to ar dažiem datiem.
Mēs varam izveidot mezglu ar Node (1) kodu. Apskatīsim visu saistītā saraksta ieviešanas kodu kopā ar lietojuma paraugu.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## printing the linked list
linked_list.display()
Palaidiet iepriekš minēto programmu, lai iegūtu šādu rezultātu.
1->2->3->4->5->6->7->Null
Tas ir viss saistītajam sarakstam. Tagad jūs zināt, kā ieviest atsevišķi saistītu sarakstu. Jūs varat viegli ieviest dubultsaiti, zinot atsevišķi saistīto sarakstu. Iedziļināsimies nākamajā apmācības sadaļā.
#2. Divkārši saistīts saraksts
Dubultsaistītajā sarakstā ir divi norādes, kas savienotas ar iepriekšējo mezglu un nākamo mezglu saistītajā sarakstā. Mums ir jāsaglabā dati un divi norādes katram mezglam saistītajā sarakstā.
Pirmā mezgla iepriekšējais rādītājs ir nulle un nākamais pēdējā mezgla rādītājs ir nulle, lai attēlotu saistītā saraksta beigas abās pusēs.
Tālāk ir norādīta saite ilustrācija.
Divkārši saistītajam sarakstam ir arī līdzīgas darbības kā atsevišķi saistītajam sarakstam ieviešanā. Atkal skaidrot tās pašas lietas jums būs garlaicīgi. Izejiet cauri kodam katrā darbībā, un jūs to ļoti ātri sapratīsit. Ejam.
Divkārši saistītu sarakstu ieviešana
1. Izveidojiet mezglu dubultsaistam sarakstam ar iepriekšējā mezgla rādītāju, datiem un nākamā mezgla rādītāju.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Divkārši saistīta saraksta klase.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Metode jauna mezgla ievietošanai dubultsaites sarakstā.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Metode, lai parādītu divkāršās saites sarakstu datus.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Mēs esam redzējuši dubultsaites saraksta kodu. Un nav koda dubultsaites sarakstu klases izmantošanai. Tas ir priekš jums. Izmantojiet divkāršās saites sarakstu klasi, kas ir līdzīga atsevišķi saistītajam sarakstam. Izklaidējies 🙂
Secinājums
Pamatojoties uz saistītajiem sarakstiem, varat atrast daudzas problēmas. Bet jums ir jāzina šajā apmācībā apgūtās saistītās programmas pamata ieviešana. Cerams, ka jūs lieliski pavadījāt laiku, apgūstot jauno koncepciju.
Laimīgu kodēšanu 🙂