Οι δομές δεδομένων διαδραματίζουν βασικό ρόλο στον κόσμο του προγραμματισμού. Μας βοηθούν να οργανώσουμε τα δεδομένα μας με τρόπο που να μπορούν να χρησιμοποιηθούν αποτελεσματικά.
Σε αυτό το σεμινάριο, θα μάθουμε για τη λίστα μεμονωμένα και διπλά συνδεδεμένη λίστα.
Μια συνδεδεμένη λίστα είναι μια γραμμική δομή δεδομένων. Δεν αποθηκεύει τα δεδομένα σε συνεχόμενες θέσεις μνήμης όπως πίνακες. Και κάθε στοιχείο στο συνδεδεμένο ονομάζεται κόμβος και συνδέονται χρησιμοποιώντας τους δείκτες. Ο πρώτος κόμβος στη συνδεδεμένη λίστα ονομάζεται κεφαλή.
Το μέγεθος της συνδεδεμένης λίστας είναι δυναμικό. Έτσι, μπορούμε να έχουμε οποιονδήποτε αριθμό κόμβων θέλουμε, εκτός εάν ο αποθηκευτικός χώρος είναι διαθέσιμος στη συσκευή.
Υπάρχουν δύο τύποι συνδεδεμένων λιστών. Ας δούμε ένα προς ένα το αναλυτικό tutorial για αυτούς.
Πίνακας περιεχομένων
#1. Λίστα μεμονωμένα συνδεδεμένα
Μια μεμονωμένα συνδεδεμένη λίστα περιέχει έναν μόνο δείκτη που συνδέεται με τον επόμενο κόμβο στη συνδεδεμένη λίστα. Πρέπει να αποθηκεύσουμε τα δεδομένα και τον δείκτη για κάθε κόμβο στη συνδεδεμένη λίστα.
Ο τελευταίος κόμβος στη συνδεδεμένη λίστα περιέχει null ως τον επόμενο δείκτη που αντιπροσωπεύει το τέλος της συνδεδεμένης λίστας.
Μπορείτε να δείτε την εικόνα ενός συνδέσμου παρακάτω.
Τώρα, κατανοούμε πλήρως μια λίστα μεμονωμένα συνδεδεμένα. Ας δούμε τα βήματα για την εφαρμογή του στην Python.
Εφαρμογή λίστας μεμονωμένα συνδεδεμένα
1. Το πρώτο βήμα είναι να δημιουργήσετε τον κόμβο για τη συνδεδεμένη λίστα.
Πώς να το δημιουργήσετε;
Στην Python, μπορούμε εύκολα να δημιουργήσουμε τον κόμβο χρησιμοποιώντας την κλάση. Η κλάση περιέχει δεδομένα και έναν δείκτη για τον επόμενο κόμβο.
Κοιτάξτε τον κώδικα για τον κόμβο.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Μπορούμε να δημιουργήσουμε τον κόμβο με οποιοδήποτε τύπο δεδομένων χρησιμοποιώντας την παραπάνω κλάση. Θα το δούμε σε λίγο.
Τώρα, έχουμε τον κόμβο μαζί μας. Στη συνέχεια, πρέπει να δημιουργήσουμε μια συνδεδεμένη λίστα με πολλούς κόμβους. Ας δημιουργήσουμε μια άλλη τάξη για μια συνδεδεμένη λίστα.
2. Δημιουργήστε μια κλάση που ονομάζεται LinkedList με αρχικοποίηση της κεφαλής σε None. Δείτε τον κώδικα παρακάτω.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Έχουμε μαζί μας κλάσεις Node και LinkedList. Πώς εισάγουμε έναν νέο κόμβο στη συνδεδεμένη λίστα; Μια απλή απάντηση μπορεί να είναι η χρήση μιας μεθόδου στην κλάση LinkedList. Ναι, θα ήταν ωραίο. Ας γράψουμε μια μέθοδο για την εισαγωγή ενός νέου κόμβου στη συνδεδεμένη λίστα.
Για να εισαγάγουμε έναν νέο κόμβο στη συνδεδεμένη λίστα, πρέπει να ακολουθήσουμε ορισμένα βήματα.
Ας τους δούμε.
- Ελέγξτε εάν η κεφαλή είναι άδεια ή όχι.
- Εάν η κεφαλή είναι άδεια, τότε αντιστοιχίστε τον νέο κόμβο στην κεφαλή.
- Εάν η κεφαλή δεν είναι άδεια, λάβετε τον τελευταίο κόμβο της συνδεδεμένης λίστας.
- Αντιστοιχίστε τον νέο κόμβο στον τελευταίο κόμβο επόμενο δείκτη.
Ας δούμε τον κώδικα για την εισαγωγή ενός νέου κόμβου στη συνδεδεμένη λίστα.
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
Ούρα! ολοκληρώσαμε τη μέθοδο εισαγωγής νέου κόμβου στη συνδεδεμένη λίστα. Πώς μπορούμε να έχουμε πρόσβαση στα δεδομένα κόμβων από τη συνδεδεμένη λίστα;
Για να αποκτήσουμε πρόσβαση στα δεδομένα από τη συνδεδεμένη λίστα, πρέπει να επαναλάβουμε τη σύνδεση χρησιμοποιώντας τον επόμενο δείκτη όπως κάνουμε για να πάρουμε τον τελευταίο κόμβο στη μέθοδο εισαγωγής. Ας γράψουμε μια μέθοδο μέσα στην κλάση LinkedList για την εκτύπωση όλων των δεδομένων κόμβων στη συνδεδεμένη λίστα.
4. Ακολουθήστε τα παρακάτω βήματα για να εκτυπώσετε όλα τα δεδομένα κόμβων στη συνδεδεμένη λίστα.
- Αρχικοποιήστε μια μεταβλητή με κεφάλι.
- Γράψτε έναν βρόχο που να επαναλαμβάνεται μέχρι να φτάσουμε στο τέλος της συνδεδεμένης λίστας.
- Εκτυπώστε τα δεδομένα του κόμβου.
- Μετακινήστε τον επόμενο δείκτη
Ας δούμε τον κωδικό.
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')
Φτου! ολοκληρώσαμε τη δημιουργία του linked με τις απαραίτητες μεθόδους. Ας δοκιμάσουμε τη συνδεδεμένη λίστα δημιουργώντας την με κάποια δεδομένα.
Μπορούμε να δημιουργήσουμε τον κόμβο με τον κώδικα Node(1). Ας δούμε τον πλήρη κώδικα της εφαρμογής της συνδεδεμένης λίστας μαζί με το δείγμα χρήσης.
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()
Εκτελέστε το παραπάνω πρόγραμμα για να έχετε το ακόλουθο αποτέλεσμα.
1->2->3->4->5->6->7->Null
Αυτό είναι για τη συνδεδεμένη λίστα. Τώρα, ξέρετε πώς να εφαρμόσετε μια λίστα μεμονωμένα συνδεδεμένα. Μπορείτε εύκολα να εφαρμόσετε τη λίστα με διπλή σύνδεση με τη γνώση της λίστας μεμονωμένης σύνδεσης. Ας βουτήξουμε στην επόμενη ενότητα του σεμιναρίου.
#2. Λίστα διπλά συνδεδεμένη
Μια λίστα με διπλή σύνδεση περιέχει δύο δείκτες που συνδέονται με τον προηγούμενο κόμβο και τον επόμενο κόμβο στη συνδεδεμένη λίστα. Πρέπει να αποθηκεύσουμε τα δεδομένα και δύο δείκτες για κάθε κόμβο στη συνδεδεμένη λίστα.
Ο προηγούμενος δείκτης του πρώτου κόμβου είναι μηδενικός και ο επόμενος δείκτης του τελευταίου κόμβου είναι μηδενικός για να αντιπροσωπεύει το τέλος της συνδεδεμένης λίστας και στις δύο πλευρές.
Μπορείτε να δείτε την εικόνα ενός συνδέσμου παρακάτω.
Η διπλά συνδεδεμένη λίστα έχει επίσης παρόμοια βήματα με τη λίστα μονής σύνδεσης σε εφαρμογή. Και πάλι το να εξηγείς τα ίδια πράγματα θα είναι βαρετό για σένα. Περάστε τον κώδικα σε κάθε βήμα και θα τον καταλάβετε πολύ γρήγορα. Πάμε.
Υλοποίηση λίστας διπλής σύνδεσης
1. Δημιουργία κόμβου για τη διπλά συνδεδεμένη λίστα με τον προηγούμενο δείκτη κόμβου, δεδομένα και τον επόμενο δείκτη κόμβου.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Κλάση λίστας διπλής σύνδεσης.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Μια μέθοδος για την εισαγωγή ενός νέου κόμβου στη λίστα διπλής σύνδεσης.
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. Μια μέθοδος για την εμφάνιση των δεδομένων της λίστας διπλής σύνδεσης.
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()
Είδαμε τον κωδικό της λίστας με διπλή σύνδεση. Και δεν υπάρχει κώδικας για τη χρήση της κλάσης της λίστας διπλής σύνδεσης. Αυτό είναι για σένα. Χρησιμοποιήστε την κλάση λίστας διπλής σύνδεσης παρόμοια με τη λίστα με μονή σύνδεση. Καλή διασκέδαση 🙂
συμπέρασμα
Μπορείτε να βρείτε πολλά προβλήματα με βάση τις συνδεδεμένες λίστες. Ωστόσο, πρέπει να γνωρίζετε τη βασική εφαρμογή των συνδεδεμένων που έχετε μάθει σε αυτό το σεμινάριο. Ελπίζω να περάσατε υπέροχα μαθαίνοντας τη νέα ιδέα.
Καλή Κωδικοποίηση 🙂