C#数据结构-静态链表_C

概述对于双向链表中的节点，都包括一个向前、向后的属性器用于指向前后两个节点，对于引用类型，对象存储的是指向内存片段的内存指针，那么我们可以将其简化看作向前向后的两个指针。现在我们将引用类型替换为值类型i

对于双向链表中的节点，都包括一个向前、向后的属性器用于指向前后两个节点，对于引用类型，对象存储的是指向内存片段的内存指针，那么我们可以将其简化看作向前向后的两个指针。

现在我们将引用类型替换为值类型int，将链用数组代替，向后的指针替换为数组的下标，那么此时的链我们称为静态链表(或者说是单向静态链表)。

不多说，直接上代码（代码已做注解）

    public class Node<T>    {        public T data { get; set; }        int next { public Node(T item)        {            data = item;        }    }

    class Staticlink<T>    {        int count { set; } = 0;        public Node<T>[] link { ; }        int minSize { 10int extendSize { 10;//扩容步长         Staticlink()        {            第一个节点为空节点，不存储内容，同时，第一个节点的next存放备用链表的第一个节点（备用链表——数组内可以用于存储内容的处于空值时的节点连接成的表）            初始化，静态链表的长度为10；            link = new Node<T>[minSize];            for (int i = 0; i < minSize; i++)            {                i=0时，由于链表为空，则备用链表的第一个节点也就是1                link[i] = new Node<T>(default(T));                link[i].next = i + 1;            }            初始化，静态链表的结尾next 指向第一个节点（除头节点外）            link[minSize - 1].next = ;            count++;        }        private int Malloc()        {            取得静态链表-备用链表中的第一个节点（取出待用，存储内容）            int i = link[].next;            if (i > 同时，移除备用链表的第一个节点，                link[0].next = link[i].next;                取到链表的最后一个元素时，扩容。                if (i >= minSize - )                {                    todo 不翻倍扩容，采用定值步长扩容~                    todo 暂不实现                }            }            return i;        }        /// <summary>        /// 在链表的结尾附加        </summary>        <param name="node"></param>        voID Append(T node)        {            Insert(count,node);        }         指定位置插入节点        <param name="index"></param>        voID Insert( index,T node)        {            要插入的节点需要在链表的范围内            if (index > count || index < )                throw new IndexOutOfRangeException("索引超出界限");            由于时插入节点，所以此处我们需要从备用链表取出一个空节点。            int maxIndex = Malloc();            int k = minSize - ;             Node<T> newNode = new Node<T>(node);创建一个节点            if (count == )                newNode.next = ;            else             {                取链表最后一个节点的next；                1; i <= index -1; i++)                {                    k = link[k].next;                }                newNode.next = link[k].next;                link[k].next = maxIndex;            }            link[maxIndex] = newNode;            count++;        }         根据索引删除        <param name="index"></param>        voID Del( index)        {            去除头节点，并判断索引要在链表范围内            if (index < 1 || index > count)                通过链取得前一个节点 -时间复杂度O(n)            int j = 1; j <= index - 1; j++)            {                k = link[k].next;            }            int beforeNodeNext = link[k].next;获取前一个节点的next;            link[k].next = link[beforeNodeNext].next;跳过要删除的节点            link[beforeNodeNext].next = link[0].next;将释放除来的节点接入备用链            link[0].next = beforeNodeNext;将当前释放的节点放入到备用的第一个节点。-待用            count-- 展示链节点        </summary>         showAll()        {            1; i <= count; i++)            {                Console.Writeline($index:{link[i].next},data:{link[i].data});            }        }　　}

测试：

 class Program    {        static voID Main(string[] args)        {            Staticlink<string> link = new Staticlink<string>();            link.Append(第一位);            link.Append(第二位第三位);            link.Insert(2,第四位，插入到二的位置第五位第六位第七位);            link.Del(6);            link.showAll();            Console.Readline();        }    }