单链表的实现

//最近动手把单链表的操作实现了一遍:

//单链表中存放的结点类:

    public class Node<T>
    {
        private T data;     //数据域
        private Node<T> next; //引用域


        //构造函数
        public Node(T val,Node<T> p)
        {
            data = val;
            next = p;
        }


        //构造函数
        public Node(T val)
        {
            data = val;
        }


        //构造函数
        public Node(Node<T> p)
        {
            next = p;
        }

        //构造函数
        public Node()
        {
            data = default(T);
            next = null;
        }

        //属性 data
        public T Data
        {
            get { return data; }
            set { data = value; }
        }

        //属性 next
        public Node<T> Next
        {
            get { return next; }
            set { next = value; }
        }
    }

//单链表类主要属性是头引用 (头结点),所实现的接口如下:

 public interface IListDS<T>
    {
        //获取表的长度
        int GetLength();
        //清空表
        void Clear();
        //判断表是否为空
        bool IsEmpty();
        //向表尾追加
        void Append(T item);
        //在指定位置插入元素
        void Insert(T item, int i);
        //删除指定位置元素
        T Delete(int i);
        //获得在指定位置的元素
        T GetElem(int i);
        //获取元素在表中的位置
        int Locate(T value);
    }

//具体的单链表类如下:

public class LinkList<T> : IListDS<T>
    {

        //头引用
        public Node<T> head;

        //头引用属性
        public Node<T> Head
        {
            get
            {
                return head;
            }
            set
            {
                head = value;
            }
        }


        //构造函数
        public LinkList()
        {
            head = null;
        }
        
        //实现接口方法...

    
}

//具体的方法实现:

1.//Is Empty //GetLength()//Clear()

public bool IsEmpty()
{
     return this.head == null;  
}

public int GetLength()  
{
      if(IsEmpty())
      {
          return -1;
      }
      Node<T> p = head;  
      int j =1;
      while(p.Next!=null)
       {
             p=p.Next;
             ++j;
       }
       return j;
}    

public void Clear()
{
　　this.head = null;
}

//2.Append 向链表末尾追加结点

public void Append(T item)
{
　　Node<T> target = new Node<T>(item);
　　if(IsEmpty())
　　{
　　　　this.head = target;
　　　　return;
　　}
　　Node<T> p = head;
　　while(p.Next!=null)
　　{
　　　　p= p.Next;
　　}
　　p.Next = target;
}

//3.Insert 插入结点有两种方式在指定位置之前插入和在指定位置之后插入

　　//3.1 在指定位置之前插入:

        public void Insert(T item, int i)
        {
            //    throw new NotImplementedException();
            if (IsEmpty() || i < 1)
            {
                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>();

            //r 存储第i个结点的前一个结点
            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;
            }

        }

　　//3.2在指定位置之后插入

 1 　　　　　public void InsertAfter(T item,int i)
 2         {
 3             if (IsEmpty() || i < 1)
 4             {
 5                 return;
 6             }
 7 
 8             //首先找到第i个结点  和第i+1个结点(i.Next)
 9 
10             Node<T> p = head;
11             int j = 1;
12 
13             while (p.Next != null && j < i)
14             {
15                 p = p.Next;
16                 ++j;
17             }
18 
19 
20             if (j == i )
21             {
22                 Node<T> target = new Node<T>(item);
23                 target.Next = p.Next;
24                 p.Next = target;
25             }
26 
27         }

//4.删除第i个结点

 1  　　    public T Delete(int i)
 2         {
 3             //
 4             //throw new NotImplementedException();
 5             if (IsEmpty() || i < 0)
 6             {
 7                 return default(T);
 8             }
 9 
10             //记录到第i个结点
11             Node<T> p = head;
12 
13             //记录第i-1个结点
14             Node<T> q = new Node<T>();
15 
　　　　　　
　　　　　　　　 if(i==1)
　　　　　　　　　　{
　　　　　　　　　　　　q = head;
                     head = q.Next;
　　　　　　　　　　　　return q.Data;
　　　　　　　　　　}



16             int j = 1;
17             while (p.Next != null&& j<i)
18             {
19                 q = p;
20                 p = p.Next;
21                 ++j;
22             }
23 
24             if (j == i)
25             {
26                 q.Next = p.Next;
27                 return p.Data;
28             }
29 
30             return default(T);
31 
32         }

//5.取表元

public T GetElem(int i)
{
     if(IsEmpty()||i<1)
     {
        return default(T);
     }        
      if(i==1)
       {
          return head.Data;
       }
       Node<T> p = head;
       int j=1;
       while(p.Next!=null && j<i)       //先找到指定位置i的结点
       {
           p=p.Next;
           ++j;
       }
       if(j==i)
       {
           return p.Data;
       }
       return default(T);
}

//6.Locate //获取元素在表中的位置

public int Locate(T item)
{
      if(IsEmpty())
      return -1;
      Node<T> p = head;
      int j =1;
      while(p.Next!=null)
      {
           if(p.Data.Equals(item))
           break;
           p=p.Next;
           ++j;
      }    
      return j;
}