【愚公系列】2021年11月 C#版 数据结构与算法解析(链表)

一：单链表实现原理

//链表类，包含链表定义及基本操作方法  
public class MyLinkList<T>
{
    private Node<T> head; //单链表的头结点  
    //头结点属性  
    public Node<T> Head
    {
        get
        {
            return head;
        }
        set
        {
            head = value;
        }
    }
    //构造器  
    public MyLinkList()
    {
        head = null;
    }
    //求单链表的长度  
    public int GetLength()
    {
        Node<T> p = head;
        int len = 0;
        while (p != null)
        {
            ++len;
            p = p.Next;
        }
        return len;
    }
    //清空单链表  
    public void Clear()
    {
        head = null;
    }
    //判断单链表是否为空  
    public bool IsEmpty()
    {
        if (head == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    //在单链表的末尾添加新元素  
    public void Append(T item)
    {
        Node<T> q = new Node<T>(item);
        Node<T> p = new Node<T>();
        if (head == null)
        {
            head = q;
            return;
        }
        p = head;
        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = q;
    }
    //在单链表的第i个结点的位置前插入一个值为item的结点  
    public void Insert(T item, int i)
    {
        if (IsEmpty() || i < 1 || i > GetLength())
        {
            Console.WriteLine("LinkList is empty or Position is error!");
            return;
        }
        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head;
            head = q;
            return;
        }
        Node<T> p = head;
        Node<T> r = new Node<T>();
        int j = 1;
        while (p.Next != null && j < i)
        {
            r = p;
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p;
            r.Next = q;
        }
    }
    //在单链表的第i个结点的位置后插入一个值为item的结点  
    public void InsertPost(T item, int i)
    {
        if (IsEmpty() || i < 1 || i > GetLength())
        {
            Console.WriteLine("LinkList is empty or Position is error!");
            return;
        }
        if (i == 1)
        {
            Node<T> q = new Node<T>(item);
            q.Next = head.Next;
            head.Next = q;
            return;
        }
        Node<T> p = head;
        int j = 1;
        while (p != null && j < i)
        {
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node<T> q = new Node<T>(item);
            q.Next = p.Next;
            p.Next = q;
        }
    }
    //删除单链表的第i个结点  
    public T Delete(int i)
    {
        if (IsEmpty() || i < 0 || i > GetLength())
        {
            Console.WriteLine("LinkList is empty or Position is error!");
            return default(T);
        }
        Node<T> q = new Node<T>();
        if (i == 1)
        {
            q = head;
            head = head.Next;
            return q.Data;
        }
        Node<T> p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            q = p;
            p = p.Next;
        }
        if (j == i)
        {
            q.Next = p.Next;
            return p.Data;
        }
        else
        {
            Console.WriteLine("The " + i + "th node is not exist!");
            return default(T);
        }
    }
    //获得单链表的第i个数据元素  
    public T GetElem(int i)
    {
        if (IsEmpty() || i < 0)
        {
            Console.WriteLine("LinkList is empty or position is error! ");
            return default(T);
        }
        Node<T> p = new Node<T>();
        p = head;
        int j = 1;
        while (p.Next != null && j < i)
        {
            ++j;
            p = p.Next;
        }
        if (j == i)
        {
            return p.Data;
        }
        else
        {
            Console.WriteLine("The " + i + "th node is not exist!");
            return default(T);
        }
    }
    //在单链表中查找值为value的结点  
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.WriteLine("LinkList is Empty!");
            return -1;
        }
        Node<T> p = new Node<T>();
        p = head;
        int i = 1;
        while (!p.Data.Equals(value) && p.Next != null)
        {
            p = p.Next;
            ++i;
        }
        return i;
    }
    //显示链表  
    public void Display()
    {
        Node<T> p = new Node<T>();
        p = this.head;
        while (p != null)
        {
            Console.Write(p.Data + " ");
            p = p.Next;
        }
    }
}

public class Program
{
    static void Main(string[] args)
    {
        MyLinkList<string> myLinkList = new MyLinkList<string>(); //实例化一个单链表  
        Console.WriteLine(myLinkList.GetLength());   //获取长度  
        //添加元素  
        myLinkList.Append("good");
        myLinkList.Append("monring");
        myLinkList.Append("lwk");
        myLinkList.Insert("!", 5);  //在i结点前插元素，位置错误测试  
        myLinkList.InsertPost("!", 5);  //在i结点后插元素，位置错误测试  
        myLinkList.InsertPost("!", 3);  //后插元素  
        myLinkList.Insert(",", 3);  //前插元素  
        myLinkList.Display();  //显示链表元素  
        Console.WriteLine(myLinkList.GetElem(4));//获取结点,并显示  
        myLinkList.Delete(1);  //删除结点  
        myLinkList.Display();
        Console.WriteLine(myLinkList.GetLength()); //显示链表长度  
        Console.Read();
    }
}

二：双向链表实现原理

