Comment mettre en œuvre une double liste chaînée avec un seul pointeur?

Il prend O(1) le temps de trouver le précédent et suivant Nœud.

struct Node
{
   int val;
   Node* p;
};

Limiter la liste à un maximum de deux nœuds 😛
Liste doublement chaînée? Tu veux dire que l'on doit être capable de traverser les deux méthodes pour avoir un externe pointeur de aucun de ses nœuds?
Ce problème intéressant paru dans le livre "Programmation Perl" (colonne) 9 ainsi. Alors que XOR solution de base est souvent proposé (peut-être parce que, au cours de ces époque, l'arithmétique des pointeurs était très commun), j'ai trouvé une solution donnée ci-dessous par "Anna" fait qu'il est extrêmement intéressant, surtout lorsque l'arithmétique des pointeurs n'est pas viable.

OriginalL'auteur MainID | 2009-11-18

algorithm data-structures

13

Cela sonne comme si c'est impossible, la façon dont c'est dit. Vous ne pouvez pas mettre en œuvre deux pointeurs à l'aide de seulement un, en général.

Vous pourriez être en mesure de serrer deux de 16 bits décalages dans l'espace utilisé par la seule (pris en charge 32 bits) pointeur ou d'une autre "piratage intelligent", mais en général, cela semble impossible.

Cet article décrit une astuce basée sur XOR:ing les valeurs de pointeur, mais je considère qu'un hack (il n'bit à bit de l'arithmétique sur les valeurs de pointeur).

Le 'XOR' astuce est à peu près la seule façon de le faire que je suis au courant. Il a certaines utilisations légitimes si le système que vous travaillez sur est limitée par la mémoire assez que l'économie d'un pointeur par nœud est la valeur de l'effort. Permet de déboguer le code liste intéressant.
Étant donné que c'est une question d'entrevue, pas un problème en pratique, je suis sur à 99% sûr que c'est prévu comme une connaissance générale de la question. L'intervieweur veut savoir si la personne interrogée connaît le XOR truc.

OriginalL'auteur unwind
10

Il y est un classique hack: stocker le XOR de l'2 pointeurs (Précédent et Suivant) et lorsque vous voyagez la liste vous avez toujours 1 de ceux à portée de main (vous venez de là) et vous pouvez XOR avec la valeur stockée à obtenir de l'autre pointeur.

Inutile de dire que cela ne fonctionnera pas dans un GC de l'environnement.

OriginalL'auteur Henk Holterman
9

Peut-être l'aide d'un XOR liste liée?

OriginalL'auteur Konamiman
6

Une solution qui a déjà été suggéré est le XOR solution.

Une autre solution est le "retournement côtés" solution:
Si votre problème est formulée de la manière suivante:

Vous êtes donné un pointeur vers le premier élément, et vous souhaitez:
1. Aller de l'avant dans la liste, je suit en O(i)
2. Revenir en arrière dans la liste, je suit en O(i)
3. Ajouter ou supprimer des éléments à l'emplacement actuel en O(1)
De sorte qu'il est toujours un seul pointeur de la liste chaînée, et il y a un seul point d'entrée (juste à aller en arrière et en avant, comme dans le 1 et 2), vous pouvez effectuer les opérations suivantes:
- Enregistrer deux pointeurs: p1, p2
- À partir de la première pointeur p1 vous pouvez revenir en arrière, à partir de la deuxième pointeur p2 vous aller de l'avant.
- La liste des éléments qui sont avant p1 point en arrière, tandis que les éléments après p2 point de l'avant.
De sorte que votre liste devrait ressembler à ceci:
```
                  p1 p2
                  |  |
                  V  V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7
```
p1 points à l'élément courant, p2 points à l'élément suivant, i1 ... i7 sont les éléments de la liste

Aller de l'avant est fait en O(1), et est donc aller vers l'arrière, par un retournement des pointeurs:
```
Forward one step:
                        p1 p2
                        |  |
                        V  V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7


Backward one step: 
            p1 p2
            |  |
            V  V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7
```
Cette solution est meilleure que la XOR dans sa lisibilité et qu'il est plus compréhensible pour les humains. L'inconvénient est que vous ne pouvez pas avoir plusieurs points d'entrée à votre liste liée.

OriginalL'auteur Anna
1

Si sizeof(int) == sizeof(Node *) alors un intermédiaire nœud qui contient un pointeur de retour.

E. g.

(real node) -> (intermediate node) -> (read node) -> (etc)

où (real node) contient une valeur et un pointeur vers le suivant (intermediate node), et (intermediate node) contient en val un pointeur de retour à la précédente intermédiaire nœud et p un pointeur vers l'avant à la suite de (read node).

BTW, c'est stupide, stupide question. Je ne vois pas ce qu'il enseigne quoi que ce soit de valeur.

OriginalL'auteur
1

Je suis récemment tombé sur une belle approche de ce problème dans un livre par Niklaus Wirth ("Algorithmes + Structures de Données = Programmes"). Il va comme ceci... Vous avez un nœud, similaire à celui que vous avez suggéré, sauf qu'il ne regroupe pas un pointeur vers la prochaine (ni à la précédente) Node. Au lieu de cela, vous avez un seul membre link qui représente la distance (par exemple, dans les unités de sizeof(Node)) à partir du nœud précédent (souligné par Node* pPrev) dans la chaîne vers le nœud suivant (souligné par Node* pNext) dans la chaîne:
```
size_t link = pNext - pPrev;
```
De sorte que le nœud pourrait ressembler à quelque chose comme ceci:
```
struct Node {
    int val;
    size_t link;
}
```
Puis, à compter de la présente nœud, pCurrent, combinée avec la précédente nœud pPrev, à la prochaine Node* pNext par écrit:
```
pNext = pPrev + pCurrent->link;
```
De même, vous pouvez parcourir dans le sens opposé par la réorganisation de cette équation:
```
pPrev = pNext - pCurrent->link;
```
Cependant, cette approche est quelque peu limitée par C/C++ de l'arithmétique des pointeurs parce que la différence de deux pointeurs n'est bien définie que si les deux point à l'intérieur d'un même bloc de mémoire. Donc, essentiellement, tous vos nœuds doivent être contenus à l'intérieur d'un large éventail de Nodes.

OriginalL'auteur Julian

Vous devez vous connecter pour publier un commentaire.