C#数据结构与算法揭秘四 双向链表

C#数据结构与算法揭秘四 双向链表

简介

本文将讲解如何在C#中实现双向链表。双向链表是一种常用的数据结构，在许多算法中都有广泛应用，它提供了与单向链表不同的灵活性和便利性。

双向链表的实现

创建一个双向节点

双向链表由节点（Node）组成。一个节点包含两个指针：一个指向前一个节点，一个指向后一个节点。由于这两个指针都可能为null，所以我们将它们声明为可空类型的指针。

public class Node<T>
{
    public T Data { get; set; }
    public Node<T>? Previous { get; set; }
    public Node<T>? Next { get; set; }
}

创建一个双向链表

有了节点，我们就可以创建一个双向链表了。一个双向链表由一个头指针和一个尾指针组成。头指针指向链表的第一个节点，尾指针指向链表的最后一个节点。由于这两个指针都可能为null，所以我们将它们声明为可空类型的指针。

public class DoublyLinkedList<T>
{
    public Node<T>? Head { get; private set; }
    public Node<T>? Tail { get; private set; }

    public bool IsEmpty => Head == null;

    public void AddFirst(T data)
    {
        var node = new Node<T> {Data = data};

        if (IsEmpty)
        {
            Head = node;
            Tail = node;
        }
        else
        {
            Head!.Previous = node;
            node.Next = Head;
            Head = node;
        }
    }

    public void AddLast(T data)
    {
        var node = new Node<T> {Data = data};

        if (IsEmpty)
        {
            Head = node;
            Tail = node;
        }
        else
        {
            Tail!.Next = node;
            node.Previous = Tail;
            Tail = node;
        }
    }
}

双向链表的遍历

遍历双向链表时，我们可以从头指针开始遍历，直到到达尾指针。或者从尾指针开始遍历，直到到达头指针。

public void Traverse()
{
    var currentNode = Head;
    while (currentNode != null)
    {
        Console.Write($"{currentNode.Data} ");
        currentNode = currentNode.Next;
    }
    Console.WriteLine();
}

public void ReverseTraverse()
{
    var currentNode = Tail;
    while (currentNode != null)
    {
        Console.Write($"{currentNode.Data} ");
        currentNode = currentNode.Previous;
    }
    Console.WriteLine();
}

示例说明

假如我们需要存储一个音乐播放器的播放列表，我们可以使用双向链表来实现。

我们可以定义一个MusicTrack类来表示音乐曲目：

public class MusicTrack
{
    public string Title { get; set; }
    public string Artist { get; set; }
    public TimeSpan Duration { get; set; }
}

然后创建一个MusicPlaylist类，它使用双向链表来存储MusicTrack对象。

public class MusicPlaylist
{
    private readonly DoublyLinkedList<MusicTrack> _playlist = new DoublyLinkedList<MusicTrack>();

    public void AddTrack(MusicTrack track) => _playlist.AddLast(track);

    public void Play() => _playlist.Traverse();

    public void ReversePlay() => _playlist.ReverseTraverse();
}

这样就可以非常方便地操作播放列表了。

var playlist = new MusicPlaylist();

playlist.AddTrack(new MusicTrack { Title = "Song A", Artist = "Artist A", Duration = TimeSpan.FromMinutes(3) });
playlist.AddTrack(new MusicTrack { Title = "Song B", Artist = "Artist B", Duration = TimeSpan.FromMinutes(4) });
playlist.AddTrack(new MusicTrack { Title = "Song C", Artist = "Artist C", Duration = TimeSpan.FromMinutes(5) });

playlist.Play();
// Output: Song A Song B Song C

playlist.ReversePlay();
// Output: Song C Song B Song A

小结

本文详细讲解了如何在C#中实现双向链表。双向链表是一种非常常用的数据结构，它提供了很多便利和灵活性，可以用来实现许多算法和数据结构。