Complexité temporelle d'un ADT Stack implémenté à l'aide d'une liste liée

Question

Quelle est la complexité temporelle des fonctions put (x) et get() pour un type de données abstrait Stack implémenté à l'aide d'une LinkedList?

Ma première pensée était qu'ils sont tous deux O (1). Mais si get() doit passer du noeud head au dernier élément de la liste pour trouver celui à supprimer et retourner, la fonction get() sera O (n).

La fonction put (x) doit également traverser toute la liste pour trouver le dernier nœud, où elle va installer un nouveau nœud. Donc, cela aussi serait O (n).

Si une version "spécialisée" d'une LinkedList était utilisée, une qui gardait toujours un pointeur vers le dernier nœud de la liste, celles-ci deviendraient toutes les deux des opérations à temps constant. Ai-je raison de comprendre qu'une mise en œuvre standard d'une LinkedList ne serait pas disponible?

Answer 1

Vous n'avez pas besoin d'insérer à la fin de la liste. Si vous insérez au début d'une liste (unidirectionnelle), ils sont tous les deux O(1).

Stack contient 1,2,3:

[1]->[2]->[3] 

poussoir 5:

[5]->[1]->[2]->[3] 

Pop:

[1]->[2]->[3], returning 5 

Answer 2

Pour une liste doublement liée aux opérations de la pile et pousser la pop devrait les deux sont O (1). Si vous êtes bloqué avec une liste à lien unique, en supposant que vous soyez autorisé à conserver un pointeur sur la queue ainsi que sur la tête, vous pouvez avoir les opérations de file d'attente O (1) de file d'attente et de file d'attente. Et parce qu'avec un surcoût constant amorti, vous pouvez faire une pile sur deux files d'attente, à la fin, vous pouvez obtenir O (1) pousser et sauter.