继续发数据结构系列~今天是单链表。

类图:

接口的代码不重复发了。在前一篇《C#数据结构之顺序表SqList》里有。

节点类Node

public class Node
{
    private T _Data;
    private Node _Next;

    public T Data
    {
        get { return _Data; }
        set { _Data = value; }
    }
    
    public Node Next
    {
        get { return _Next; }
        set { _Next = value; }
    }

    public Node(T val, Node p)
    {
        _Data = val;
        _Next = p;
    }

    public Node(Node p)
    {
        _Next = p;
    }

    public Node(T val)
    {
        _Data = val;
        _Next = null;
    }

    public Node()
    {
        _Data = default(T);
        _Next = null;
    }
}

单链表类LinkList

public class LinkList : IListDs
{
    private Node _Head;

    public Node Head
    {
        get
        {
            return _Head;
        }
        set
        {
            _Head = value;
        }
    }

    public int Length
    {
        get
        {
            Node p = _Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }
    }

    public bool IsEmpty
    {
        get
        {
            if (_Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }

    public LinkList()
    {
        _Head = null;
    }

    public void Clear()
    {
        _Head = null;
    }

    public void Append(T item)
    {
        Node q = new Node(item);
        Node p = new Node();
        if (_Head == null)
        {
            _Head = q;
            return;
        }
        p = _Head;
        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = q;
    }

    public void Insert(T item, int i)
    {
        if (IsEmpty || i < 1)
        {
            // List is empty or Position is error
            return;
        }
        if (i == 1)
        {
            Node q = new Node(item);
            q.Next = _Head;
            _Head = q;
            return;
        }
        Node p = _Head;
        Node r = new Node();
        int j = 1;
        while (p.Next != null && j < i)
        {
            r = p;
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node q = new Node(item);
            q.Next = p;
            r.Next = q;
        }
    }

    public void InsertPost(T item, int i)
    {
        if (IsEmpty || i < 1)
        {
            //List is empty or Position is error!
            return;
        }
        if (i == 1)
        {
            Node q = new Node(item);
            q.Next = _Head.Next;
            _Head.Next = q;
            return;
        }
        Node p = _Head;
        int j = 1;
        while (p != null && j < i)
        {
            p = p.Next;
            ++j;
        }
        if (j == i)
        {
            Node q = new Node(item);
            q.Next = p.Next;
            p.Next = q;
        }
    }
    
    public T Delete(int i)
    {
        if (IsEmpty || i < 0)
        {
            //Link is empty or Position is error!
            return default(T);
        }

        Node q = new Node();
        if (i == 1)
        {
            q = _Head;
            _Head = _Head.Next;
            return q.Data;
        }
        Node 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
        {
            //The ith node is not exist!
            return default(T);
        }
    }

    public T GetElement(int i)
    {
        // 转换为物理序位
        --i;

        if (IsEmpty)
        {
            //List is empty!
            return default(T);
        }
        Node p = new Node();
        p = _Head;
        int j = 0;
        while (p.Next != null && j < i)
        {
            ++j;
            p = p.Next;
        }
        if (j == i)
        {
            return p.Data;
        }
        else
        {
            //The ith node is not exist
            return default(T);
        }
    }

    public int Locate(T value)
    {
        if (IsEmpty)
        {
            //List is Empty!
            return -1;
        }
        Node p = new Node();
        p = _Head;
        int i = 1;
        while (!p.Data.Equals(value) && p.Next != null)
        {
            p = p.Next;
            ++i;
        }
        return i;
    }
}

测试代码:

private static void LinkListTest()
{
    Console.WriteLine("LinkList Created:\n---------------------------------");
    LinkList lkList = CreateLListHead(new string[] { "a", "b", "c", "d" });
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.WriteLine("Post Insert \"world\" into index 2:\n---------------------------------");
    lkList.InsertPost("world", 2);
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.WriteLine("Insert \"hello\" into index 2:\n---------------------------------");
    lkList.InsertPost("hello", 2);
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.WriteLine("Append \"e\":\n---------------------------------");
    lkList.Append("e");
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.WriteLine("Delete item on index 5:\n---------------------------------");
    lkList.Delete(5);
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.WriteLine("Locate item \"hello\":\n---------------------------------");
    Console.WriteLine("#{0}", lkList.Locate("hello"));
    Console.WriteLine();

    Console.WriteLine("Clear LinkList:\n---------------------------------");
    lkList.Clear();
    PrintLinkList(lkList);
    Console.WriteLine("\n");

    Console.ReadKey();
}

public static LinkList CreateLListHead(string[] strs)
{
    LinkList L = new LinkList();
    foreach (var item in strs)
    {
        Node p = new Node(item);
        p.Next = L.Head;
        L.Head = p;
    }
    return L;
}

有图有真相: