C#实现双向链表

一、定义

双向链表是链表的一种，它的每个数据节点都有2个指针，分别指向直接前驱和直接后序。所以，从双向链表中的任意一个节点开始，都可以很方便的访问它的前驱节点和后继结点。

双链表中有2条不同方向的链，即每个节点中除了next域存放后继结点地址外，还增加一个指向其直接前驱的指针域prev。

双链表的特点：

1）双链表有头指针head唯一确定

2）带头结点的双链表的某些运算将变得方便

3）将头结点和尾节点连接起来，可成为双向循环链表

双链表的好处在于，如果在链表中需要通过某个节点得到它的直接前驱或者直接后继结点时，双链表直接用prev或者next引用就能找到；而单链表要做到这一点，必须再次从head节点开始一个一个向后找。这样，时间复杂度就从O(n)降低到O(1)，显然效率更高。

二、节点Node类型定义

/// <summary>
/// 双向链表的节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class DbNode<T>
{
    //私有变量
    private T _data; //节点的值
    private DbNode<T> _prev; //前驱节点
    private DbNode<T> _next; //后继结点

    //属性

    /// <summary>
    /// 节点的值
    /// </summary>
    public T Data
    {
        get { return this._data; }
        set { this._data = value; }
    }

    /// <summary>
    /// 前驱节点
    /// </summary>
    public DbNode<T> Prev
    {
        get { return this._prev; }
        set { this._prev = value; }
    }

    /// <summary>
    /// 后继结点
    /// </summary>
    public DbNode<T> Next
    {
        get { return this._next; }
        set { this._next = value; }
    }

    // 构造函数 6个

    public DbNode(T data, DbNode<T> prev, DbNode<T> next)
    {
        this._data = data;
        this._prev = prev;
        this._next = next;
    }

    public DbNode(T data, DbNode<T> prev)
    {
        this._data = data;
        this._prev = prev;
        this._next = null; //结尾处的node
    }

    //public DbNode(T data, DbNode<T> next)
    //{
    //    this._data = data;
    //    this._prev = null; //开头处的node
    //    this._next = next;
    //}

    public DbNode(DbNode<T> next)
    {
        //使用 default 关键字，此关键字对于引用类型会返回空，对于数值类型会返回零。
        //对于结构，此关键字将返回初始化为零或空的每个结构成员，具体取决于这些结构是值类型还是引用类型
        this._data = default(T);
        this._next = next;
        this._prev = null;
    }

    public DbNode(T data)
    {
        this._data = data;
        this._prev = null;
        this._next = null;
    }

    public DbNode()
    {
        this._data = default(T);
        this._prev = null;
        this._next = null;
    }
}

三、双链表的完整实现（C#）

/// <summary>
/// 双向链表类
/// </summary>
public class DbLinkedList<T>
{

    private DbNode<T> _head;

    public DbNode<T> Head
    {
        get { return this._head; }
        set { this._head = value; }
    }

    //构造函数
    public DbLinkedList()
    {
        Head = null;
    }

    /// <summary>
    /// 索引器
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T this[int index]
    {
        get
        {
            return this.GetItemAt(index);
        }
    }

