Κυκλική συνδεδεμένη λίστα: Πλεονεκτήματα και μειονεκτήματα

Τι είναι μια κυκλική συνδεδεμένη λίστα;

Μια κυκλική συνδεδεμένη λίστα είναι μια ακολουθία κόμβων διατεταγμένων έτσι ώστε κάθε κόμβος να μπορεί να αναδιαμορφωθεί.tracστον εαυτό του. Κάθε «κόμβος» είναι ένα αυτοαναφορικό στοιχείο με δείκτες σε έναν ή δύο κόμβους στην άμεση γειτνίαση του.

Παρακάτω είναι μια απεικόνιση μιας κυκλικής συνδεδεμένης λίστας με 3 κόμβους.

Εδώ, μπορείτε να δείτε ότι κάθε κόμβος επαναλαμβάνεταιtracεφικτό στον εαυτό του. Το παράδειγμα που φαίνεται παραπάνω είναι μια κυκλική λίστα με μία μόνο σύνδεση.

Σημείωση: Η απλούστερη κυκλική συνδεδεμένη λίστα είναι ένας μόνο κόμβος του οποίου ο επόμενος δείκτης tracεπιστρέφει στον εαυτό του, όπως φαίνεται παρακάτω.

Βασικο Operaσεις σε Κυκλικές Συνδεδεμένες Λίστες

Οι τρεις βασικές λειτουργίες σε μια κυκλική συνδεδεμένη λίστα είναι:

1. Εισαγωγή
2. Διαγραφή και
3. Διασχίζοντας

• Η εισαγωγή είναι η διαδικασία τοποθέτησης ενός κόμβου σε μια καθορισμένη θέση στην κυκλική συνδεδεμένη λίστα.
• Η διαγραφή είναι η διαδικασία αφαίρεσης ενός υπάρχοντος κόμβου από τη συνδεδεμένη λίστα. Ο κόμβος μπορεί να αναγνωριστεί από την εμφάνιση της τιμής του ή από τη θέση του.
• Η διέλευση μιας κυκλικής συνδεδεμένης λίστας είναι η διαδικασία εμφάνισης ολόκληρου του περιεχομένου της συνδεδεμένης λίστας και η επανεξέτασή του.tracεπιστρέφοντας στον κόμβο πηγής.

Η επόμενη ενότητα εξηγεί πώς λειτουργεί η εισαγωγή και τους δύο τύπους εισαγωγής που είναι δυνατοί σε μια κυκλική λίστα με μία μόνο σύνδεση.

Εισαγωγή Operaσμού

Αρχικά δημιουργείτε έναν κόμβο του οποίου ο επόμενος δείκτης δείχνει πίσω στον εαυτό του, όπως φαίνεται παρακάτω. Χωρίς αυτόν τον κόμβο εκκίνησης, η πρώτη εισαγωγή γίνεται ο πρώτος κόμβος στη λίστα.

Στη συνέχεια, υπάρχουν δύο πιθανότητες:

• Εισαγωγή στην τρέχουσα θέση της κυκλικής συνδεδεμένης λίστας. Αυτό αντιστοιχεί στην εισαγωγή είτε στην αρχή είτε στο τέλος μιας κανονικής μονά συνδεδεμένης λίστας — σε μια κυκλική συνδεδεμένη λίστα, η αρχή και το τέλος είναι το ίδιο σημείο.
• Εισαγωγή μετά από κόμβο με ευρετήριο. Ο κόμβος πρέπει να αναγνωρίζεται από έναν αριθμό ευρετηρίου που αντιστοιχεί στην τιμή του στοιχείου του.

Για να εισαγάγετε στην αρχή ή στο τέλος της κυκλικής συνδεδεμένης λίστας — δηλαδή, στη θέση όπου προστέθηκε ο πρώτος κόμβος — ακολουθήστε τα παρακάτω βήματα:

• Θα πρέπει να διακόψετε την υπάρχουσα αυτοσύνδεση με τον υπάρχοντα κόμβο
• Ο επόμενος δείκτης του νέου κόμβου θα συνδεθεί με τον υπάρχοντα κόμβο.
• Ο επόμενος δείκτης του τελευταίου κόμβου θα δείχνει προς τον κόμβο που έχει εισαχθεί.

