Un vecteur est une chose tangible, mais la liste que vous envisagez est un nom pour un moyen de voir plusieurs choses vaguement liées mais distinctes.
Le vecteur est comme un carton d'oeufs — c'est une boîte avec un certain nombre fixe de fentes, dont chacun peut ou peut ne pas avoir une chose à l'intérieur de celui-ci. En revanche, ce que vous pensez d'une liste est plus comme prendre quelques chaussures individuelles et attacher leurs lacets ensemble. La "liste" est vraiment une vue d'un par la cellule qui contient une valeur — comme une fente dans le carton d'oeufs — et pointe vers une autre cellule, qui détient également une valeur et pointe vers une autre cellule, qui détient une valeur et ne pointe probablement à rien d'autre, ce qui en fait la fin de la liste. Ce que vous pensez d'une liste n'est pas vraiment une chose, mais plutôt une relation entre plusieurs cellules distinctes.
Vous avez raison de dire qu'il y a certaines opérations que vous pouvez effectuer sur les deux structures, mais leur complexité de temps est différente. Pour une liste, en poussant un élément sur le front ne modifie en fait rien à propos de la liste existante; au lieu de cela, cela signifie faire une nouvelle cellule par défaut pour représenter la nouvelle tête de la liste, et en pointant cette cellule contre à la liste existante comme la nouvelle queue. C'est une opération O (1); Peu importe la longueur de la liste, la mise en place d'une nouvelle cellule prend toujours le même temps. De même, apparaissant un élément au début de la liste ne change pas la liste existante; Cela signifie simplement déplacer votre vue d'une cellule par rapport à la tête actuelle pour voir quel était le deuxième élément en tant que nouvelle tête. Par contre, avec un vecteur, pousser un nouvel élément vers l'avant nécessite d'abord de déplacer tous les éléments existants d'un espace pour laisser un espace vide au début, en supposant qu'il y ait suffisamment d'espace dans le vecteur pour contenir tous les éléments existants articles et un de plus. Ce décalage a une complexité de temps O (n), ce qui signifie que plus il y a d'éléments dans le vecteur, plus il faut de temps pour les déplacer et faire de la place pour le nouvel élément. De même, le fait de sauter du front d'un vecteur nécessite de déplacer tous les éléments existants, mais le premier vers le bas, de sorte que le second devienne le premier, et le troisième devient le second, et ainsi de suite.Encore une fois, c'est la complexité du temps O (n).
Il est parfois possible de manipuler la comptabilité dans un vecteur de sorte que le fait de faire éclater un objet sur le devant ne nécessite pas de déplacer tous les éléments existants; Au lieu de cela, il suffit de changer l'enregistrement de l'élément qui compte en premier. Vous pouvez imaginer que cela comporte de nombreux défis: les index utilisés pour accéder aux éléments doivent être ajustés, la capacité du vecteur n'est plus simple à interpréter et la réallocation de l'espace pour le vecteur pour accueillir de nouveaux éléments doit maintenant considérer où laisser la nouvelle -un espace vide disponible après avoir copié les données existantes sur un nouveau stockage. Le "deque" structure répond à ces préoccupations. Choisir entre une liste et un vecteur nécessite de réfléchir à ce que vous voulez en faire et à ce que vous savez à l'avance sur la nature et la taille du contenu. Ils chantent chacun dans des scénarios différents, malgré le chevauchement apparent de leur but.
Au moment où je l'ai écrit la réponse ci-dessus, la question demandait de pousser et les éléments popping de la avant des deux un vecteur et une liste. Opérer sur le l'extrémité d'un vecteur comme vector-push et vector-pop est beaucoup plus semblable à manipuler la tête d'une liste que la distinction faite dans ma comparaison ci-dessus. Selon que la capacité du vecteur peut accueillir un autre élément sans réattribution, pousser et faire éclater les éléments à la fin d'un vecteur prend une durée constante (O (1)).
cela semble tout confus, dont Lisp parlez-vous? Dans Common Lisp, ni PUSH ni POP ne fonctionnent avec des vecteurs. –
@rainer commun lisp ... – wrongusername
@rainer oh darn je voulais dire vecteur-pousser-étendre, je vais mettre à jour la question – wrongusername