Structure de données de liste doublement chaînée
La liste doublement chaînée est une structure de données fondamentale où chaque élément contient des références vers les nœuds précédents et suivants. Cette structure permet un parcours bidirectionnel et des opérations d'insretion/suppression efficaces aux deux extrémités.
Implémentation en C++
Voici une implémentation template en C++ avec gestion mémoire et fonctionnalités avencées :
template<typename T>
class DoubleLinkedList {
private:
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};
Node* head;
Node* tail;
size_t count;
public:
DoubleLinkedList() : head(nullptr), tail(nullptr), count(0) {}
~DoubleLinkedList() {
clear();
}
void push_front(const T& value) {
Node* newNode = new Node(value);
if (empty()) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
++count;
}
void push_back(const T& value) {
Node* newNode = new Node(value);
if (empty()) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
++count;
}
bool remove(const T& value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
if (current->prev) current->prev->next = current->next;
else head = current->next;
if (current->next) current->next->prev = current->prev;
else tail = current->prev;
delete current;
--count;
return true;
}
current = current->next;
}
return false;
}
void selection_sort(bool ascending = true) {
if (count < 2) return;
Node* i = head;
while (i != nullptr) {
Node* extremum = i;
Node* j = i->next;
while (j != nullptr) {
if (ascending ? (j->data < extremum->data) :
(j->data > extremum->data)) {
extremum = j;
}
j = j->next;
}
if (extremum != i) {
std::swap(i->data, extremum->data);
}
i = i->next;
}
}
bool empty() const { return count == 0; }
size_t size() const { return count; }
void clear() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
tail = nullptr;
count = 0;
}
T& operator[](size_t index) {
if (index >= count) throw std::out_of_range("Index invalide");
Node* current;
if (index < count / 2) {
current = head;
for (size_t i = 0; i < index; ++i) {
current = current->next;
}
} else {
current = tail;
for (size_t i = count - 1; i > index; --i) {
current = current->prev;
}
}
return current->data;
}
};
Exemple d'utilisation en C++
#include <iostream>
int main() {
DoubleLinkedList<std::string> liste;
liste.push_back("Alpha");
liste.push_back("Bravo");
liste.push_back("Charlie");
liste.push_back("Delta");
std::cout << "Avant tri: ";
for (size_t i = 0; i < liste.size(); ++i) {
std::cout << liste[i] << " ";
}
std::cout << std::endl;
liste.selection_sort();
std::cout << "Après tri: ";
for (size_t i = 0; i < liste.size(); ++i) {
std::cout << liste[i] << " ";
}
std::cout << std::endl;
return 0;
}
Implémentation en C#
Version générique avec énumérateur et support des collections :
public class DoubleLinkedList<T> : IEnumerable<T> where T : IComparable<T> {
private class Node {
public T Value;
public Node Next;
public Node Previous;
public Node(T value) {
Value = value;
}
}
private Node first;
private Node last;
private int count;
public int Count => count;
public void AddFront(T item) {
var newNode = new Node(item);
if (first == null) {
first = last = newNode;
} else {
newNode.Next = first;
first.Previous = newNode;
first = newNode;
}
count++;
}
public void AddBack(T item) {
var newNode = new Node(item);
if (last == null) {
first = last = newNode;
} else {
newNode.Previous = last;
last.Next = newNode;
last = newNode;
}
count++;
}
public bool Remove(T item) {
var current = first;
while (current != null) {
if (current.Value.Equals(item)) {
if (current.Previous != null) {
current.Previous.Next = current.Next;
} else {
first = current.Next;
}
if (current.Next != null) {
current.Next.Previous = current.Previous;
} else {
last = current.Previous;
}
count--;
return true;
}
current = current.Next;
}
return false;
}
public void Sort(bool ascending = true) {
if (count < 2) return;
var current = first;
while (current != null) {
var extremum = current;
var runner = current.Next;
while (runner != null) {
if (ascending ? runner.Value.CompareTo(extremum.Value) < 0 :
runner.Value.CompareTo(extremum.Value) > 0) {
extremum = runner;
}
runner = runner.Next;
}
if (extremum != current) {
(current.Value, extremum.Value) = (extremum.Value, current.Value);
}
current = current.Next;
}
}
public IEnumerator<T> GetEnumerator() {
var current = first;
while (current != null) {
yield return current.Value;
current = current.Next;
}
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Exemple d'utilisation en C#
var liste = new DoubleLinkedList<string>();
liste.AddBack("Alpha");
liste.AddBack("Bravo");
liste.AddBack("Charlie");
liste.AddBack("Delta");
Console.WriteLine("Avant tri: " + string.Join(" ", liste));
liste.Sort();
Console.WriteLine("Après tri: " + string.Join(" ", liste));
Implémentation en Java
Version avec généricité et itérateur :
import java.util.Iterator;
public class DoubleLinkedList<T extends Comparable<T>> implements Iterable<T> {
private static class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) {
this.data = data;
}
}
private Node<T> head;
private Node<T> tail;
private int size;
public void addFirst(T element) {
Node<T> newNode = new Node<>(element);
if (head == null) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
public void addLast(T element) {
Node<T> newNode = new Node<>(element);
if (tail == null) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
size++;
}
public boolean remove(T element) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(element)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
size--;
return true;
}
current = current.next;
}
return false;
}
public void sort(boolean ascending) {
if (size < 2) return;
Node<T> i = head;
while (i != null) {
Node<T> extremum = i;
Node<T> j = i.next;
while (j != null) {
if (ascending ? j.data.compareTo(extremum.data) < 0 :
j.data.compareTo(extremum.data) > 0) {
extremum = j;
}
j = j.next;
}
if (extremum != i) {
T temp = i.data;
i.data = extremum.data;
extremum.data = temp;
}
i = i.next;
}
}
public int size() {
return size;
}
@Override
public Iterator<T> iterator() {
return new Iterator<>() {
private Node<T> current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public T next() {
T data = current.data;
current = current.next;
return data;
}
};
}
}
Exemple d'utilisation en Java
public class Main {
public static void main(String[] args) {
DoubleLinkedList<String> liste = new DoubleLinkedList<>();
liste.addLast("Alpha");
liste.addLast("Bravo");
liste.addLast("Charlie");
liste.addLast("Delta");
System.out.print("Avant tri: ");
for (String item : liste) {
System.out.print(item + " ");
}
System.out.println();
liste.sort(true);
System.out.print("Après tri: ");
for (String item : liste) {
System.out.print(item + " ");
}
System.out.println();
}
}
Caractéristiques des implémentations
Ces implémentations offrent :
- Complexité temporelle O(1) pour les insertions/suppressions aux extrémités
- Recherche en O(n) avec optiimsation possible par tri préalable
- Gestion automatique de la mémoire (destructeurs C#, garbage collection Java)
- Support des itérations avec foreach/for-each
- Tri par sélection intégré avec ordre configurable