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

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

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

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

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

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

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

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

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

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

Στην επόμενη ενότητα, θα κατανοήσετε την εισαγωγή ενός κόμβου και τους τύπους εισαγωγής που είναι δυνατοί σε μια κυκλική μεμονωμένα συνδεδεμένη λίστα.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ΒΗΜΑ 3) Ελεύθερος /αποδιάθεση του πρώτου κόμβου

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

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

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

ΒΗΜΑ 2) Καταργήστε τη σύνδεση μεταξύ του προηγούμενου κόμβου και του τρέχοντος κόμβου. Συνδέστε τον προηγούμενο κόμβο του με τον επόμενο κόμβο που δείχνει ο τρέχων κόμβος (με VALUE1).

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

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

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

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

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

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

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

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

1. Οι κυκλικές λίστες είναι πολύπλοκες σε σύγκριση με μεμονωμένα συνδεδεμένες λίστες.
2. RevΤο erse of κυκλικής λίστας είναι πολύπλοκο σε σύγκριση με μεμονωμένες ή διπλές λίστες.
3. Εάν δεν χειριστείτε προσεκτικά, τότε ο κώδικας μπορεί να πάει σε έναν άπειρο βρόχο.
4. Πιο δύσκολο να βρεθεί το τέλος της λίστας και ο έλεγχος βρόχου.
5. Με την εισαγωγή στην Έναρξη, πρέπει να διασχίσουμε την πλήρη λίστα για να βρούμε τον τελευταίο κόμβο. (Προοπτική Υλοποίησης)

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

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

#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. Για τον κώδικα addEmpty, εκχωρήστε έναν κενό κόμβο χρησιμοποιώντας τη συνάρτηση malloc.
2. Για αυτόν τον κόμβο, τοποθετήστε τα δεδομένα στη μεταβλητή temp.
3. Εκχωρήστε και συνδέστε τη μοναδική μεταβλητή με τη μεταβλητή temp
4. Επιστρέψτε το τελευταίο στοιχείο στο main() / περιβάλλον εφαρμογής.

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. Εάν δεν υπάρχει στοιχείο για εισαγωγή, τότε θα πρέπει να φροντίσετε να προσθέσετε σε μια κενή λίστα και να επιστρέψετε το στοιχείο ελέγχου.
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 τερματίζεται. Το επόμενο τμήμα του κώδικα αποφασίζει τι πρέπει να γίνει με το αντικείμενο.

...
    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. Σύνδεσμος ο προηγούμενος κόμβος με τον νέο κόμβο. Συνδέστε τον τρέχοντα κόμβο με τη θερμοκρασία (τη μεταβλητή διέλευσης).
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. Η κρυφοκοιτασία ή η διέλευση δεν είναι δυνατή εάν απαιτούνται μηδενικά. Ο χρήστης πρέπει να εκχωρήσει ή να εισαγάγει έναν κόμβο.
2. Εάν υπάρχει μόνο ένας κόμβος, δεν υπάρχει ανάγκη διέλευσης, το περιεχόμενο του κόμβου μπορεί να εκτυπωθεί και ο βρόχος while δεν εκτελείται.
3. Εάν υπάρχουν περισσότεροι από ένας κόμβοι, τότε το temp εκτυπώνει όλο το στοιχείο μέχρι το τελευταίο στοιχείο.
4. Τη στιγμή που επιτυγχάνεται το τελευταίο στοιχείο, ο βρόχος τερματίζεται και η συνάρτηση επιστρέφει κλήση στην κύρια συνάρτηση.

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

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