using System;
using System.Text;
namespace 线性表
{
  public class DbLinkList<T> : IListDS<T>
  {
    private DbNode<T> head;
    public DbNode<T> Head
    {
      get { return head; }
      set { head = value; }
    }
    public DbLinkList()
    {
      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 int Count()
    {
      DbNode<T> p = head;
      int len = 0;
      while (p != null)
      {
        len++;
        p = p.Next;
      }
      return len;
    }
    /// <summary>
    /// 清空
    /// </summary>
    public void Clear()
    {
      head = null;
    }
    /// <summary>
    /// 是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
      return head == null;
    }
    /// <summary>
    /// 在最后附加元素
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
      DbNode<T> d = new DbNode<T>(item);
      DbNode<T> n = new DbNode<T>();
      if (head == null)
      {
        head = d;
        return;
      }
      n = head;
      while (n.Next != null)
      {
        n = n.Next;
      }
      n.Next = d;
      d.Prev = n;
    }
    //前插
    public void InsertBefore(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      //在最开头插入
      if (i == 0)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = head;//把"头"改成第二个元素
        head.Prev = q;
        head = q;//把自己设置为"头"
        return;
      }
      DbNode<T> n = head;
      DbNode<T> d = new DbNode<T>();
      int j = 0;
      //找到位置i的前一个元素d
      while (n.Next != null && j < i)
      {
        d = n;
        n = n.Next;
        j++;
      }
      if (n.Next == null) //说明是在最后节点插入(即追加)
      {
        DbNode<T> q = new DbNode<T>(item);
        n.Next = q;
        q.Prev = n;
        q.Next = null;
      }
      else
      {
        if (j == i)
        {
          DbNode<T> q = new DbNode<T>(item);
          d.Next = q;
          q.Prev = d;
          q.Next = n;
          n.Prev = q;
        }
      }
    }
    /// <summary>
    /// 在位置i后插入元素item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void InsertAfter(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      if (i == 0)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = head.Next;
        head.Next.Prev = q;
        head.Next = q;
        q.Prev = head;
        return;
      }
      DbNode<T> p = head;
      int j = 0;
      while (p != null && j < i)
      {
        p = p.Next;
        j++;
      }
      if (j == i)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = p.Next;
        if (p.Next != null)
        {
          p.Next.Prev = q;
        }
        p.Next = q;
        q.Prev = p;
      }
      else      
      {
        Console.WriteLine("Position is error!");
      }
    }
    /// <summary>
    /// 删除位置i的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T RemoveAt(int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("Link is empty or Position is error!");
        return default(T);
      }
      DbNode<T> q = new DbNode<T>();
      if (i == 0)
      {
        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 (j == i)
      {
        p.Next.Prev = q;
        q.Next = p.Next;        
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    /// <summary>
    /// 获取指定位置的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetItemAt(int i)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is empty!");
        return default(T);
      }
      DbNode<T> p = new DbNode<T>();
      p = head;
      if (i == 0) 
      { 
        return p.Data; 
      }
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        p = p.Next;
      }
      if (j == i)
      {
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    //按元素值查找索引
    public int IndexOf(T value)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is Empty!");
        return -1;
      }
      DbNode<T> p = new DbNode<T>();
      p = head;
      int i = 0;
      while (!p.Data.Equals(value) && p.Next != null)
      {
        p = p.Next;
        i++;
      }
      return i;
    }
    /// <summary>
    /// 元素反转
    /// </summary>
    public void Reverse()
    {
      DbLinkList<T> result = new DbLinkList<T>();
      DbNode<T> t = this.head;
      result.Head = new DbNode<T>(t.Data);
      t = t.Next;
      //(把当前链接的元素从head开始遍历，逐个插入到另一个空链表中，这样得到的新链表正好元素顺序跟原链表是相反的)
      while (t!=null)
      {        
        result.InsertBefore(t.Data, 0);
        t = t.Next;
      }
      this.head = result.head;//将原链表直接挂到"反转后的链表"上
      result = null;//显式清空原链表的引用，以便让GC能直接回收
    }
    //得到某个指定的节点(为了下面测试从后向前遍历)
    private DbNode<T> GetNodeAt(int i){
      if (IsEmpty())
      {
        Console.WriteLine("List is empty!");
        return null;
      }
      DbNode<T> p = new DbNode<T>();
      p = head;
      if (i == 0)
      {
        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 is not exist!");
        return null;
      }
    }
    /// <summary>
    /// 测试用prev属性从后面开始遍历
    /// </summary>
    /// <returns></returns>
    public string TestPrevErgodic() 
    {
      DbNode<T> tail = GetNodeAt(Count() - 1);
      StringBuilder sb = new StringBuilder();
      sb.Append(tail.Data.ToString() + ",");
      while (tail.Prev != null)
      {
        sb.Append(tail.Prev.Data.ToString() + ",");
        tail = tail.Prev;
      }
      return sb.ToString().TrimEnd(',');      
    }
    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(',');
    }
  }
}

Console.WriteLine("-------------------------------------");
Console.WriteLine("双链表测试开始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8 
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z

双链表的插入操作要稍微复杂一点，示意图如下：

同样对于删除操作，也要额外处理prev指向

二：循环双向链表实现原理

代码就不贴了