Complexité temporelle de l'enlèvement de l'élément de liste à double liaison?

Beaucoup de ce que je suis en train de lire, dit que la suppression d'un élément interne dans une liste doublement chaînée (DLL) est O(1); mais pourquoi est-ce le cas?

Je comprends pourquoi il est O(n) pour SLLs; la traversée de la liste O(n) et supprimer O(1) mais n'avez-vous pas toujours nécessaire de parcourir la liste dans une DLL pour trouver l'élément?

source d'informationauteur Matuku

  1. 14

    Pour une liste doublement chaînée, c'est la constante de temps de supprimer un élément une fois que vous savez où il est.

    Pour une seule liste liée, c'est la constante de temps de supprimer un élément une fois que vous savez où il et son prédécesseur.

    Depuis ce lien, vous pointez sur montre une seule liste liée de suppression O(n) et un doublement liés les uns que O(1)il est certain qu'une fois que vous savez déjà où l'élément que vous souhaitez supprimer, mais pas autre chose.

    Dans ce cas, pour une liste doublement chaînée, vous pouvez simplement utiliser le prev et next pointeurs de le retirer, vous donnant O(1). Ignorant le cas où vous êtes à la tête ou la queue, cela signifie quelque chose comme:

    corpse->prev->next = corpse->next
corpse->next->prev = corpse->prev
free (corpse)

    Cependant, dans une seule liste liée, où vous ne connaissez que le nœud que vous souhaitez supprimer, vous ne pouvez pas utiliser corpse->prev afin d'obtenir un précédent parce qu'il n'y est pas prev lien.

    Vous avez de la place trouver à l'article précédent, en parcourant la liste de la tête, à la recherche de celui qui a un next de l'élément que vous souhaitez supprimer. Qui va prendre O(n)après lequel il est une fois de plus O(1) pour la suppression effective de l', tels que (encore une fois, en ignorant les cas de bord pour des raisons de simplicité):

    lefty = head
while lefty->next != corpse:
    lefty = lefty-> next
lefty->next = corpse->next
free (corpse)

    C'est pourquoi les deux problèmes sont différents dans cet article.

  2. 3

    Comme il l'a déclaré à laquelle le lien pointe vers:

    Le coût de la modification d'un élément interne est basé sur déjà un pointeur, si vous avez besoin de trouver l'élément premier, le coût de la récupération de l'élément est également pris.

    Donc, pour les deux DLL et SLL la recherche linéaire est O(n), et la suppression via le pointeur est en O(1).

  3. 2

    La complexité de la sortie en DLL est O(1).
    Il peut également être O(1) dans SLL si le pointeur à l'élément précédent et de ne pas l'élément lui-même.

    Cette complexité est en supposant que vous savez où l'élément est.

    I. e. la signature d'opération est semblable à remove_element(list* l, link* e)
    La recherche de l'élément est O(n) dans les deux cas.

  4. 1

    @Matuku: Vous avez raison.

    Je humblement en désaccord avec la plupart de réponses ici, en essayant de justifier comment supprimer l'opération de la DLL est O(1). Il n'est pas.

    Laissez-moi vous expliquer.

    Pourquoi sommes-nous considérer le scénario que nous 'aurait le pointeur vers le nœud est supprimé? LinkedLists (Individuellement/Doublement) sont parcourus de façon linéaire, c'est leur définition. Ils ont des pointeurs seulement à la tête/queue. Comment pouvons-nous tout d'un coup avoir un pointeur vers certains nœud entre les deux? Cela va à l'encontre de l'objectif de cette structure de données. Et d'après cette hypothèse, si j'ai une DLL liste de 1 million de nœuds, alors dois-je également maintenir 1 million de pointeurs (appelons-les accès aux pointeurs) pointant vers chacun de ces nœuds pour que je puisse les supprimer en O(1)? Alors, comment aurais-je stocker ces 1 millions d'accès pointeurs? Et comment puis-je savoir qui de l'accès d'un pointeur sur les données correctes/nœud que je veux supprimer?

    Peut-on avoir un exemple concret où nous "avons" le pointeur vers les données qui doivent être supprimés 100% du temps?

    Et si vous connaissez l'emplacement exact/pointeur/référence de/vers le nœud à supprimer, pourquoi à même d'utiliser une LinkedList? Suffit d'utiliser la matrice de! C'est ce que les tableaux sont pour - un accès direct à ce que vous voulez!

    En supposant que vous avez un accès direct à n'importe quel nœud que vous voulez dans la DLL est aller à l'encontre de l'idée de la LinkedList conceptuel de Données de la Structure. Je suis d'accord avec l'OP, il est correct. Je m'en tiendrai à ce sujet - Doublement LinkedLists ne peut pas ont O(1) pour la suppression d'un nœud. Vous avez encore besoin de démarrer à partir de la tête ou de la queue, ce qui le met en bas à O(n).

    " Si " nous avons le pointeur vers le nœud supprimé dire X, alors bien sûr, c'est O(1) car nous avons des pointeurs vers la next et prev nœud, nous pouvons supprimer X. Mais que les gros s'est imaginaire, et non pas réel.

    Nous ne pouvons pas jouer avec la définition du sacré-Structure de Données appelée LinkedLists pour certains bizarre hypothèses que nous pouvons avoir de temps à autre.