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

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

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

## **双向链表** ##

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

**![922236-20171220110004678-643077430.png][]**

![922236-20171220110011240-853997173.png][]

实现：接口

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        interface IListDS<T>
        {
            int GetLength();
            void Clear();
            bool IsEmpty();
            void Add(T item);
            void Insert(T item, int index);
            T Delete(int index);
            T this[int index] { get; }
            T GetEle(int index);
            int Locate(T value);
    
        }
    }

双向节点：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace _001_线性表
    {
        /// <summary>
        /// 双向节点
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class DbNode<T>
        {
            private T data;
            private DbNode<T> prev;
            private DbNode<T> next;
    
            public DbNode(T val,DbNode<T> p,DbNode<T> n)
          {
              this.data = val;
              this.prev = p;
              this.next = n;
          }
            public DbNode(DbNode<T> p)
            {
                next = p;
            }
            public DbNode(T val)
            {
                data = val;
                next = null;
                prev = null;
            }
            public DbNode()
            {
                data = default(T);
                next = null;
                prev = null;
            }
            public T Data
            {
                get { return data; }
                set { data = value; }
            }
            public DbNode<T> Prev
            {
                get { return prev; }
                set { prev = value; }
            }
            public DbNode<T> Next
            {
                get { return next; }
                set { next = value; }
            }
            public void SetNode(DbNode<T> pre,DbNode<T> next)
            {
                this.prev = pre;
                this.next = next;
            }
    
    
    
        }
    }

