Concept
Liste chaînée
Concepts associés (34)
File d'attente à double extrémité
In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque (see below). Deque is sometimes written dequeue, but this use is generally deprecated in technical literature or technical writing because dequeue is also a verb meaning "to remove from a queue".
S-expression
Une S-expression (ou expression symbolique) est une convention pour la représentation de données ou d'expressions d'un programme sous forme textuelle. Les S-expressions sont utilisées dans la famille de langages Lisp, incluant Scheme et , ainsi que comme métalangage dans des protocoles de communication tels IMAP ou le langage CBCL (Common Business Communication Language) de John McCarthy.
Fonction de hachage
Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.
Tas (informatique)
vignette|Un exemple de tas. Il contient 9 éléments. L'élément le plus prioritaire (100) est à la racine. En informatique, un tas (ou monceau au Canada, heap en anglais) est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. C'est un arbre binaire presque complet ordonné. Un arbre binaire est dit presque complet si tous ses niveaux sont remplis, sauf éventuellement le dernier, qui doit être rempli sur la gauche (cf. Contre-exemples).
Tri par tas
thumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort). En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier.
Arbre bicolore
Un arbre bicolore, ou arbre rouge-noir ou arbre rouge et noir est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir).
Structure de données persistante
En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée ; une telle structure est immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée.
CAR and CDR
In computer programming, CAR (car) kɑr and CDR (cdr) (ˈkʌdər or ˈkʊdər) are primitive operations on cons cells (or "non-atomic S-expressions") introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second. Thus, the expression (car (cons x y)) evaluates to x, and (cdr (cons x y)) evaluates to y.
Pseudo-code
En programmation, le pseudo-code, également appelé LDA (pour Langage de Description d'Algorithmes) est une façon de décrire un algorithme en langage presque naturel, sans référence à un langage de programmation en particulier. L'écriture en pseudo-code permet souvent de bien prendre toute la mesure de la difficulté de la mise en œuvre de l'algorithme, et de développer une démarche structurée dans la construction de celui-ci.
Memory pool
Memory pools, also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation. Dynamic memory allocation can, and has been achieved trough the use of techniques such as malloc and C++'s operator new; although established and reliable implementations, these suffer from fragmentation because of variable block sizes, it is not recommendable to use them in a real time system due to performance. A more efficient solution is preallocating a number of memory blocks with the same size called the memory pool.