Représentation d'une liste chaînée bi-directionnelle

Question

Comment représenter une liste bi-directionnelle (doublement)?

Answer 1

C'est une liste chaînée dans laquelle chaque nœud a des références aux nœuds suivant et précédent.

http://en.wikipedia.org/wiki/Doubly-linked_list

Answer 2

pseudocode:

list-node 
{ 
    some-data 
    pointer-or-reference to prev-list-node 
    pointer-or-reference to next-list-node 
} 

De cette façon, vous pouvez:

current-node = beginning 
current-node = current-node -> next-list-node 
current-node = current-node -> prev-list-node 

de "déplacer" avant et en arrière. La syntaxe dépend de la langue.

Answer 3

En C#:

internal class ListNode<T> { 

    public T Item { get; set; } 
    public ListNode Prev { get; set; } 
    public ListNode Next { get; set; } 

} 

public class List<T> { 

    public List() { Head = Tail = null; } 

    public void Add(T item) { 
     var node = new ListNode<T>(item); 
     if(IsEmpty) 
      Head = Tail = node; 
     else { 
      node.Prev = Tail; 
      Tail.Next = node; 
      Tail = node; 
     }   
    } 

    protected ListNode<T> Head { get; set; } 
    protected ListNode<T> Tail { get; set; } 

    public bool IsEmpty { get { return Head == null; } } 

} 

et ainsi de suite ...