软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

C#数据结构之双链表介绍

据说单链表没有回路,那么双链表也出现了,既包括后继指针,又加入了前驱指针,某个元素可以寻找他上面一个元素,也可以寻找到下一个元素。当然双链表也是链表的一种。

物理存储结构:不一定是连续的存储区域

逻辑存储结构:逻辑上存储是连续的

使用场景:跟单链表一样,适用于对数据的大量新增和删除元素,对访问元素无要求,预先无法确定数据量的程序

首先创建存储元素结构

///     /// 双链表    ///     class DLinkList    {        public string data;        //上一个节点        public DLinkList prior;        //下一个节点        public DLinkList next;    }

创建操作类和表头

///     /// 双链表操作    ///     class DLinkListClass    {        //创造双链表的头元素        public DLinkList dhead = new DLinkList();}

插入数据:同样跟单链表一样有两种方式插入,时间空间复杂度为:O(n)

#region 建立双链表-头插法 O(n)        public void CreateListFrist(string[] split)        {            DLinkList s;            dhead.next = null;            for (int i = 0; i < split.Length; i++)            {                s = new DLinkList();                s.data = split[i];                //新增的这一级找到以前head指向的下一级,作为next                s.next = dhead.next;                //头部的下一级的prior以前指向的是head,那么现在这级的prior先找到新插入的元素                if (dhead.next!=null)                {                    s.next.prior = s;                }                //head的下一级指向新增项                dhead.next = s;                //新增项的prior上一级指向head                s.prior = dhead;            }        }        #endregion        #region 建立双链表-尾插法 O(n)        public void CreateListEnd(string[] split)        {            DLinkList p, s;            p = dhead;            for (int i = 0; i < split.Length; i++)            {                //插入新项                s = new DLinkList();                s.prior = p;                s.data = split[i];                //尾部的下一级指向新增项                p.next = s;                //新增项转换成尾部                p = s;            }            p.next = null;        }        #endregion

输出双链表,时间空间复杂度为:O(n)

#region 输出双链表表 O(n)        public string DispList()        {            string str = "";            DLinkList p;            p = dhead.next;            while (p != null)            {                str += p.data + " ";                p = p.next;            }            return str;        }        #endregion

输出双链表的长度,时间空间复杂度为:O(n)

#region 双链表的长度 O(n)        public int ListLength()        {            int i = 0;            DLinkList p;            p = dhead;            while (p.next != null)            {                i++;                p = p.next;            }            return i;        }        #endregion

获取元素item项的值,时间空间复杂度为:O(n)

#region 获取第item项的值 O(n)        public bool GetElem(int item, ref string e)        {            DLinkList p = dhead;            int j = 0;            if (item < 1)            {                return false;            }            //循环找到item的位置            while (j < item && p != null)            {                j++;                p = p.next;            }            //判断item位置是否存在            if (p == null)            {                return false;            }            else            {                e = p.data;                return true;            }        }        #endregion

根据元素值获取位置,时间空间复杂度为:O(n)

#region 根据元素值获取item位置 O(n)        public int LoateElem(string e)        {            DLinkList p = dhead.next;            int item = 0;            //开始找元素里面的data与e相等            while (p != null && p.data != e)            {                //计数                item++;                //下一个元素                p = p.next;            }            //如果双链表没有元素或者没有找到与双链表匹配的值,输出为0            if (p == null)            {                return 0;            }            else            {                return item;            }        }        #endregion

指定位置插入元素,时间空间复杂度为:O(n)

1.这里先找到插入元素位置,获取前一个元素

2.将这个元素的后继地址给新增元素的后继地址

3.然后把下一个元素的前驱地址换成新元素的地址

4.然后将新元素的前驱地址换成前一个元素的地址

5.前一个元素的后继地址换成新元素地址

#region 在item插入值 O(n)          public bool ListInsert(int item, string values)          {              DLinkList p, s;              p = dhead;              int j = 0;              while (j<item-1 && p!=null)              {                  p = p.next;                  j++;              }              if (p==null)              {                  return false;              }              else              {                  //创造一个新增元素                  s = new DLinkList();                  s.data = values;                  //新增项找到下一级                  s.next = p.next;                  //新增项的下一级的prior找到新增元素                  if (s.next!=null)                  {                      s.next.prior = s;                  }                  //新增项的prior上一级                  s.prior = p;                  //新增项上一级的next                  p.next = s;                  return true;              }          }          #endregion  

删除定点的元素,时间空间复杂度为:O(n)

1.寻找到这个元素的位置

2.这里先找到删除元素的上一级,这个上一级的后继地址指向删除元素的下一级元素

3.然后这个上一级的前驱元素指向删除元素的上一级

#region 删除item项          public bool ListDelete(int item, ref string values)          {              DLinkList p, s;              p = dhead;              int j = 0;              while (j<item-1 && p!=null)              {                  p = p.next;                  j++;              }              if (p==null || p.next==null)              {                  return false;              }              else              {                  s = p.next;                  values = s.data;                  //删除项的上一级next寻找删除项下一级                  p.next = s.next;                  //删除项的下一级的prior寻找删除项的上一级                  if (p.next != null)                  {                      s.next.prior = p;                  }                  //释放空间                  s = null;                  return true;              }          }          #endregion  

结论:双链表相比顺序表新增删除省了不少事,不用每次都要重新操作后面的移位问题,但是相对于链表内存消耗多了指针域

优点:没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。插入和删除元素速率高。

缺点:占用额外的空间以存储指针(浪费空间)。随机存取元素速率低。双链表要找一个数,必须要从表头开始找起,存取率元素的速率非常的低。

循环双链表,操作跟双链表一样,只是注意尾元素的后继不是指向空地址,而是指向head头元素,头元素的前驱地址指向的是尾元素的地址,这里的头元素在循环链表中做了一个参照物的作用,如果你不知道头元素在哪里,可能操作的时候会出现一直循环下去,最终会导致程序崩溃。