C#实现单链表（线性表）

顺序表由连续内存构成，链表则不同。顺序表的优势在于查找，链表的优势在于插入元素等操作。顺序表的例子：http://blog.csdn.net/suinon/archive/2010/02/28/5333668.aspx

要注意的是，单链表的Add（）方法最好不要频繁调用，尤其是链表长度较长的时候，因为每次Add，都会从头节点到尾节点进行遍历，这个缺点的优化方法是将节点添加到头部，但顺序是颠倒的。

所以，在下面的例子中，执行Purge（清洗重复元素）的时候，没有使用Add（）方法去添加元素，而是定义一个节点，让它始终指向目标单链表的最后一个节点，这样就不用每次都从头到尾遍历。

此外，链表还可以做成循环链表，即最后一个结点的next属性等于head，主要操作与单链表相似，判断最后一个结点，不是等于null，而是等于head

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinearList
{
    //定义线性表的行为，可供顺序表类和单链表类继承
    public interface IListDS<T>
    {
        int GetLength();
        void Insert(T item, int i);
        void Add(T item);
        bool IsEmpty();
        T GetElement(int i);
        void Delete(int i);
        void Clear();
        int LocateElement(T item);
        void Reverse();
    }
    //链表节点类
    class Node<T>
    {
        private T tData;
        private Node<T> nNext;
        public T Data
        {
            get { return this.tData; }
            set { this.tData = value; }
        }
        public Node<T> Next
        {
            get { return this.nNext; }
            set { this.nNext = value; }
        }
        public Node()
        {
            this.tData = default(T);
            this.nNext = null;
        }
        public Node(T t)
        {
            this.tData = t;
            this.nNext = null;
        }
        public Node(T t,Node<T> node)
        {
            this.tData = t;
            this.nNext = node;
        }
    }
    //该枚举表示单链表Add元素的位置，分头部和尾部两种
    enum AddPosition {Head,Tail};
    //单链表类
    class LinkedList<T>:IListDS<T>
    {
        private Node<T> tHead;//单链表的表头
        public Node<T> Head
        {
            get { return this.tHead; }
            set { this.tHead = value; }
        }
        public LinkedList()
        {
            this.tHead = null;
        }
        public LinkedList(Node<T> node)
        {
            this.tHead = node;
        }
        public void Add(T item,AddPosition p)//选择添加位置
        {
            if (p == AddPosition.Tail)
            {
                this.Add(item);//默认添加在末尾
            }
            else//从头部添加会节省查找的开销，时间复杂度为O(1)不必每次都循环到尾部，这恰好是顺序表的优点
            {
                Node<T> node = this.Head;
                Node<T> nodeTmp = new Node<T>(item);
                if (node == null)
                {
                    this.Head = nodeTmp;
                }
                else
                {
                    nodeTmp.Next = node;
                    this.tHead = nodeTmp;
                }
            }
        }
        #region IListDS<T> 成员
        public int GetLength()
        {
            Node<T> node = new Node<T>();
            int count = 0;
            node = this.tHead;
            while (node != null)
            {
                count++;
                node = node.Next;
            }
            return count;
        }
        public void Insert(T item, int i)//i最小从1开始
        {
            Node<T> insertNode = new Node<T>(item, null);//实例化待添加的Node
            if (this.tHead == null && i == 1)
            {
                this.tHead = insertNode;
                return;
            }
            if (i < 1 || i > this.GetLength() || (this.tHead == null && i != 1))
            {
                Console.WriteLine("There are no elements in this linked list!");
                return;
            }
            int j = 1;
            Node<T> node = this.tHead;
            Node<T> nodeTmp;
            while (node != null && j < i)//循环结束时，保证node为第i个node
            {
                node = node.Next;
                j++;
            }
            nodeTmp = node.Next;//原来的单链表的第i+1个node
            node.Next = insertNode;//第i个node后的node修改为待插入的node
            insertNode.Next = nodeTmp;//待插入的node插入后，其后继node为原来链表的第i+1个node
        }
        public void Add(T item)//添加至尾部，时间复杂度为O(n)，如果添加至头部，则会节省循环的开销
        {
            Node<T> LastNode = new Node<T>(item, null);//实例化待添加的Node
            if (this.tHead == null)
            {
                this.tHead = LastNode;
            }
            else
            {
                Node<T> node = this.tHead;
                
                while (node.Next != null)
                {
                    node = node.Next;
                }
                node.Next = LastNode;
            }
            
        }
        public bool IsEmpty()
        {
            return this.tHead == null;
        }
        public T GetElement(int i)//设i最小从1开始
        {
            if (i < 1 || i > this.GetLength())
            {
                Console.WriteLine("The location is not right!");
                return default(T);
            }
            else
            {
                if (i == 1)
                {
                    return this.tHead.Data;
                }
                else
                {
                    Node<T> node = this.tHead;
                    int j = 1;
                    while (j < i)
                    {
                        node = node.Next;
                        j++;
                    }
                    return node.Data;
                }
            }
        }
        public void Delete(int i)//设i最小从1开始
        {
            if (i < 1 || i > this.GetLength())
            {
                Console.WriteLine("The location is not right!");
            }
            else
            {
                if (i == 1)
                {
                    Node<T> node = this.tHead;
                    this.tHead = node.Next;
                }
                else
                {
                    Node<T> node = this.tHead;
                    int j = 1;
                    while (j < i-1)
                    {
                        node = node.Next;
                        j++;
                    }
                    node.Next = node.Next.Next;
                }
            }
        }
        public void Clear()
        {
            this.tHead = null;//讲thead设为null后，则所有后继结点由于失去引用，等待GC自动回收
        }
        public int LocateElement(T item)//返回值最小从1开始
        {
            if (this.tHead == null)
            {
                Console.WriteLine("There are no elements in this linked list!");
                return -1;
            }
            Node<T> node = this.tHead;
            int i = 0;
            while (node != null)
            {
                i++;
                if (node.Data.Equals(item))//如果Data是自定义类型，则其Equals函数必须override
                {
                    return i;
                }
                node = node.Next;
            }
            Console.WriteLine("No found!");
            return -1;
        }
        public void Reverse()
        {
            if (this.tHead == null)
            {
                Console.WriteLine("There are no elements in this linked list!");
            }
            else
            {
                Node<T> node = this.tHead;
                if (node.Next == null)//如果只有头节点，则不作任何改动
                {
                }
                else
                {
                    Node<T> node1 = node.Next;
                    Node<T> node2;
                    while (node1 != null)
                    {
                        node2 = node.Next.Next;
                        node.Next = node2;//可以发现node始终未变，始终是原来的那个头节点
                        node1.Next = this.tHead;
                        this.tHead = node1;
                        node1 = node2;
                    }
                }
            }
        }
        #endregion
    }
    class Program
    {
        
        static void Main(string[] args)
        {
            
            /*测试单链表的清空
            lList.Clear();
            Node<int> n = new Node<int>();
            n = lList.Head;
            while (n != null)
            {
                Console.WriteLine(n.Data);
                n = n.Next;
            }
            Console.ReadLine();
             */
            /*测试单链表返回元素个数
            LinkedList<int> lList = new LinkedList<int>();
            lList.Add(3);
            Console.WriteLine(lList.GetLength());
            Console.ReadLine();
            */
            /*测试单链表插入
            LinkedList<int> lList = new LinkedList<int>();
            lList.Insert(0,1);
            lList.Add(1);
            lList.Add(2);
            lList.Add(3);
            lList.Add(4);
            lList.Insert(99,3);
            Node<int> n = new Node<int>();
            n = lList.Head;
            while (n != null)
            {
                Console.WriteLine(n.Data);
                n = n.Next;
            }
            Console.ReadLine();
            */
            /*测试单链表获取某位置的值
            LinkedList<int> lList = new LinkedList<int>();
            lList.Add(1);
            lList.Add(2);
            lList.Add(3);
            lList.Add(4);
            Console.WriteLine(lList.GetElement(1));
            Console.ReadLine();
             */
           /*测试单链表删除某位置的值
           LinkedList<int> lList = new LinkedList<int>();
           lList.Add(1);
           lList.Add(2);
           lList.Add(3);
           lList.Add(4);
           Node<int> n = new Node<int>();
           n = lList.Head;
           while (n != null)
           {
               Console.WriteLine(n.Data);
               n = n.Next;
           }
           Console.ReadLine();
           lList.Delete(2);
           Node<int> m = new Node<int>();
           m = lList.Head;
           while (m != null)
           {
               Console.WriteLine(m.Data);
               m = m.Next;
           }
           Console.ReadLine();
           */
             /*测试单链表按值查找元素位置
            LinkedList<int> lList = new LinkedList<int>();
            lList.Add(1);
            lList.Add(2);
            lList.Add(3);
            lList.Add(4);
            Console.WriteLine(lList.LocateElement(3));
            Console.ReadLine();
            */
            /*测试单链表Reverse操作（逆序）
            LinkedList<int> lList = new LinkedList<int>();
            lList.Add(1);
            lList.Add(2);
            lList.Add(3);
            lList.Add(4);
            lList.Add(5);
            Node<int> m = new Node<int>();
            m = lList.Head;
            while (m != null)
            {
                Console.WriteLine(m.Data);
                m = m.Next;
            }
            Console.ReadLine();
            lList.Reverse();
            Node<int> n = new Node<int>();
            n = lList.Head;
            while (n != null)
            {
                Console.WriteLine(n.Data);
                n = n.Next;
            }
            Console.ReadLine();
            */
            /*测试单链表从头部添加元素
            LinkedList<int> lList = new LinkedList<int>();
            lList.Add(1,AddPosition.Head);
            lList.Add(2, AddPosition.Head);
            lList.Add(3, AddPosition.Head);
            lList.Add(4, AddPosition.Head);
            lList.Add(5, AddPosition.Head);
            Node<int> m = new Node<int>();
            m = lList.Head;
            while (m != null)
            {
                Console.WriteLine(m.Data);
                m = m.Next;
            }
            Console.ReadLine();
            */
            /*测试对单链表清除重复元素操作（返回另一链表）。这个例子中避免使用Add（）方法，因为每个Add（）都要从头到尾进行遍历，不适用Add（）方法
             就要求对目标链表的最后一个元素实时保存。另一种避免的方法在于从头部Add，但这样的最终结果为倒序
            LinkedList<int> lList = new LinkedList<int>();//原链表
            LinkedList<int> lList2 = new LinkedList<int>();//保存结果的链表
            lList.Add(1);
            lList.Add(2);
            lList.Add(1);
            lList.Add(3);
            lList.Add(3);
            lList.Add(4);
            lList.Add(5);
            Node<int> m = new Node<int>();
            m = lList.Head;
            while (m != null)
            {
                Console.WriteLine(m.Data);
                m = m.Next;
            }
            Console.ReadLine();
            Node<int> node1 = lList.Head;//标识原链表的当前要参与比较大小的元素，即可能放入链表2中的元素
            Node<int> node2;//标识结果单链表的最后一个元素，避免使用Add函数造成多次遍历
            Node<int> node3;//对node1的后继进行暂时保存，并最终付给node1
            node3 = node1.Next;
            lList2.Head = node1;//链表1的头结点肯定要加入链表2
            node2 = lList2.Head;//node2表示链表2的最后一个元素，此时最后一个元素为头结点
            node2.Next = null;//由于是把node1赋给了链表2的头结点，必须把它的后续结点设为null，否则会一起带过来
            node1 = node3;//如果没有node3暂存node1的后继，对lList2.Head后继赋为null的就会同时修改node1的后继，因为两者指向同一块内存
            while (node1 != null)
            {
                //在iList2中比较大小
                Node<int> tmp = lList2.Head;
                if (node1.Data.Equals(tmp.Data))
                {
                    node1 = node1.Next;
                    continue;//若相等，则node1向后移一位，重新计算
                }
                else
                {
                    Node<int> tmp2 = tmp;
                    tmp = tmp.Next;//tmp标识链表2的用于循环的节点，与node比较
                    if (tmp == null)//当链表2中现有元素与node1都不相等时
                    {
                        node3 = node1.Next;
                        node2.Next = node1;
                        node2 = node1;
                        node2.Next = null;
                        node1 = node3;
                        continue;
                    }
                    while (tmp != null)//tmp不为null时，一直循环到它为null
                    {
                        if (node1.Data.Equals(tmp.Data))
                        {
                            node1 = node1.Next;
                        }
                        else
                        {
                            tmp2 = tmp;
                            tmp = tmp.Next;
                            if (tmp == null)
                            {
                                node3 = node1.Next;
                                node2.Next = node1;
                                node2 = node1;
                                node2.Next = null;
                                node1 = node3;
                            }
                        }
                    }
                }
            }
            //输出清除重复处理后的数组
            Node<int> n = new Node<int>();
            n = lList2.Head;
            while (n!= null)
            {
                Console.WriteLine(n.Data);
                n = n.Next;
            }
            Console.ReadLine();
            */
        }
    }
}