数据结构-双向链表&双向循环链表

女爷i 2021-10-01 00:40 697阅读 0赞

借图：http://www.cnblogs.com/skywang12345/p/3561803.html\#a33

双向链表

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

922236-20171220110004678-643077430.png

922236-20171220110011240-853997173.png

实现：接口

ContractedBlock.gif ExpandedBlockStart.gif

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  7. namespace _001_线性表
  8. {
  9.     interface IListDS<T>
  10.     {
  11.         int GetLength();
  12.         void Clear();
  13.         bool IsEmpty();
  14.         void Add(T item);
  15.         void Insert(T item, int index);
  16.         T Delete(int index);
  17.         T this[int index] { get; }
  18.         T GetEle(int index);
  19.         int Locate(T value);
  21.     }
  22. }

双向节点：

ContractedBlock.gif ExpandedBlockStart.gif

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  6. namespace _001_线性表
  7. {
  8.     /// <summary>
  9.     /// 双向节点
  10.     /// </summary>
  11.     /// <typeparam name="T"></typeparam>
  12.     class DbNode<T>
  13.     {
  14.         private T data;
  15.         private DbNode<T> prev;
  16.         private DbNode<T> next;
  18.         public DbNode(T val,DbNode<T> p,DbNode<T> n)
  19.       {
  20.           this.data = val;
  21.           this.prev = p;
  22.           this.next = n;
  23.       }
  24.         public DbNode(DbNode<T> p)
  25.         {
  26.             next = p;
  27.         }
  28.         public DbNode(T val)
  29.         {
  30.             data = val;
  31.             next = null;
  32.             prev = null;
  33.         }
  34.         public DbNode()
  35.         {
  36.             data = default(T);
  37.             next = null;
  38.             prev = null;
  39.         }
  40.         public T Data
  41.         {
  42.             get { return data; }
  43.             set { data = value; }
  44.         }
  45.         public DbNode<T> Prev
  46.         {
  47.             get { return prev; }
  48.             set { prev = value; }
  49.         }
  50.         public DbNode<T> Next
  51.         {
  52.             get { return next; }
  53.             set { next = value; }
  54.         }
  55.         public void SetNode(DbNode<T> pre,DbNode<T> next)
  56.         {
  57.             this.prev = pre;
  58.             this.next = next;
  59.         }
  63.     }
  64. }

双向链表：

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  6. namespace _001_线性表
  7. {
  8.     /// <summary>
  9.     /// 双向链表
  10.     /// </summary>
  11.     /// <typeparam name="T"></typeparam>
  12.     class DoubleLink<T>:IListDS<T>
  13.     {
  14.         #region IListDS<T> 成员
  16.         private DbNode<T> _linkHead;
  17.         public DoubleLink()
  18.         {
  19.             _linkHead = null;
  20.         }
  22.         public int GetLength()
  23.         {
  24.             if (IsEmpty()) return 0;
  25.             DbNode<T> temp = _linkHead;
  26.             int length = 1;
  27.             while (temp.Next != null)
  28.             {
  29.                  length++;
  30.                  temp = temp.Next;
  31.             }
  32.             return length;
  33.         }
  35.         public void Clear()
  36.         {
  37.             _linkHead = null;
  38.         }
  40.         public bool IsEmpty()
  41.         {
  42.             return _linkHead == null;
  43.         }
  45.         /// <summary>
  46.         /// 在双向链表的尾端添加一个新数据
  47.         /// </summary>
  48.         /// <param name="item"></param>
  49.         public void Add(T item)
  50.         {
  51.             DbNode<T> newNode = new DbNode<T>(item);
  52.             if (IsEmpty())
  53.             {
  54.                 _linkHead = newNode;
  55.             }
  56.             else
  57.             {
  58.                 DbNode<T> preNode = GetListItem(this.GetLength() - 1);
  59.                 newNode.Prev = newNode;
  60.                 preNode.Next = newNode.Prev;
  61.                 newNode.Prev = preNode;
  62.             }
  63.         }
  65.         /// <summary>
  66.         /// 获取指定位置的双向链表项目，头项从0开始
  67.         /// </summary>
  68.         public DbNode<T> GetListItem(int index)
  69.         {
  70.             if (index < 0)
  71.                 throw new Exception("索引不能小于0");
  72.             if (index > this.GetLength() - 1)
  73.                 throw new Exception("索引超出列表总长度");
  74.             DbNode<T> temp = _linkHead;
  75.             for (int i = 0; i < index; i++)
  76.             {
  77.                 temp = temp.Next;
  78.             }
  79.             return temp;
  80.         }
  82.         /// <summary>
  83.         /// 在双向链表指定的位置插入一个新项
  84.         /// </summary>
  85.         public void Insert(T item, int index)
  86.         {
  87.             if (index < 0)
  88.                 throw new Exception("插入位置不能小于0");
  89.             if (index > this.GetLength() + 1)
  90.                 throw new Exception("插入位置超出链表长度");
  91.             DbNode<T> newNode = new DbNode<T>(item);
  92.             if (index == 0)
  93.             {
  94.                 newNode.Next = _linkHead;
  95.                 _linkHead = newNode;
  96.             }
  97.             else
  98.             {
  99.                 DbNode<T> preNode = GetListItem(index - 1); //要插入位置前面的节点
  100.                 DbNode<T> atfNode = GetListItem(index);//要插入位置后面的节点
  101.                 preNode.Next = new DbNode<T>(item, preNode, atfNode);
  102.             }
  103.         }
  106.         /// <summary>
  107.         /// 删除指定位置的双向链表项
  108.         /// </summary>
  109.         /// <param name="index"></param>
  110.         public T Delete(int index)
  111.         {
  112.             if (index < 0)
  113.                 throw new Exception("删除位置不能小于0");
  114.             if (index > this.GetLength() - 1)
  115.                 throw new Exception("插入位置超出链表长度");
  117.             T data = default(T);
  118.             if (index == 0)
  119.             {
  120.                 data = _linkHead.Data;
  121.                 _linkHead = _linkHead.Next;
  122.                 if(!IsEmpty())
  123.                     this._linkHead.Prev = null;
  124.             }
  125.             else
  126.             {
  127.                 DbNode<T> DelNode = GetListItem(index); //取到要删除的节点
  128.                 data = DelNode.Data;
  129.                 DbNode<T> preNode = DelNode.Prev;
  130.                 DbNode<T> nextNode = DelNode.Next;
  131.                 preNode.Next = nextNode;
  132.                 nextNode.Prev = preNode;
  133.             }
  134.             return data;
  135.         }
  137.         public T this[int index]
  138.         {
  139.             get { return GetEle(index); }
  140.         }
  142.         public T GetEle(int index)
  143.         {
  144.             DbNode<T> temp = _linkHead;
  145.             for (int i = 0; i < index; i++)
  146.             {
  147.                 temp = temp.Next;
  148.             }
  149.             return temp.Data;
  150.         }
  152.         public int Locate(T value)
  153.         {
  154.             DbNode<T> temp = _linkHead;
  155.             if (IsEmpty())
  156.             {
  157.                 return -1;
  158.             }
  159.             else
  160.             {
  161.                 int index = 0;
  162.                 while (true)
  163.                 {
  164.                     if (!temp.Data.Equals(value))
  165.                     {
  166.                         if (temp.Next != null)
  167.                         {
  168.                             index++;
  169.                             temp = temp.Next;
  170.                         }
  171.                         else
  172.                         {
  173.                             break;
  174.                         }
  175.                     }
  176.                     else
  177.                     {
  178.                         return index;
  179.                     }
  180.                 }
  181.                 return -1;
  182.             }
  183.         }
  184.         #endregion
  185.     }
  186. }

双向循环链表

从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双链表的示意图如下：

632293-20170306150003297-951612143.png

表头为空，表头的后继节点为”节点10”(数据为10的节点)；”节点10”的后继节点是”节点20”(数据为10的节点)，”节点20”的前继节点是”节点10”；”节点20”的后继节点是”节点30”，”节点30”的前继节点是”节点20”；…；末尾节点的后继节点是表头。

双链表删除节点

632293-20170306150039609-1719195275.png

删除”节点30”
删除之前：”节点20”的后继节点为”节点30”，”节点30” 的前继节点为”节点20”。”节点30”的后继节点为”节点40”，”节点40” 的前继节点为”节点30”。
删除之后：”节点20”的后继节点为”节点40”，”节点40” 的前继节点为”节点20”。

双链表添加节点

632293-20170306150105453-2068434988.png

在”节点10”与”节点20”之间添加”节点15”
添加之前：”节点10”的后继节点为”节点20”，”节点20” 的前继节点为”节点10”。
添加之后：”节点10”的后继节点为”节点15”，”节点15” 的前继节点为”节点10”。”节点15”的后继节点为”节点20”，”节点20” 的前继节点为”节点15”。

实现：

ContractedBlock.gif ExpandedBlockStart.gif

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  7. namespace _001_线性表
  8. {
  9.     /// <summary>
  10.     /// 双向循环链表
  11.     /// </summary>
  12.     /// <typeparam name="T"></typeparam>
  13.     class DoubleLoopLink<T> : IListDS<T>
  14.     {
  15.         private DbNode<T> _linkHead;
  16.         public T this[int index] =>GetEle(index);
  18.         public void Add(T item)
  19.         {
  20.             DbNode<T> newNode = new DbNode<T>(item, null, null);
  21.             if (IsEmpty())
  22.             {
  23.                 _linkHead = newNode;
  24.                 _linkHead.Prev = _linkHead;
  25.                 _linkHead.Next = _linkHead;
  26.             }
  27.             else
  28.             {
  29.                 DbNode<T> preNode = _linkHead;
  30.                 while (preNode.Next != _linkHead)
  31.                 {
  32.                     preNode = preNode.Next;
  33.                 }
  34.                 preNode.Next = newNode;//链表的尾部 的后指针  指向新的节点
  35.                 newNode.SetNode(preNode, _linkHead);     
  36.                 _linkHead.Prev = newNode; //头部的 前指针 指向 新的尾部
  37.             }
  38.         }
  40.         public void Clear()
  41.         {
  42.             _linkHead = null;
  43.         }
  45.         public T Delete(int index)
  46.         {
  47.             T data = default(T);
  48.             if (IsEmpty())
  49.                 throw new Exception("链表为空，没有可清除的项");
  50.             if (index < 0 || index > this.GetLength() - 1)
  51.                 throw new Exception("给定索引超出链表长度");
  53.             DbNode<T> preNode = _linkHead;
  54.             if (index == 0)
  55.             {
  56.                 while (preNode.Next != _linkHead)
  57.                 {
  58.                     preNode = preNode.Next;
  59.                 }
  60.                 this._linkHead = _linkHead.Next;
  61.                 this._linkHead.Prev = preNode;
  62.                 data = preNode.Next.Data;
  63.                 preNode.Next = this._linkHead;
  64.             }
  65.             else
  66.             {
  67.                 for (int i = 1; i < index - 1; i++)
  68.                 {
  69.                     preNode = preNode.Next;
  70.                 }
  71.                 //看图比较好理解
  72.                 DbNode<T> aftNode = preNode.Next.Next; //要删除的节点  后面的节点
  73.                 preNode.Next = aftNode;//要删除节点的前面节点 的后指针 指向  要删除的节点  后面的节点
  74.                 aftNode.Prev = preNode; //要删除的节点 前面的节点  指向  要删除节点的前面节点    
  75.             }
  76.             return data;
  77.         }
  79.         public T GetEle(int index)
  80.         {
  81.             DbNode<T> temp = _linkHead;
  82.             for (int i = 0; i < index; i++)
  83.             {
  84.                 temp = temp.Next;
  85.             }
  86.             return temp.Data;
  87.         }
  89.         public int GetLength()
  90.         {
  91.             if (IsEmpty()) return 0;
  92.             DbNode<T> temp = _linkHead;
  93.             int length = 1;
  94.             while (temp.Next != _linkHead)
  95.             {
  96.                 length++;
  97.                 temp = temp.Next;
  98.             }
  99.             return length;
  100.         }
  101.         /// <summary>
  102.         /// 插入
  103.         /// </summary>
  104.         /// <param name="item"></param>
  105.         /// <param name="index"></param>
  106.         public void Insert(T item, int index)
  107.         {
  108.             if (IsEmpty())
  109.                 throw new Exception("数据链表为空");
  110.             if (index < 0 || index > this.GetLength())
  111.                 throw new Exception("给定索引超出链表长度");
  113.             DbNode<T> newNode = new DbNode<T>(item);
  114.             DbNode<T> preNode = _linkHead;
  115.             if (index == 0) //等于零  先找到 链表中 head的前一个节点 这个节点连接 head
  116.             {
  117.                 while (preNode.Next != _linkHead)
  118.                 {
  119.                     preNode = preNode.Next;
  120.                 }
  121.                 preNode.Next = newNode;
  122.                 newNode.SetNode(preNode, _linkHead);
  123.                 _linkHead.Prev = newNode;
  124.                 return;
  125.             }
  126.             else
  127.             {
  128.                 for (int i = 1; i < index - 1; i++)
  129.                 {
  130.                     preNode = preNode.Next;
  131.                 }
  132.                 //preNode要插入位置的前节点
  133.                 DbNode<T> atfNode = preNode.Next;//要插入节点的后节点
  134.                 preNode.Next = newNode; //后指针 连上新节点
  135.                 newNode.SetNode(preNode,atfNode);
  136.                 atfNode.Prev = newNode;//要插入节点的后节点 连上 新节点
  137.             }
  138.         }
  139.         public bool IsEmpty()
  140.         {
  141.             return _linkHead == null;
  142.         }
  144.         public int Locate(T value)
  145.         {
  146.             if (IsEmpty())
  147.                 throw new Exception("链表为空");
  148.             DbNode<T> preNode = _linkHead;
  149.             int index = 0;
  150.             while (true)
  151.             {
  152.                 if (!preNode.Data.Equals(value))
  153.                 {
  154.                     if (preNode.Next != _linkHead)
  155.                     {
  156.                         index++;
  157.                         preNode = preNode.Next;
  158.                     }
  159.                     else
  160.                     {
  161.                         break;
  162.                     }
  163.                 }
  164.                 else
  165.                 {
  166.                     return index;
  167.                 }
  168.             }
  169.             return -1;
  170.         }
  171.     }
  172. }

基本的链表大概就是这样了。

转载于:https://www.cnblogs.com/rongweijun/p/8072677.html

发表评论

表情：
评论列表 （有 0 条评论，697人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构-链表-双向链表

    数据结构-链表-双向链表 单向链表和环形链表都是属于拥有方向性的链表，只能单向遍历，如果由于某种原因造成了某个连接断裂，那后面的链表数据便会遗失而无法复原。所以，我们可以

    小鱼儿小鱼儿/ 0 赞/ 50 阅读