    /// <summary>
    /// 判断双向链表是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        return Head == null;
    }

    /// <summary>
    /// 获取指定位置的元素
    /// </summary>
    /// <param name="i">指定的位置</param>
    /// <returns>T node</returns>
    public T GetItemAt(int i)
    {
        //判空
        if (IsEmpty())
        {
            Console.WriteLine("The double linked list is empty.");
            return default(T);
        }

        DbNode<T> p = new DbNode<T>();
        p = Head;

        // 如果是第一个node
        if (0 == i)
        {
            return p.Data;
        }

        int j = 0;
        while (p.Next != null && j < i)//移动j的指针到i的前一个node
        {
            j++;
            p = p.Next;
        }

        if (j == i)
        {
            return p.Data;
        }
        else
        {
            Console.WriteLine("The node dose not exist.");
            return default(T);
        }
    }

    /// <summary>
    /// 返回链表的长度
    /// </summary>
    /// <returns></returns>
    public int Count()
    {
        DbNode<T> p = Head;
        int length = 0;
        while (p != null)
        {
            length++;
            p = p.Next;
        }
        return length;
    }

    /// <summary>
    /// 清空双链表
    /// </summary>
    public void Clear()
    {
        this.Head = null;
    }

    /// <summary>
    /// 在位置i后插入node T
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void AddAfter(T item, int i)
    {
        if (IsEmpty() || i < 0)
        {
            Console.WriteLine("The double linked list is empty or the position is uncorrect.");
            return;
        }

        if (0 == i) //在头之后插入元素
        {
            DbNode<T> newNode = new DbNode<T>(item);
            newNode.Next = Head.Next;
            Head.Next.Prev = newNode;
            Head.Next = newNode;
            newNode.Prev = Head;
            return;
        }

        DbNode<T> p = Head; //p指向head
        int j = 0;

        while (p != null && j < i)
        {
            p = p.Next;
            j++;
        }

        if (j == i)
        {
            DbNode<T> newNode = new DbNode<T>(item);
            newNode.Next = p.Next;
            if (p.Next != null)
            {
                p.Next.Prev = newNode;
            }
            newNode.Prev = p;
            p.Next = newNode;
        }
        else
        {
            Console.WriteLine("The position is uncorrect.");
        }



    }

    /// <summary>
    /// 在位置i前插入node T
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void AddBefore(T item, int i)
    {
        if (IsEmpty() || i < 0)
        {
            Console.WriteLine("The double linked list is empty or the position is uncorrect.");
            return;
        }

        if (0 == i) //在头之前插入元素
        {
            DbNode<T> newNode = new DbNode<T>(item);
            newNode.Next = Head; //把头改成第二个元素
            Head.Prev = newNode;
            Head = newNode; //把新元素设置为头
            return;
        }

        DbNode<T> n = Head;
        DbNode<T> d = new DbNode<T>();
        int j = 0;

        while (n.Next != null && j < i)
        {
            d = n; //把d设置为头
            n = n.Next;
            j++;
        }

        if (n.Next == null) //在最后节点后插入，即AddLast
        {
            DbNode<T> newNode = new DbNode<T>(item);
            n.Next = newNode;
            newNode.Prev = n;
            newNode.Next = null;//尾节点指向空
        }
        else //插到中间
        {
            if (j == i)
            {
                DbNode<T> newNode = new DbNode<T>(item);
                d.Next = newNode;
                newNode.Prev = d;
                newNode.Next = n;
                n.Prev = newNode;
            }
        }
    }

    /// <summary>
    /// 在链表最后插入node
    /// </summary>
    /// <param name="item"></param>
    public void AddLast(T item)
    {
        DbNode<T> newNode = new DbNode<T>(item);
        DbNode<T> p = new DbNode<T>();

        if (Head == null)
        {
            Head = newNode;
            return;
        }
        p = Head; //如果head不为空，head就赋值给第一个节点
        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = newNode;
        newNode.Prev = p;
    }

    /// <summary>
    /// 移除指定位置的node
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T RemoveAt(int i)
    {
        if (IsEmpty() || i < 0)
        {
            Console.WriteLine("The double linked list is empty or the position is uncorrect.");
            return default(T);
        }

        DbNode<T> q = new DbNode<T>();
        if (0 == i)
        {
            q = Head;
            Head = Head.Next;
            Head.Prev = null;//删除掉了第一个元素
            return q.Data;
        }

        DbNode<T> p = Head;
        int j = 0;

        while (p.Next != null && j < i)
        {
            j++;
            q = p;
            p = p.Next;
        }

        if (i == j) //?
        {
            p.Next.Prev = q;
            q.Next = p.Next;
            return p.Data;
        }
        else
        {
            Console.WriteLine("The position is uncorrect.");
            return default(T);
        }
    }

    /// <summary>
    /// 根据元素的值查找索引
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public int IndexOf(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("The list is empty.");
            return -1;
        }

        DbNode<T> p = new DbNode<T>();
        p = Head;
        int i = 0;
        while (p.Next != null && !p.Data.Equals(value))//查找value相同的item
        {
            p = p.Next;
            i++;
        }
        return i;
    }

    public void Reverse()
    {//遍历当前链表的元素，逐个插入到另一个临时链表中AddBefore
        //这样，得到的新链表的顺序正好和原链表是相反的

        DbLinkedList<T> tmpList = new DbLinkedList<T>();
        DbNode<T> p = this.Head;
        tmpList.Head = new DbNode<T>(p.Data);
        p = p.Next;

        while (p != null)
        {
            tmpList.AddBefore(p.Data, 0);
            p = p.Next;
        }

        this.Head = tmpList.Head;
        tmpList = null;
    }

    /// <summary>
    /// 根据Prev指针从最后一个节点开始倒叙遍历输出
    /// </summary>
    /// <returns></returns>
    public string ReverseByPrev()
    {
        //取得最后一个节点
        DbNode<T> tail = GetNodeAt(Count() - 1);
        StringBuilder sb = new StringBuilder();
        sb.Append(tail.Data.ToString() + ",");
        while (tail.Prev!=null)
        {
            sb.Append(tail.Prev.Data + ",");
            tail = tail.Prev;
        }
        return sb.ToString().TrimEnd(',');
    }

    /// <summary>
    /// 根据元素位置得到指定的节点
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    private DbNode<T> GetNodeAt(int i)
    {
        if (IsEmpty())
        {
            Console.WriteLine("The list is empty.");
            return null;
        }

        DbNode<T> p = new DbNode<T>();
        p = this.Head;

        if (0 == i)
        {
            return p;
        }

        int j = 0;
        while (p.Next != null && j < i)
        {
            j++;
            p = p.Next;
        }
        if (j == i)
        {
            return p;
        }
        else
        {
            Console.WriteLine("The node does not exist.");
            return null;
        }
    }

    public T Fisrt()
    {
        return this.GetItemAt(0);
    }

    public T Last()
    {
        return this.GetItemAt(this.Count() - 1);
    }


    /// <summary>
    /// 打印双向链表的每个元素
    /// </summary>
    public void Print()
    {
        DbNode<T> current = new DbNode<T>();
        current = this.Head;
        Console.Write(current.Data + ",");
        while (current.Next != null)
        {
            Console.Write(current.Next.Data + ",");
            current = current.Next;
        }
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        DbNode<T> n = this.Head;
        sb.Append(n.Data.ToString() + ",");
        while (n.Next != null)
        {
            sb.Append(n.Next.Data.ToString() + ",");
            n = n.Next;
        }

        return sb.ToString().TrimEnd(',');
    }
}

