C#数据结构－链表

理论基础：

链表是用一组任意的存储单元来存储线性表中的数据元素。

如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表(Singly Linked List)。

单链表由头引用H唯一确定。头引用指向单链表的第一个结点，也就是把单链表第一个结点的地址放在H中。

C#实现：

1接口

引用线性表的接口IListDS<T>

2实现

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

首先，必须定义一个单链表的节点类

public class Node<T>

{

    private T data;        //数据域

    private Node<T> next;  //引用域

    public Node(T val)

    {

        data = val;

        next = null;

    }

    public Node()

    {

        data = default(T);

        next = null;

    }

    public T Data

    {

        get { return data; }

        set { data = value; }

    }

    public Node<T> Next

    {

        get { return next; }

        set { next = value; }

    }

}

实现主体类

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

Append,Insert,InsertBack三个方法实质上都是插入操作，可以考虑用overload或者override来实现，有兴趣的朋友试试。

public class LinkList<T> : IListDS<T>

{

    private Node<T> head;

    public Node<T> Head

    {

        get { return head; }

        set { head = value; }

    }

    public LinkList()

    {

        head = null;

    }

    /// <summary>

    /// 获取长度

    /// </summary>

    /// <returns></returns>

    public int GetLength()

    {

        Node<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()

    {

        if (head == null)

        {

            return true;

        }

        else

        {

            return false;

        }

    }

    /// <summary>

    /// 附加操作,线性表未满，将值为item的新元素添加到末尾

    /// </summary>

    /// <param name="item"></param>

    public void Append(T item)

    {

        Node<T> newNode = new Node<T>(item);  //根据元素创建新的节点

        Node<T> node = new Node<T>();

        if (head == null)

        {

            head = newNode;

            return;

        }

        node = head;

        while (node.Next != null)

        {

            node = node.Next;

        }

        node.Next = newNode;

    }

    /// <summary>

    /// 寻找节点

    /// </summary>

    /// <param name="i"></param>

    /// <returns></returns>

    public Node<T> FindNode(int i)

    {

        if (IsEmpty())

        {

            Console.Write("List is empty");

            return null;

        }

        if (i < 1)

        {

            Console.Write("Index is error");

            return null;

        }

        Node<T> current = head;

        int j = 1;

        while (current.Next != null && j < i)

        {

            ++j;

            current = current.Next;

        }

        return current;

    }

    /// <summary>

    /// 插入操作,在第i个节点前面插入item

    /// </summary>

    /// <param name="item"></param>

    /// <param name="i"></param>

    public void Insert(T item, int i)

    {

        Node<T> newNode = new Node<T>(item);

        Node<T> node = new Node<T>();

        Node<T> current = FindNode(i);

        if (current != null)

        {

            node = current;       //对目标节点备份

            newNode.Next = current;

            node.Next = newNode;

        }

    }

    /// <summary>

    /// 插入操作,在第i个节点后面插入item

    /// </summary>

    /// <param name="item"></param>

    /// <param name="i"></param>

    public void InsertBack(T item, int i)

    {

        Node<T> newNode = new Node<T>(item);

        Node<T> current = FindNode(i);

        if (current != null)

        {

            newNode.Next = current.Next;

            current.Next = newNode;

        }

    }

    /// <summary>

    /// 删除操作

    /// </summary>

    /// <param name="i"></param>

    /// <returns></returns>

    public T Delete(int i)

    {

        Node<T> current = FindNode(i);

        Node<T> node = new Node<T>();

        if (current != null)

        {

            node = current;   //对目标节点备份

            node.Next = current.Next;

            return current.Data;

        }

        else

        {

            Console.Write("the node is not exist!");

            return default(T);

        }

    }