ΣΗΜΕΙΩΣΗ: Ο δείκτης που σηματοδοτεί την αρχή ή το τέλος του κύκλου μπορεί να αντιστοιχιστεί εκ νέου σε οποιονδήποτε κόμβο. Μια διέλευση θα επιστρέψει στον ίδιο κόμβο, όπως θα συζητηθεί αργότερα σε αυτό το άρθρο.

Τα βήματα στο (α) i-iii φαίνονται παρακάτω:

(Υπάρχοντας κόμβος)

Βήμα 1) Σπάστε τον υπάρχοντα σύνδεσμο

Βήμα 2) Δημιουργήστε έναν σύνδεσμο προς τα εμπρός (από νέο κόμβο σε υπάρχοντα κόμβο)

Βήμα 3) Δημιουργήστε έναν σύνδεσμο βρόχου στον πρώτο κόμβο

Στη συνέχεια, θα δοκιμάσετε την εισαγωγή μετά από έναν κόμβο.

Για παράδειγμα, εισαγάγετε το "VALUE2" μετά τον κόμβο που περιέχει το "VALUE0", υποθέτοντας ότι το σημείο εκκίνησης είναι ο κόμβος με το "VALUE0".

• Διακόψτε τη σύνδεση μεταξύ του πρώτου και του δεύτερου κόμβου και τοποθετήστε τον κόμβο με την ένδειξη "VALUE2" ανάμεσά τους.
• Ο επόμενος δείκτης του πρώτου κόμβου συνδέεται με τον νέο κόμβο και ο επόμενος δείκτης του νέου κόμβου συνδέεται με αυτό που προηγουμένως ήταν ο δεύτερος κόμβος.
• Η υπόλοιπη διάταξη παραμένει αμετάβλητη. Όλοι οι κόμβοι επαναπροσδιορίζονται.tracικανοί για τους ίδιους.

ΣΗΜΕΙΩΣΗ: Επειδή η διάταξη είναι κυκλική, η διαδικασία εισαγωγής ενός κόμβου είναι ίδια ανεξάρτητα από τη θέση που επιλέγετε. Ο δείκτης που κλείνει τον κύκλο συμπεριφέρεται όπως οποιοσδήποτε άλλος δείκτης στη λίστα.

Αυτό φαίνεται παρακάτω:

(Ας πούμε ότι υπάρχουν μόνο δύο κόμβοι. Αυτή είναι μια ασήμαντη περίπτωση)

Βήμα 1) Αφαιρέστε τον εσωτερικό σύνδεσμο μεταξύ των συνδεδεμένων κόμβων

Βήμα 2) Συνδέστε τον κόμβο της αριστερής πλευράς στον νέο κόμβο

Βήμα 3) Συνδέστε τον νέο κόμβο στον κόμβο της δεξιάς πλευράς.

διαγραφή Operaσμού

Ας υποθέσουμε μια κυκλική συνδεδεμένη λίστα 3 κόμβων. Οι δύο περιπτώσεις διαγραφής είναι:

• Διαγραφή του τρέχοντος στοιχείου
• Διαγραφή μετά από ένα στοιχείο.

Διαγραφή στην αρχή/τέλος:

1. Περάστε στον πρώτο κόμβο από τον τελευταίο κόμβο.
2. Η διαγραφή από το τέλος απαιτεί μόνο ένα βήμα διάσχισης, από τον τελευταίο κόμβο στον πρώτο κόμβο.
3. Διαγράψτε τη σύνδεση μεταξύ του τελευταίου κόμβου και του πρώτου κόμβου.
4. Συνδέστε τον τελευταίο κόμβο με το επόμενο στοιχείο του πρώτου κόμβου.
5. Ελευθερώστε τον πρώτο κόμβο.

(Υπάρχουσα ρύθμιση)

Βήμα 1) Αφαιρέστε τον κυκλικό σύνδεσμο

Βήμα 2) Αφαιρέστε τη σύνδεση μεταξύ του πρώτου και του επόμενου, συνδέστε τον τελευταίο κόμβο στον κόμβο που ακολουθεί τον πρώτο

Βήμα 3) Ελευθερώστε / καταργήστε την κατανομή του πρώτου κόμβου

Διαγραφή μετά από κόμβο:

