data-structures
Liste liée
Recherche…
Introduction aux listes liées
Une liste chaînée est une collection linéaire d'éléments de données, appelés noeuds, qui sont liés à un autre noeud au moyen d'un "pointeur". Ci-dessous se trouve une liste à lien unique avec une référence de tête.
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴─────────┘ └─────────┴─────────┘
Il existe de nombreux types de listes liées, y compris des listes à liens simples et doubles et des listes à liens circulaires.
Avantages
Les listes liées sont une structure de données dynamique qui peut croître et diminuer, allouer et libérer de la mémoire pendant l'exécution du programme.
Les opérations d'insertion et de suppression de nœuds sont facilement implémentées dans une liste chaînée.
Les structures de données linéaires telles que les piles et les files d'attente sont facilement implémentées avec une liste chaînée.
Les listes liées peuvent réduire le temps d'accès et peuvent s'étendre en temps réel sans surcharge de mémoire.
Singly Linked List
Les listes liées individuellement sont un type de liste liée . Les nœuds d'une liste à lien unique n'ont qu'un seul "pointeur" vers un autre nœud, généralement "suivant". C'est ce qu'on appelle une liste à lien unique, car chaque nœud n'a qu'un seul "pointeur" vers un autre nœud. Une liste à lien unique peut avoir une référence de tête et / ou de queue. L'avantage d'avoir une référence de queue est les cas getFromBack , addToBack et removeFromBack , qui deviennent O (1).
┌─────────┬─────────┐ ┌─────────┬─────────┐
HEAD ──▶│ data │"pointer"│──▶│ data │"pointer"│──▶ null
└─────────┴────△────┘ └─────────┴─────────┘
SINGLE │
REFERENCE ────┘
Exemple de code en Java, avec des tests unitaires - liste à liens simples avec référence de tête
Liste liée XOR
Une liste liée à XOR est également appelée liste liée à la mémoire efficace . C'est une autre forme d'une liste doublement liée. Cela dépend fortement de la porte logique XOR et de ses propriétés.
Pourquoi est-ce ce qu'on appelle la liste liée à la mémoire efficace?
Cela s'appelle ainsi parce que cela utilise moins de mémoire qu'une liste doublement liée traditionnelle.
Est-ce différent d'une liste doublement liée?
Oui c'est ça
Une liste doublement liée stocke deux pointeurs, le point suivant et le nœud précédent. Fondamentalement, si vous voulez revenir en arrière, vous allez à l'adresse indiquée par le pointeur back . Si vous voulez avancer, vous allez à l'adresse indiquée par le next pointeur. C'est comme:
Une liste liée à la mémoire efficace , ou à savoir la liste liée XOR ne possède qu'un seul pointeur au lieu de deux. Cela stocke l'adresse précédente (addr (prev)) XOR (^) l'adresse suivante (addr (next)). Lorsque vous souhaitez passer au nœud suivant, vous effectuez certains calculs et recherchez l'adresse du nœud suivant. C'est la même chose pour aller au nœud précédent. C'est comme:
Comment ça marche?
Pour comprendre le fonctionnement de la liste chaînée, vous devez connaître les propriétés de XOR (^):
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
Laissons maintenant cela de côté et voyons ce que chaque nœud stocke.
Le premier nœud, ou la tête , stocke 0 ^ addr (next) car il n'y a pas de nœud ou d'adresse précédent. Ça ressemble à ça .
Ensuite, le deuxième nœud stocke addr (prev) ^ addr (next) . Ça ressemble à ça .
La queue de la liste n'a pas de nœud suivant, donc elle stocke addr (prev) ^ 0 . Ça ressemble à ça .
Passer de la tête au nœud suivant
Disons que vous êtes maintenant au premier nœud ou au nœud A. Maintenant, vous voulez vous déplacer au nœud B. Voici la formule pour le faire:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Donc ce serait:
addr (next) = addr (prev) ^ (0 ^ addr (next))
Comme il s'agit de la tête, l'adresse précédente serait simplement 0, donc:
addr (next) = 0 ^ (0 ^ addr (next))
Nous pouvons supprimer les parenthèses:
addr (next) = 0 ^ 0 addr (next)
En utilisant la propriété none (2) , on peut dire que 0 ^ 0 sera toujours 0:
addr (next) = 0 ^ addr (next)
En utilisant la propriété none (1) , nous pouvons le simplifier pour:
addr (next) = addr (next)
Vous avez l'adresse du nœud suivant!
Passer d'un noeud au noeud suivant
Maintenant, disons que nous sommes dans un nœud intermédiaire, qui a un nœud précédent et suivant.
Appliquons la formule:
Address of Next Node = Address of Previous Node ^ pointer in the current Node
Remplacez maintenant les valeurs:
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
Supprimer les parenthèses:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
En utilisant la propriété none (2) , nous pouvons simplifier:
addr (next) = 0 ^ addr (next)
En utilisant la propriété none (1) , nous pouvons simplifier:
addr (next) = addr (next)
Et vous l'obtenez!
Passer d'un nœud au nœud dans lequel vous étiez auparavant
Si vous ne comprenez pas le titre, cela signifie fondamentalement que si vous étiez au nœud X et que vous avez maintenant migré vers le nœud Y, vous voulez retourner au nœud visité précédemment, ou essentiellement au nœud X.
Ce n'est pas une tâche fastidieuse. Rappelez-vous que j'avais mentionné ci-dessus, que vous stockiez l'adresse dans laquelle vous étiez dans une variable temporaire. Donc, l'adresse du nœud que vous voulez visiter se trouve dans une variable:
addr (prev) = temp_addr
Passer d'un noeud au noeud précédent
Ce n'est pas la même que celle mentionnée ci-dessus. Je veux dire que vous étiez au nœud Z, maintenant vous êtes au nœud Y et que vous voulez aller au nœud X.
Cela revient presque au déplacement d'un nœud au nœud suivant. Juste que c'est le contraire. Lorsque vous écrivez un programme, vous utiliserez les mêmes étapes que celles mentionnées dans le déplacement d'un nœud vers le nœud suivant, mais vous trouvez simplement l'élément précédent dans la liste plutôt que de trouver l'élément suivant.
Exemple de code en C
/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
// Node structure of a memory efficient doubly linked list
struct node
{
int data;
struct node* npx; /* XOR of next and previous node */
};
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
/* Insert a node at the begining of the XORed linked list and makes the
newly inserted node as head */
void insert(struct node **head_ref, int data)
{
// Allocate memory for new node
struct node *new_node = (struct node *) malloc (sizeof (struct node) );
new_node->data = data;
/* Since new node is being inserted at the begining, npx of new node
will always be XOR of current head and NULL */
new_node->npx = XOR(*head_ref, NULL);
/* If linked list is not empty, then npx of current head node will be XOR
of new node and node next to current head */
if (*head_ref != NULL)
{
// *(head_ref)->npx is XOR of NULL and next. So if we do XOR of
// it with NULL, we get next
struct node* next = XOR((*head_ref)->npx, NULL);
(*head_ref)->npx = XOR(new_node, next);
}
// Change head
*head_ref = new_node;
}
// prints contents of doubly linked list in forward direction
void printList (struct node *head)
{
struct node *curr = head;
struct node *prev = NULL;
struct node *next;
printf ("Following are the nodes of Linked List: \n");
while (curr != NULL)
{
// print current node
printf ("%d ", curr->data);
// get address of next node: curr->npx is next^prev, so curr->npx^prev
// will be next^prev^prev which is next
next = XOR (prev, curr->npx);
// update prev and curr for next iteration
prev = curr;
curr = next;
}
}
// Driver program to test above functions
int main ()
{
/* Create following Doubly Linked List
head-->40<-->30<-->20<-->10 */
struct node *head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
// print the created list
printList (head);
return (0);
}
Le code ci-dessus remplit deux fonctions de base: insertion et transversale.
Insertion: Ceci est effectué par la fonction
insert. Cela insère un nouveau nœud au début. Lorsque cette fonction est appelée, elle place le nouveau nœud en tête et le nœud principal précédent en tant que second nœud.Traversal: Ceci est effectué par la fonction
printList. Il traverse simplement chaque nœud et imprime la valeur.
Notez que XOR des pointeurs n'est pas défini par la norme C / C ++. Ainsi, l'implémentation ci-dessus peut ne pas fonctionner sur toutes les plates-formes.
Les références
https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/
http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-2/
Notez que j'ai pris beaucoup de contenu de ma propre réponse sur le principal.
Ignorer la liste
Les listes de passage sont des listes liées qui vous permettent de passer directement au noeud approprié. C'est une méthode qui est beaucoup plus rapide qu'une liste à liens simples. Il s'agit fondamentalement d'une liste liée par un seul élément, mais les pointeurs ne vont pas d'un nœud au nœud suivant, mais sautent peu de nœuds. Ainsi, le nom "Skip List".
Est-ce différent d'une liste liée singulièrement?
Oui c'est ça
Une liste individuelle liée est une liste avec chaque nœud pointant vers le nœud suivant. Une représentation graphique d'une liste à lien unique ressemble à:
Une liste de saut est une liste avec chaque nœud pointant vers un nœud qui pourrait ou non le suivre. Une représentation graphique d'une liste de passage est la suivante:
Comment ça marche?
La liste de passage est simple. Disons que nous voulons accéder au nœud 3 dans l'image ci-dessus. Nous ne pouvons pas prendre la route pour aller de la tête au quatrième nœud, car c'est après le troisième nœud. Nous allons donc de la tête au deuxième nœud, puis au troisième.
Une représentation graphique est comme:
Les références
Doubly Linked List
Les listes doublement liées sont un type de liste liée . Les nœuds d'une liste doublement liée ont deux "pointeurs" vers les autres nœuds, "suivant" et "précédent". C'est ce qu'on appelle une liste à double lien parce que chaque nœud n'a que deux "pointeurs" pour les autres nœuds. Une liste à double lien peut avoir un pointeur de tête et / ou de queue.
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
Les listes à double lien sont moins efficaces que les listes à liens simples. cependant, pour certaines opérations, elles offrent des améliorations significatives en termes de gain de temps. Un exemple simple est la fonction get , qui pour une liste à double lien avec une référence de tête et de queue commencera à partir de la tête ou de la queue en fonction de l'index de l'élément à obtenir. Pour une liste à n éléments, pour obtenir l'élément indexé n/2 + i , une liste à liens simples avec des références tête / queue doit traverser n/2 + i nœuds, car elle ne peut pas "revenir" de queue. Une liste à double lien avec des références head / tail ne doit traverser que n/2 - i nœuds, car elle peut "revenir" en arrière, traversant la liste dans l'ordre inverse.
Un exemple simple de SinglyLinkedList en Java
Une implémentation de base de liste unique dans java - qui peut ajouter des valeurs entières à la fin de la liste, supprimer la première valeur rencontrée de la liste, renvoyer un tableau de valeurs à un instant donné et déterminer si une valeur donnée est présente dans la liste.
Node.java
package com.example.so.ds;
/**
* <p> Basic node implementation </p>
* @since 20161008
* @author Ravindra HV
* @version 0.1
*/
public class Node {
private Node next;
private int value;
public Node(int value) {
this.value=value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getValue() {
return value;
}
}
SinglyLinkedList.java
package com.example.so.ds;
/**
* <p> Basic single-linked-list implementation </p>
* @since 20161008
* @author Ravindra HV
* @version 0.2
*/
public class SinglyLinkedList {
private Node head;
private volatile int size;
public int getSize() {
return size;
}
public synchronized void append(int value) {
Node entry = new Node(value);
if(head == null) {
head=entry;
}
else {
Node temp=head;
while( temp.getNext() != null) {
temp=temp.getNext();
}
temp.setNext(entry);
}
size++;
}
public synchronized boolean removeFirst(int value) {
boolean result = false;
if( head == null ) { // or size is zero..
// no action
}
else if( head.getValue() == value ) {
head = head.getNext();
result = true;
}
else {
Node previous = head;
Node temp = head.getNext();
while( (temp != null) && (temp.getValue() != value) ) {
previous = temp;
temp = temp.getNext();
}
if((temp != null) && (temp.getValue() == value)) { // if temp is null then not found..
previous.setNext( temp.getNext() );
result = true;
}
}
if(result) {
size--;
}
return result;
}
public synchronized int[] snapshot() {
Node temp=head;
int[] result = new int[size];
for(int i=0;i<size;i++) {
result[i]=temp.getValue();
temp = temp.getNext();
}
return result;
}
public synchronized boolean contains(int value) {
boolean result = false;
Node temp = head;
while(temp!=null) {
if(temp.getValue() == value) {
result=true;
break;
}
temp=temp.getNext();
}
return result;
}
}
TestSinglyLinkedList.java
package com.example.so.ds;
import java.util.Arrays;
import java.util.Random;
/**
*
* <p> Test-case for single-linked list</p>
* @since 20161008
* @author Ravindra HV
* @version 0.2
*
*/
public class TestSinglyLinkedList {
/**
* @param args
*/
public static void main(String[] args) {
SinglyLinkedList singleLinkedList = new SinglyLinkedList();
int loop = 11;
Random random = new Random();
for(int i=0;i<loop;i++) {
int value = random.nextInt(loop);
singleLinkedList.append(value);
System.out.println();
System.out.println("Append :"+value);
System.out.println(Arrays.toString(singleLinkedList.snapshot()));
System.out.println(singleLinkedList.getSize());
System.out.println();
}
for(int i=0;i<loop;i++) {
int value = random.nextInt(loop);
boolean contains = singleLinkedList.contains(value);
singleLinkedList.removeFirst(value);
System.out.println();
System.out.println("Contains :"+contains);
System.out.println("RemoveFirst :"+value);
System.out.println(Arrays.toString(singleLinkedList.snapshot()));
System.out.println(singleLinkedList.getSize());
System.out.println();
}
}
}