Σε αυτό το σεμινάριο, θα μάθετε για τη δομή δεδομένων συνδεδεμένης λίστας και την εφαρμογή της σε Python, Java, C και C ++.
Μια δομή δεδομένων συνδεδεμένης λίστας περιλαμβάνει μια σειρά συνδεδεμένων κόμβων. Εδώ, κάθε κόμβος αποθηκεύει τα δεδομένα και τη διεύθυνση του επόμενου κόμβου. Για παράδειγμα,
Δομή δεδομένων LinkedList
Πρέπει να ξεκινήσετε κάπου, οπότε δίνουμε στη διεύθυνση του πρώτου κόμβου ένα ειδικό όνομα που ονομάζεται HEAD.
Επίσης, ο τελευταίος κόμβος στη συνδεδεμένη λίστα μπορεί να αναγνωριστεί επειδή το επόμενο τμήμα του δείχνει NULL.
Μπορεί να έχετε παίξει το παιχνίδι Treasure Hunt, όπου κάθε ένδειξη περιλαμβάνει τις πληροφορίες σχετικά με την επόμενη ένδειξη. Έτσι λειτουργεί η συνδεδεμένη λίστα.
Αναπαράσταση του LinkedList
Ας δούμε πώς αντιπροσωπεύεται κάθε κόμβος του LinkedList. Κάθε κόμβος αποτελείται από:
- Ένα στοιχείο δεδομένων
- Μια διεύθυνση άλλου κόμβου
Περιτυλίγουμε τόσο το στοιχείο δεδομένων όσο και την επόμενη αναφορά κόμβου σε δομή ως:
struct node ( int data; struct node *next; );
Η κατανόηση της δομής ενός συνδεδεμένου κόμβου λίστας είναι το κλειδί για την κατανόησή του.
Κάθε κόμβος δομής έχει ένα στοιχείο δεδομένων και ένα δείκτη σε έναν άλλο κόμβο δομής. Ας δημιουργήσουμε μια απλή συνδεδεμένη λίστα με τρία στοιχεία για να κατανοήσουμε πώς λειτουργεί.
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Εάν δεν καταλάβατε καμία από τις παραπάνω γραμμές, το μόνο που χρειάζεστε είναι μια ανανέωση σε δείκτες και δομές.
Σε λίγα μόνο βήματα, δημιουργήσαμε μια απλή συνδεδεμένη λίστα με τρεις κόμβους.
Παράσταση LinkedList
Η δύναμη του LinkedList προέρχεται από την ικανότητα να σπάσει την αλυσίδα και να επανενωθεί. Π.χ. εάν θέλετε να βάλετε ένα στοιχείο 4 μεταξύ 1 και 2, τα βήματα θα ήταν:
- Δημιουργήστε έναν νέο κόμβο δομής και εκχωρήστε μνήμη σε αυτόν.
- Προσθέστε την τιμή δεδομένων ως 4
- Στρέψτε τον επόμενο δείκτη του στον κόμβο δομής που περιέχει 2 ως τιμή δεδομένων
- Αλλάξτε τον επόμενο δείκτη του "1" στον κόμβο που μόλις δημιουργήσαμε.
Κάνοντας κάτι παρόμοιο σε έναν πίνακα θα απαιτούσε αλλαγή των θέσεων όλων των επόμενων στοιχείων.
Σε python και Java, η συνδεδεμένη λίστα μπορεί να εφαρμοστεί χρησιμοποιώντας τάξεις όπως φαίνεται στους παρακάτω κωδικούς.
Βοηθητικό πρόγραμμα συνδεδεμένης λίστας
Οι λίστες είναι μια από τις πιο δημοφιλείς και αποτελεσματικές δομές δεδομένων, με εφαρμογή σε κάθε γλώσσα προγραμματισμού όπως C, C ++, Python, Java και C #.
Εκτός από αυτό, οι συνδεδεμένες λίστες είναι ένας πολύ καλός τρόπος για να μάθετε πώς λειτουργούν οι δείκτες. Με την εξάσκηση στον τρόπο χειρισμού συνδεδεμένων λιστών, μπορείτε να προετοιμαστείτε για να μάθετε πιο προηγμένες δομές δεδομένων, όπως γραφήματα και δέντρα.
Εφαρμογές συνδεδεμένης λίστας σε παραδείγματα Python, Java, C και C ++
Python Java C C + # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next
// Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
// Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
// Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )
Πολυπλοκότητα συνδεδεμένης λίστας
Χρόνος πολυπλοκότητας
| Χειρότερη περίπτωση | Μέση περίπτωση | |
|---|---|---|
| Αναζήτηση | Επί) | Επί) |
| Εισάγετε | Ο (1) | Ο (1) |
| Διαγραφή | Ο (1) | Ο (1) |
Διαστημική πολυπλοκότητα: O (n)
Εφαρμογές συνδεδεμένης λίστας
- Δυναμική κατανομή μνήμης
- Εφαρμόζεται σε στοίβα και ουρά
- Σε αναίρεση λειτουργικότητα των λογισμικών
- Hash πίνακες, γραφήματα
Προτεινόμενες αναγνώσεις
1. Μαθήματα
- Λειτουργίες LinkedList (Traverse, Insert, Delete)
- Τύποι LinkedList
- Java LinkedList
2. Παραδείγματα
- Αποκτήστε το μεσαίο στοιχείο του LinkedList σε μία μόνο επανάληψη
- Μετατρέψτε το LinkedList σε μια σειρά και αντίστροφα
- Εντοπισμός βρόχου σε LinkedList
