单链表是什么？

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

• 逻辑结构示意图
  

• 节点结构示意图
  

代码实现

• 定义链表节点类

/// <summary>
/// 链表节点
/// </summary>
public class ListNode<T>
{
    public T data;              // 存储的数据
    public ListNode<T> next;    // 下一个节点的引用

    public ListNode(){}
    public ListNode(T data){
        this.data = data;
    }

    public ListNode(T data,ListNode<T> next) : this(data){
        this.next = next;
    }
}

---

• 实现链表类，封装对链表的基本操作

    /// <summary>
    /// 单链表类（实现链表的一些基本操作）
    /// </summary>
    public class SingleLinkedList<T>
    {
        public ListNode<T> head = null; // 表头节点
        private int count = 0;

        public int Count{
            get{return count;}
        }

        /// <summary>
        /// 根据索引获取元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T Get(int index){
            if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
            if(index == 0) return head.data;
            return GetPrevNode(index).next.data;
        }

        /// <summary>
        /// 设置索引位置上的元素
        /// </summary>
        /// <param name="index"></param>
        /// <param name="newData"></param>
        public void Set(int index, T newData){
            if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
            if(index == 0) head.data = newData;
            GetPrevNode(index).next.data = newData;
        }

        /// <summary>
        /// 添加到链表尾部
        /// </summary>
        /// <param name="data"></param>
        public void Append(T data){
            ListNode<T> newNode = new ListNode<T>(data);
            if(head == null){
                head = newNode;
            }else{
                ListNode<T> tempNode = head;
                while(tempNode.next != null){
                    tempNode = tempNode.next;
                }
                tempNode.next = newNode;
            }
            count++;
        }

        /// <summary>
        /// 添加到指定的索引位置
        /// </summary>
        /// <param name="index"></param>
        /// <param name="data"></param>
        public void Insert(int index,T data){
            if(index < 0 || index > count) throw new IndexOutOfRangeException("链表索引越界");
            ListNode<T> newNode = new ListNode<T>(data);
            if(index == 0){
                newNode.next = head;
                head = newNode;
            }else{
                ListNode<T> prevNode = GetPrevNode(index);
                 newNode.next = prevNode.next;
                 prevNode.next = newNode;
            }
            count++;
        }

        /// <summary>
        /// 获取元素所在的索引
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public int IndexOf(T data){
            ListNode<T> tempNode = head;
            for (int i = 0; i < count; i++) {
                if(tempNode.data.Equals(data))
                    return i;
                tempNode = tempNode.next;
            }
            return -1;
        }

        /// <summary>
        /// 移除元素
        /// </summary>
        /// <param name="data"></param>
        public void Remove(T data){
            int index = IndexOf(data);
            if(index != -1){
                RemoveAt(index);
            }
        }

        /// <summary>
        /// 移除索引位置上的元素,并返回该元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T RemoveAt(int index){
            if(index < 0 || index >= count) throw new IndexOutOfRangeException("链表索引越界");
            T removeData = default(T);
            if(index == 0){
                removeData = head.data;
                head = head.next;

            }else{
                ListNode<T> prevNode = GetPrevNode(index);
                ListNode<T> currentNode = prevNode.next;
                removeData = currentNode.data;
                prevNode.next = currentNode.next;
            }
            count--;
            return removeData;
        }

        /// <summary>
        /// 是否为空链表表
        /// </summary>
        public bool IsEmpty{
            get{return count == 0;}
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        public void Clear(){
            head = null;
            count = 0;
        }

        /// <summary>
        /// 重写ToString方法，方便查看链表信息
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.AppendFormat("Count={0}\n",count);
            sb.Append("[");
            for (int i = 0; i < count; i++) {
                if(i == count - 1)
                    sb.Append(Get(i).ToString());
                else
                    sb.AppendFormat("{0}, ",Get(i));
            }
            sb.Append("]");
            return sb.ToString();
        }

        /// <summary>
        /// 获取索引位置的上一个节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private ListNode<T> GetPrevNode(int index){
            ListNode<T> tempNode = head;
            for(int i = 0; i < index - 1; i++){
                tempNode = tempNode.next;
            }
            return tempNode;
        }

    }

测试

    class Program
    {
        public static void Main(string[] args)
        {
            SingleLinkedList<int> list = new SingleLinkedList<int>();
            for(int i = 0; i < 10; i++){
                list.Append(i);
            }
            Console.WriteLine(list);
            list.Set(9,100);
            Console.WriteLine(list);
            list.RemoveAt(9);
            list.RemoveAt(7);
            list.Insert(3,99);
            Console.WriteLine(list);
            list.Remove(99);
            Console.WriteLine(list);
            Console.ReadKey(true);
        }
    }

---