Implémenter un algorithme pour insérer un nœud dans une liste chaînée circulaire sans le traverser

Question

Je pensais à une solution à ce problème.

Mon entrée:
1. Avoir un pointeur de queue qui pointe vers le dernier noeud.
2. Une fois que vous connaissez le dernier pointeur, vous pouvez facilement ajouter un nouveau nœud à côté de celui-ci.

Void Insert(Node N) 
{ 
    if (head == null) // linked list is empty 
    { 
     head = N; tail = N; tail.Next = head; 
    } 
    else 
    {   
     Node temp = tail.Next; // since this is circular tail will point to head 
     Tail.Next = N; 
     N.Next = temp; // correct 
     tail = N;  
    } 
} 

Peut-on envisager une meilleure solution sans utiliser de pointeur de queue? Aussi comme indiqué dans le problème sans traverser? Ceci est une question d'entrevue, juste besoin d'entrées pour trouver la meilleure solution.

Answer 1

Je suppose que vous avez une liste circulaire liée individuellement, et seulement un pointeur vers un élément (appelez ceci le nœud principal). Chaque noeud de la liste est donc constitué d'une valeur et d'un pointeur vers l'élément suivant. Le nœud de queue pointe vers le nœud de tête. L'insertion d'un nœud directement après le nœud principal est triviale. Je suppose que vous voulez insérer un nœud directement avant le nœud principal. Pour cela, vous avez besoin que le nouveau nœud devienne le dernier nœud, pointé sur l'ancien dernier nœud, et qui pointe vers le nœud principal. Maintenant, vous voulez éviter de parcourir la liste pour trouver le dernier nœud. Cela signifie que vous ne pouvez pas accéder à ce dernier nœud et ainsi, ne pas modifier son pointeur. La seule autre façon de faire ce travail est de modifier la place que le dernier point de nœud à, à savoir:

1. insérer un nouveau noeud après le nœud principal
2. copie la valeur de la tête en cours nœud à ce nouveau noeud
3. mettre la nouvelle valeur dans le nœud principal courant
4. faire le nouveau nœud du nouveau nœud principal

Answer 2

Non, vous avez besoin du pointeur de queue. Sinon, vous devrez parcourir la liste. Sinon, comment sauriez-vous où la liste se termine?

Vous pourriez trouver une sorte d'arithmétique d'indexation intelligente, mais ce serait toujours un pointeur vers la tête/queue.

Answer 3

vous avez également le nœud de tête. vous pouvez insérer en l'utilisant aussi. Je suppose qu'il n'y a aucune restriction sur où insérer le nouveau noeud (la question ne le spécifie pas explicitement).

L'insérer sur la tête est trivial.

Modifier Insérez après la tête

Answer 4

Si votre mesure de « mieux » est de ne pas maintenir à la fois la tête et des pointeurs de la queue, vous pouvez au lieu de maintenir le curseur de la queue. Le pointeur de tête est implicite (donné par tail.Next).

En pratique, l'accès à une liste est souvent assez courant (par exemple, si vous utilisez la liste circulaire en tant que file d'attente), et une étape supplémentaire pour accéder à la tête peut ajouter une surcharge. Dans un test pour un projet que j'ai fait, éliminer le pointeur de la tête de cette façon abaissait la mémoire (nos listes étaient généralement courtes, mais nous en avions beaucoup), mais le temps augmentait puisque nous accédions souvent à la tête de liste. YMMV.

Answer 5

J'ai simplifié votre code un peu. Pas besoin de la variable temp, vous ne l'avez même pas utilisé pour quelque chose après l'avoir défini.

Void Insert(Node N) { 
    if (head == null) { // linked list is empty 
     head = tail = N; 
    } 
    else { // insert after tail 
     tail.Next = N; 
     tail = N;  
    } 
    tail.Next = head; 
} 

Answer 6

Au lieu de stocker la tête et la queue, il suffit de ranger la queue.

Void Insert(Node N) 
{ 
    if (tail == null) // linked list is empty 
    { 
     tail = N.Next = N; 
    } 
    else 
    { 
     N.Next = tail.Next; 
     tail = tail.Next = N; 
    } 
} 
Node Head() { return tail == null ? null : tail.next; }