1. Διασχίστε μέχρι ο επόμενος κόμβος να είναι ο κόμβος που θα διαγραφεί.
2. Μεταβείτε στον επόμενο κόμβο, τοποθετώντας έναν δείκτη στον προηγούμενο κόμβο.
3. Συνδέστε τον προηγούμενο κόμβο στον κόμβο μετά τον παρόντα κόμβο, χρησιμοποιώντας τον επόμενο δείκτη του.
4. Ελευθερώστε τον τρέχοντα (αποσυνδεδεμένο) κόμβο.

Βήμα 1) Ας πούμε ότι πρέπει να διαγράψουμε έναν κόμβο με "VALUE1".

Βήμα 2) Αφαιρέστε τη σύνδεση μεταξύ του προηγούμενου κόμβου και του τρέχοντος κόμβου και, στη συνέχεια, συνδέστε τον προηγούμενο κόμβο απευθείας με τον κόμβο που υποδεικνύεται από τον επόμενο δείκτη του τρέχοντος κόμβου (τον κόμβο μετά την τιμή VALUE1).

Βήμα 3) Ελευθερώστε ή κατανείμετε τον τρέχοντα κόμβο.

Διέλευση μιας κυκλικής συνδεδεμένης λίστας

Για να διασχίσετε μια κυκλική συνδεδεμένη λίστα από έναν τελευταίο δείκτη, ελέγξτε πρώτα αν ο τελευταίος δείκτης είναι NULL. Εάν δεν είναι NULL, ελέγξτε αν η λίστα έχει μόνο ένα στοιχείο. Διαφορετικά, περπατήστε στη λίστα με έναν προσωρινό δείκτη μέχρι να φτάσετε ξανά στον τελευταίο δείκτη, όπως φαίνεται στην παρακάτω κινούμενη εικόνα.

Πλεονεκτήματα της κυκλικής συνδεδεμένης λίστας

Μερικά από τα πλεονεκτήματα των κυκλικών συνδεδεμένων λιστών είναι:

1. Δεν απαιτείται ανάθεση NULL στον κωδικό. Η κυκλική λίστα δεν οδηγεί ποτέ σε έναν δείκτη NULL, εκτός και αν κατανεμηθεί πλήρως.
2. Οι κυκλικά συνδεδεμένες λίστες είναι πλεονεκτικές για λειτουργίες τέλους λίστας επειδή η αρχή και το τέλος συμπίπτουν. Algorithms Όπως ο χρονοπρογραμματισμός round-robin, μπορεί να κινείται καθαρά μέσα από διεργασίες σε ουρά, χωρίς να συναντά αιωρούμενους ή NULL δείκτες.
3. Μια κυκλική συνδεδεμένη λίστα εξακολουθεί να υποστηρίζει όλες τις κανονικές λειτουργίες μιας απλά συνδεδεμένης λίστας. Μια κυκλική διπλά συνδεδεμένη λίστα μπορεί ακόμη και να εξαλείψει την ανάγκη για πλήρη διάσχιση για τον εντοπισμό ενός στοιχείου — στη χειρότερη περίπτωση, ο στόχος βρίσκεται απέναντι από τον δείκτη έναρξης, επομένως χρειάζεται να διανυθεί το πολύ η μισή λίστα.

Μειονεκτήματα της κυκλικής συνδεδεμένης λίστας

Τα μειονεκτήματα της χρήσης μιας κυκλικής συνδεδεμένης λίστας είναι τα παρακάτω:

1. Οι κυκλικές λίστες είναι πιο περίπλοκες από μεμονωμένα συνδεδεμένες λίστες.
2. RevΗ δημιουργία μιας κυκλικής λίστας είναι πιο περίπλοκη από την αντιστροφή μιας μονά ή διπλά συνδεδεμένης λίστας.
3. Εάν ο τερματισμός του βρόχου δεν αντιμετωπιστεί προσεκτικά, ο κώδικας διέλευσης μπορεί να εισέλθει σε έναν άπειρο βρόχο.
4. Είναι πιο δύσκολο να βρεθεί το τέλος της λίστας και να γραφτούν οι σωστές συνθήκες ελέγχου βρόχου.
5. Η εισαγωγή στην αρχή απαιτεί τη διέλευση ολόκληρης της λίστας για να φτάσουμε στον τελευταίο κόμβο (από την άποψη της υλοποίησης).

Λίστα μεμονωμένα συνδεδεμένα ως κυκλική συνδεδεμένη λίστα

Σας ενθαρρύνουμε να διαβάσετε και να εφαρμόσετε τον παρακάτω κώδικα C. Απεικονίζει την αριθμητική δεικτών που σχετίζεται με μια κυκλική λίστα με μία μόνο σύνδεση.

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Επεξήγηση κωδικού:

1. Οι δύο πρώτες γραμμές κώδικα είναι τα απαραίτητα αρχεία κεφαλίδας που περιλαμβάνονται.
2. Η επόμενη ενότητα ορίζει τη δομή κάθε αυτοαναφορικού κόμβου. Περιέχει μια τιμή και έναν δείκτη του ίδιου τύπου με τη δομή.
3. Κάθε στιγμιότυπο δομής συνδέεται με άλλα αντικείμενα δομής του ίδιου τύπου.
4. Υπάρχουν διαφορετικά πρωτότυπα λειτουργιών για:
   1. Προσθήκη στοιχείου σε μια κενή συνδεδεμένη λίστα
   2. Εισαγωγή στο επί του παρόντος μυτερό θέση μιας κυκλικής συνδεδεμένης λίστας.
   3. Εισαγωγή μετά από ένα συγκεκριμένο ευρετήριο τιμή στη συνδεδεμένη λίστα.
   4. Αφαίρεση/Διαγραφή μετά από ένα συγκεκριμένο ευρετήριο τιμή στη συνδεδεμένη λίστα.
   5. Αφαίρεση στην τρέχουσα αιχμηρή θέση μιας κυκλικής συνδεδεμένης λίστας
5. Η τελευταία συνάρτηση εκτυπώνει κάθε στοιχείο μέσω μιας κυκλικής διέλευσης σε οποιαδήποτε κατάσταση της συνδεδεμένης λίστας.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

Επεξήγηση κωδικού:

1. Για τον κώδικα addToEmpty, εκχωρήστε έναν κενό κόμβο χρησιμοποιώντας τη συνάρτηση malloc().
2. Τοποθετήστε τα εισερχόμενα δεδομένα στον προσωρινό κόμβο.
3. Αντιστοιχίστε τον προσωρινό κόμβο στην τελευταία θέση και ορίστε τον επόμενο δείκτη του στον εαυτό του, έτσι ώστε ο μεμονωμένος κόμβος να δείχνει πίσω στον εαυτό του.
4. Επιστρέψτε τον τελευταίο δείκτη πίσω στο περιβάλλον main() / application.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Επεξήγηση κώδικα

1. Εάν η λίστα είναι κενή, παραδώστε την στην addToEmpty() και επιστρέψτε τον έλεγχο.
2. Δημιουργήστε έναν προσωρινό κόμβο για να τοποθετήσετε μετά τον τρέχοντα κόμβο.
3. Συνδέστε τους δείκτες όπως φαίνεται στο παραπάνω διάγραμμα.
4. Επιστρέφει τον τελευταίο δείκτη, που ταιριάζει με το μοτίβο που χρησιμοποιήθηκε στην προηγούμενη συνάρτηση.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Επεξήγηση κωδικού:

1. Εάν η λίστα είναι κενή, αγνοήστε το κλειδί αναζήτησης, προσθέστε το τρέχον στοιχείο ως τον μόνο κόμβο στη λίστα και επιστρέψτε τον έλεγχο.
2. Σε κάθε επανάληψη του βρόχου do-while, ένας προηγούμενος δείκτης περιέχει το αποτέλεσμα που διανύθηκε τελευταία φορά.
3. Μόνο τότε πραγματοποιείται το επόμενο βήμα διέλευσης.
4. Η συνάρτηση do-while τερματίζεται όταν βρεθούν τα δεδομένα-στόχοι ή όταν το temp φτάσει ξανά στον τελευταίο δείκτη. Το ακόλουθο μπλοκ κώδικα αποφασίζει τι θα γίνει με το εντοπισμένο στοιχείο.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Επεξήγηση κωδικού:

1. Εάν έχει διαβαστεί ολόκληρη η λίστα αλλά το στοιχείο δεν βρεθεί, εμφανίζεται το μήνυμα "Το στοιχείο δεν βρέθηκε" και επιστρέφεται ο έλεγχος στον καλούντα.
2. Εάν βρεθεί ο κόμβος-στόχος, εκχωρήστε έναν νέο κόμβο για την τιμή που θα εισαχθεί.
3. Σύνδεσμος τον προηγούμενο κόμβο με τον νέο κόμβο και συνδέστε τον επόμενο δείκτη του νέου κόμβου με την τιμή temp (τη μεταβλητή διέλευσης).
4. Αυτό τοποθετεί το νέο στοιχείο αμέσως μετά τον κόμβο-στόχο στην κυκλική συνδεδεμένη λίστα. Στη συνέχεια, ο έλεγχος επιστρέφει στον καλούντα.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Επεξήγηση κώδικα

1. Για να αφαιρέσετε τον τελευταίο (τρέχοντα) κόμβο, ελέγξτε πρώτα αν η λίστα είναι κενή. Εάν είναι, δεν μπορεί να αφαιρεθεί κανένα στοιχείο.
2. Η μεταβλητή temp προωθεί έναν σύνδεσμο προς τα εμπρός.
3. Συνδέστε τον τελευταίο δείκτη με τον κόμβο που ακολουθεί τον πρώτο κόμβο.
4. Απελευθερώστε τον προσωρινό δείκτη για να καταργήσετε την κατανομή του μη συνδεδεμένου κόμβου.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Επεξήγηση κώδικα

1. Όπως και με την προηγούμενη συνάρτηση αφαίρεσης, ελέγξτε πρώτα αν η λίστα είναι κενή. Εάν είναι, δεν μπορεί να αφαιρεθεί κανένα στοιχείο.
2. Δύο δείκτες εκχωρούνται συγκεκριμένες θέσεις για τον εντοπισμό του στοιχείου που θα διαγραφεί.
3. Οι δείκτες προωθούνται ο ένας πίσω από τον άλλον (προηγούμενη θερμοκρασία μονοπατιών).
4. Η διέλευση συνεχίζεται μέχρι να βρεθεί το στοιχείο-στόχος ή ο επόμενος δείκτης να φτάσει ξανά στον τελευταίο κόμβο.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Επεξήγηση προγράμματος

1. Εάν διασχιστεί ολόκληρη η συνδεδεμένη λίστα χωρίς να βρεθεί ο στόχος, εμφανίζεται το μήνυμα "Δεν βρέθηκε στοιχείο".
2. Διαφορετικά, το στοιχείο αποσυνδέεται και απελευθερώνεται στα βήματα 3 και 4.
3. Ο προηγούμενος δείκτης συνδέεται με τον κόμβο στον οποίο υποδεικνύεται ο επόμενος δείκτης του temp (ο κόμβος μετά από αυτόν που διαγράφεται).
4. Στη συνέχεια, ο δείκτης θερμοκρασίας απελευθερώνεται.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Επεξήγηση κώδικα

1. Η διέλευση από το peek δεν είναι δυνατή εάν δεν υπάρχουν μηδενικοί κόμβοι — ο χρήστης πρέπει πρώτα να εκχωρήσει ή να εισάγει έναν κόμβο.
2. Εάν υπάρχει μόνο ένας κόμβος, δεν απαιτείται διάσχιση — το περιεχόμενο του κόμβου εκτυπώνεται απευθείας και ο βρόχος while δεν εκτελείται.
3. Εάν υπάρχουν περισσότεροι από ένας κόμβοι, η εντολή temp εκτυπώνει κάθε στοιχείο μέχρι το τελευταίο στοιχείο.
4. Τη στιγμή που προσεγγίζεται το τελευταίο στοιχείο, ο βρόχος τερματίζεται και η συνάρτηση επιστρέφει τον έλεγχο στην main().

Εφαρμογές της Κυκλικής Συνδεδεμένης Λίστας

• Εφαρμογή κυκλικού προγραμματισμού σε διαδικασίες συστήματος και κυκλικού προγραμματισμού σε γραφικά υψηλής ταχύτητας.
• Χρονοπρογραμματισμός Token-ring σε δίκτυα υπολογιστών.
• Χρησιμοποιείται σε μονάδες προβολής όπως ψηφιακοί πίνακες καταστημάτων που απαιτούν συνεχή διακίνηση δεδομένων.

Συχνές Ερωτήσεις