双链表的基本操作有14个：

操作	含义
AddAfter()	在链表中指定的现有node后添加新的node
AddBefore()	在链表中指定的现有node前添加新的node
AddFirst()	在链表的开头处添加新的node
AddLast()	在链表的结尾处添加新的node
Clear()	移除链表中的所有node
Contains()	确定某值是否存在在链表中
Find()	查找包含指定值的第一个node
FindLast()	查找包含指定值的最后一个node
Remove()	移除指定node
RemoveFirst()	移除位于开头处的node
RemoveLast()	移除位于结尾处的node
Count()	获取链表中实际包含的node数
Fisrt()	获取链表中的第一个node
Last()	获取链表中的最后一个node

四、测试代码

static void Main(string[] args)
{
    Console.WriteLine("-------------------------------------");
    Console.WriteLine("双链表测试开始...");

    DbLinkedList<String> dblink = new DbLinkedList<string>();
    DbNode<String> head = new DbNode<string>("x");
    dblink.Head = head;
    dblink.AddBefore("w", 0);
    dblink.AddBefore("v", 0);
    dblink.AddLast("y");

    int count = dblink.Count();
    dblink.AddBefore("z", count);

    Console.WriteLine(count);

    string result = dblink.ToString();
    Console.WriteLine(result);
    //dblink.Print();

    int position = dblink.IndexOf("z");
    Console.WriteLine("z在list中的第{0}位", position);

    Console.WriteLine("在list中第0个元素是:{0}",dblink[0]);
    Console.WriteLine("在list中第3个元素是:{0}", dblink[2]);

    string item = dblink.RemoveAt(2);
    Console.WriteLine("删除了list中的第2个元素：{0}", item);

    Console.WriteLine(dblink.ToString());

    dblink.AddBefore("x", 2);

    Console.WriteLine(dblink.ToString());

    Console.WriteLine("list中第2个元素是：{0}",dblink.GetItemAt(2));

    Console.WriteLine(dblink.ToString());

    //反转
    Console.WriteLine("-------链表反转--------");

    dblink.Reverse();
    Console.WriteLine(dblink.ToString());

    dblink.AddAfter("1", 0);
    dblink.AddAfter("2", 1);
    dblink.AddAfter("6", 6);
    dblink.AddAfter("8", 7);
    dblink.AddAfter("A", 10);//position error.

    Console.WriteLine(dblink.ToString());

    string tail = dblink.GetItemAt(dblink.Count() - 1);
    Console.WriteLine("结尾的元素是：{0}", tail);

    Console.WriteLine(dblink.ReverseByPrev());

    Console.WriteLine("链表是：{0}", dblink.ToString());

    Console.WriteLine("---链表中的第一个节点是：{0}", dblink[0]);
    Console.WriteLine("---链表中的最后一个节点是：{0}", dblink[dblink.Count() - 1]);

    Console.WriteLine("---First()：{0}", dblink.Fisrt());

    Console.WriteLine("---Last()：{0}", dblink.Last());
}