双向链表：

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace _001_线性表
    {
        /// <summary>
        /// 双向链表
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class DoubleLink<T>:IListDS<T>
        {
            #region IListDS<T> 成员
    
            private DbNode<T> _linkHead;
            public DoubleLink()
            {
                _linkHead = null;
            }
           
            public int GetLength()
            {
                if (IsEmpty()) return 0;
                DbNode<T> temp = _linkHead;
                int length = 1;
                while (temp.Next != null)
                {
                     length++;
                     temp = temp.Next;
                }
                return length;
            }
    
            public void Clear()
            {
                _linkHead = null;
            }
    
            public bool IsEmpty()
            {
                return _linkHead == null;
            }
    
            /// <summary>
            /// 在双向链表的尾端添加一个新数据
            /// </summary>
            /// <param name="item"></param>
            public void Add(T item)
            {
                DbNode<T> newNode = new DbNode<T>(item);
                if (IsEmpty())
                {
                    _linkHead = newNode;
                }
                else
                {
                    DbNode<T> preNode = GetListItem(this.GetLength() - 1);
                    newNode.Prev = newNode;
                    preNode.Next = newNode.Prev;
                    newNode.Prev = preNode;
                }
            }
    
            /// <summary>
            /// 获取指定位置的双向链表项目，头项从0开始
            /// </summary>
            public DbNode<T> GetListItem(int index)
            {
                if (index < 0)
                    throw new Exception("索引不能小于0");
                if (index > this.GetLength() - 1)
                    throw new Exception("索引超出列表总长度");
                DbNode<T> temp = _linkHead;
                for (int i = 0; i < index; i++)
                {
                    temp = temp.Next;
                }
                return temp;
            }
    
            /// <summary>
            /// 在双向链表指定的位置插入一个新项
            /// </summary>
            public void Insert(T item, int index)
            {
                if (index < 0)
                    throw new Exception("插入位置不能小于0");
                if (index > this.GetLength() + 1)
                    throw new Exception("插入位置超出链表长度");
                DbNode<T> newNode = new DbNode<T>(item);
                if (index == 0)
                {
                    newNode.Next = _linkHead;
                    _linkHead = newNode;
                }
                else
                {
                    DbNode<T> preNode = GetListItem(index - 1); //要插入位置前面的节点
                    DbNode<T> atfNode = GetListItem(index);//要插入位置后面的节点
                    preNode.Next = new DbNode<T>(item, preNode, atfNode);
                }
            }
    
    
            /// <summary>
            /// 删除指定位置的双向链表项
            /// </summary>
            /// <param name="index"></param>
            public T Delete(int index)
            {
                if (index < 0)
                    throw new Exception("删除位置不能小于0");
                if (index > this.GetLength() - 1)
                    throw new Exception("插入位置超出链表长度");
    
                T data = default(T);
                if (index == 0)
                {
                    data = _linkHead.Data;
                    _linkHead = _linkHead.Next;
                    if(!IsEmpty())
                        this._linkHead.Prev = null;
                }
                else
                {
                    DbNode<T> DelNode = GetListItem(index); //取到要删除的节点
                    data = DelNode.Data;
                    DbNode<T> preNode = DelNode.Prev;
                    DbNode<T> nextNode = DelNode.Next;
                    preNode.Next = nextNode;
                    nextNode.Prev = preNode;
                }
                return data;
            }
    
            public T this[int index]
            {
                get { return GetEle(index); }
            }
    
            public T GetEle(int index)
            {
                DbNode<T> temp = _linkHead;
                for (int i = 0; i < index; i++)
                {
                    temp = temp.Next;
                }
                return temp.Data;
            }
    
            public int Locate(T value)
            {
                DbNode<T> temp = _linkHead;
                if (IsEmpty())
                {
                    return -1;
                }
                else
                {
                    int index = 0;
                    while (true)
                    {
                        if (!temp.Data.Equals(value))
                        {
                            if (temp.Next != null)
                            {
                                index++;
                                temp = temp.Next;
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            return index;
                        }
                    }
                    return -1;
                }
            }
            #endregion
        }
    }

## **双向循环链表** ##

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

双链表的示意图如下：

![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][]

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _001_线性表
    {
        /// <summary>
        /// 双向循环链表
        /// </summary>
        /// <typeparam name="T"></typeparam>
        class DoubleLoopLink<T> : IListDS<T>
        {
            private DbNode<T> _linkHead;
            public T this[int index] =>GetEle(index);
    
            public void Add(T item)
            {
                DbNode<T> newNode = new DbNode<T>(item, null, null);
                if (IsEmpty())
                {
                    _linkHead = newNode;
                    _linkHead.Prev = _linkHead;
                    _linkHead.Next = _linkHead;
                }
                else
                {
                    DbNode<T> preNode = _linkHead;
                    while (preNode.Next != _linkHead)
                    {
                        preNode = preNode.Next;
                    }
                    preNode.Next = newNode;//链表的尾部 的后指针  指向新的节点
                    newNode.SetNode(preNode, _linkHead);     
                    _linkHead.Prev = newNode; //头部的 前指针 指向 新的尾部
                }
            }
            
            public void Clear()
            {
                _linkHead = null;
            }
    
            public T Delete(int index)
            {
                T data = default(T);
                if (IsEmpty())
                    throw new Exception("链表为空，没有可清除的项");
                if (index < 0 || index > this.GetLength() - 1)
                    throw new Exception("给定索引超出链表长度");
    
                DbNode<T> preNode = _linkHead;
                if (index == 0)
                {
                    while (preNode.Next != _linkHead)
                    {
                        preNode = preNode.Next;
                    }
                    this._linkHead = _linkHead.Next;
                    this._linkHead.Prev = preNode;
                    data = preNode.Next.Data;
                    preNode.Next = this._linkHead;
                }
                else
                {
                    for (int i = 1; i < index - 1; i++)
                    {
                        preNode = preNode.Next;
                    }
                    //看图比较好理解
                    DbNode<T> aftNode = preNode.Next.Next; //要删除的节点  后面的节点
                    preNode.Next = aftNode;//要删除节点的前面节点 的后指针 指向  要删除的节点  后面的节点
                    aftNode.Prev = preNode; //要删除的节点 前面的节点  指向  要删除节点的前面节点    
                }
                return data;
            }
    
            public T GetEle(int index)
            {
                DbNode<T> temp = _linkHead;
                for (int i = 0; i < index; i++)
                {
                    temp = temp.Next;
                }
                return temp.Data;
            }
    
            public int GetLength()
            {
                if (IsEmpty()) return 0;
                DbNode<T> temp = _linkHead;
                int length = 1;
                while (temp.Next != _linkHead)
                {
                    length++;
                    temp = temp.Next;
                }
                return length;
            }
            /// <summary>
            /// 插入
            /// </summary>
            /// <param name="item"></param>
            /// <param name="index"></param>
            public void Insert(T item, int index)
            {
                if (IsEmpty())
                    throw new Exception("数据链表为空");
                if (index < 0 || index > this.GetLength())
                    throw new Exception("给定索引超出链表长度");
    
                DbNode<T> newNode = new DbNode<T>(item);
                DbNode<T> preNode = _linkHead;
                if (index == 0) //等于零  先找到 链表中 head的前一个节点 这个节点连接 head
                {
                    while (preNode.Next != _linkHead)
                    {
                        preNode = preNode.Next;
                    }
                    preNode.Next = newNode;
                    newNode.SetNode(preNode, _linkHead);
                    _linkHead.Prev = newNode;
                    return;
                }
                else
                {
                    for (int i = 1; i < index - 1; i++)
                    {
                        preNode = preNode.Next;
                    }
                    //preNode要插入位置的前节点
                    DbNode<T> atfNode = preNode.Next;//要插入节点的后节点
                    preNode.Next = newNode; //后指针 连上新节点
                    newNode.SetNode(preNode,atfNode);
                    atfNode.Prev = newNode;//要插入节点的后节点 连上 新节点
                }
            }
            public bool IsEmpty()
            {
                return _linkHead == null;
            }
    
            public int Locate(T value)
            {
                if (IsEmpty())
                    throw new Exception("链表为空");
                DbNode<T> preNode = _linkHead;
                int index = 0;
                while (true)
                {
                    if (!preNode.Data.Equals(value))
                    {
                        if (preNode.Next != _linkHead)
                        {
                            index++;
                            preNode = preNode.Next;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        return index;
                    }
                }
                return -1;
            }
        }
    }

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

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

[922236-20171220110004678-643077430.png]: /images/20210724/e113a394df4e493b831a54f8a0da0379.png
[922236-20171220110011240-853997173.png]: /images/20210724/26497e4be41e487aa83cc1f5c412abf4.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/eadc57da31524301bd6ab62e47dc70ff.png
[632293-20170306150003297-951612143.png]: /images/20210724/fdc192c639034e39bca0ed64ef31a845.png
[632293-20170306150039609-1719195275.png]: /images/20210724/77a2a5fb357943e98dc7fede998c9dcf.png
[632293-20170306150105453-2068434988.png]: /images/20210724/317f457106874b3c9905ccf84e276355.png