public class DbNode{ //私有变量 private T _data; //节点的值 privat..._构造void addbefore(t data,nodesucc) 怎么调用">
devbox
IT领航者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法-003.双向链表和循环链表_构造void addbefore(t data,nodesucc) 怎么调用

作者：IT领航者 | 2024-02-02 12:43:07

赞

踩

构造void addbefore(t data,nodesucc) 怎么调用

双向链表
在这里插入图片描述
结点Node类型定义：

/// <summary>
/// 双向链表的节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class DbNode<T>
{
    //私有变量
    private T _data; //节点的值
    private DbNode<T> _prev; //前驱节点
    private DbNode<T> _next; //后继结点

    //属性

    /// <summary>
    /// 节点的值
    /// </summary>
    public T Data
    {
        get { return this._data; }
        set { this._data = value; }
    }

    /// <summary>
    /// 前驱节点
    /// </summary>
    public DbNode<T> Prev
    {
        get { return this._prev; }
        set { this._prev = value; }
    }

    /// <summary>
    /// 后继结点
    /// </summary>
    public DbNode<T> Next
    {
        get { return this._next; }
        set { this._next = value; }
    }

    // 构造函数 6个

    public DbNode(T data, DbNode<T> prev, DbNode<T> next)//中间节点
    {
        this._data = data;
        this._prev = prev;
        this._next = next;
    }

    public DbNode(T data, DbNode<T> prev)//结尾结点
    {
        this._data = data;
        this._prev = prev;
        this._next = null; //结尾处的node
    }

    //public DbNode(T data, DbNode<T> next)//开头结点
    //{
    //    this._data = data;
    //    this._prev = null; //开头处的node
    //    this._next = next;
    //}

    public DbNode(DbNode<T> next)
    {
        //使用 default 关键字，此关键字对于引用类型会返回空，对于数值类型会返回零。
        //对于结构，此关键字将返回初始化为零或空的每个结构成员，具体取决于这些结构是值类型还是引用类型
        this._data = default(T);
        this._next = next;
        this._prev = null;
    }

    public DbNode(T data)
    {
        this._data = data;
        this._prev = null;
        this._next = null;
    }

    public DbNode()
    {
        this._data = default(T);
        this._prev = null;
        this._next = null;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86

循环链表：
循环单链表
在这里插入图片描述
Node类：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    public class Node<T>
    {
        private T data; //数据域
        private Node<T> next; //引用域

        //数据域属性
        public T Data { get => data; set => data = value; }
        //引用域属性
        internal Node<T> Next { get => next; set => next = value; }

        //构造器
        public Node(T val, Node<T> p) {
            Data = val;
            Next = p;
        }

        //构造器
        public Node(Node<T> p) {
            Next = p;
        }

        //构造器
        public Node(T val) {
            Data = val;
        }

        //构造器
        public Node() {
            Data = default(T);
            Next = null;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

SingleCycle接口

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    interface SingleCycleDs<T>
    {
        int GetLength();    //求长度
        void Clear();   //清空操作
        bool IsEmpty(); //判断线性表是否为空
        void Append(T item);    //附加操作
        void Insert(T item, int i); //插入
        void Delete(int i);    //删除操作
        T GetElem(int i);   //取表元
        int Locate(T value);    //按值查找
        void Reverse(); //逆置
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

SingleCycle类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class SingleCycle<T> : SingleCycleDs<T>
    {
        Node<T> head;   //头节点

        //头节点属性
        public Node<T> Head { get => head; set => head = value; }

        //构造器
        public SingleCycle() {
            head = new Node<T>();
            head.Next = head;
        }

        /// <summary>
        /// 附加元素到尾部
        /// </summary>
        /// <param name="item">元素</param>
        public void Append(T item)
        {
            Node<T> p = new Node<T>(item);
            Node<T> c = head;

            //头节点为空时，直接修改头节点和新增节点的引用
            if (IsEmpty()) {
                head.Next = p;
                p.Next = head;
                return;
            }

            //遍历至最后一个节点
            while (c.Next != head) {
                c = c.Next;
            }

            //将新增元素挂载到末尾
            c.Next = p;
            p.Next = head;
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        public void Clear()
        {
            head.Next = head;
        }

        /// <summary>
        /// 删除节点
        /// </summary>
        /// <param name="i">删除节点的位置</param>
        public void Delete(int i)
        {
            //链表为空
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("链表为空或位置错误");
                return;
            }

            //删除头节点
            if (i == 1)
            {
                head.Next = head.Next.Next;
                return;
            }

            //遍历位置删除节点
            Node<T> c = head.Next;  //目标节点
            Node<T> p = new Node<T>(); //目标节点的前驱节点
            int j = 1;
            while (c.Next != head && j < i)
            {
                /* 记录当前节点，
                 * 因为当前节点为下一次遍历的前驱节点，
                 * 当遍历到目标节点时，可以直接用其前驱节点操作。
                 */
                p = c;

                c = c.Next;
                ++j;
            }
            //遍历到位置
            if (j == i)
            {
                Console.WriteLine(j);
                Console.WriteLine(p.Next.Data);
                //用前驱节点来跳过目标节点，直接挂载目标节点的后继节点到其前驱节点上
                p.Next = p.Next.Next;
                Console.WriteLine("删除成功");
            }
            //未找到位置
            else {
                Console.WriteLine("位置不正确");
            }
        }

        /// <summary>
        /// 根据位置获取元素值
        /// </summary>
        /// <param name="i">元素位置</param>
        /// <returns>元素数据域值</returns>
        public T GetElem(int i)
        {
            //链表为空时返回默认值。
            if (IsEmpty()) {
                Console.WriteLine();
                return default(T);
            }

            //返回第一个元素的值
            if (i == 1) {
                return head.Next.Data;
            }

            //遍历查找并返回
            Node<T> c = head.Next;
            int j = 1;
            while (c.Next != head && j < i) {
                c = c.Next;
                ++j;
            }
            //遍历找到
            if (j == i)
            {
                return c.Data;
            }
            else {
                Console.WriteLine("位置不正确");
            }
            return default(T);
        }

        /// <summary>
        /// 获取列表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            if (IsEmpty()) {
                return 0;
            }

            Node<T> c = head.Next;
            int i = 1;
            while (c.Next != head) {
                c = c.Next;
                ++i;
            }
            return i;

        }

        /// <summary>
        /// 插入节点
        /// </summary>
        /// <param name="item">插入的元素值</param>
        /// <param name="i">插入位置</param>
        public void Insert(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("链表为空或位置错误");
            }

            //插入到首节点位置
            if (i == 1) {
                Node<T> c = head.Next; //保存首节点
                head.Next = new Node<T>(item); //将新节点插入到头节点后
                head.Next.Next = c; //将首节点设为新节点的后继
                return;
            }

            //遍历位置插入
            Node<T> c1 = head.Next;
            Node<T> p = new Node<T>();
            int j = 1;
            while (c1.Next != head && j < i)
            {
                p = c1;
                c1 = c1.Next;
                ++j;
            }
            //遍历找到
            if (j == i)
            {
                p.Next = new Node<T>(item);
                p.Next.Next = c1;
            }
            else
            {
                Console.WriteLine("位置不正确");
            }
        }

        //判断链表是否为空
        public bool IsEmpty()
        {
            return head.Next == head;
        }

        /// <summary>
        /// 根据节点值查找位置
        /// </summary>
        /// <param name="value">节点值</param>
        /// <returns>节点位置</returns>
        public int Locate(T value)
        {
            int i = 1;
            Node<T> c = head.Next;


            /* 这里的判断条件要不能写c.Next，
             * 因为当目标值为最后一个节点的值时，c.Next==head会成立
             * 所以要让循环多遍历一次，
             * 当c时头节点时说明列表已遍历完毕，这时如果还未找到，说明不存在。
             * 注意：要将比较语句写在逻辑判断后面，
             * 因为head=null，当c=head时，比较语句会抛异常。
             * 所以要先比较c==head来中断后面的语句。
            */

            while (c != head && !c.Data.Equals(value))
            {
                c = c.Next;
                ++i;
            }

            if (c == head)
            {
                Console.WriteLine("不存在这样的节点");
                return -1;
            }
            else {
                return i;
            }
        }

        public void Reverse()
        {
            throw new NotImplementedException();
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251

Program类

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            SingleCycle<string> link = new SingleCycle<string>();
            //添加元素
            link.Append("123");
            link.Append("567");
            link.Append("jqk");
            link.Append("qwe");

            //link.Clear();
            //link.Delete(5);
            //Console.WriteLine(link.GetElem(4));
            //Console.WriteLine(link.GetLength());
            //link.Insert("asd", 4);
            Console.WriteLine(link.Locate("1231"));
            
            //输出
            Node<string> c = link.Head.Next;
            while (c != link.Head)
            {
                Console.WriteLine(c.Data);
                c = c.Next;
            }

            Console.Read();
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

循环双链表
在这里插入图片描述
节点类（DoubleLinkedListNode.cs）

 public class DoubleLinkedListNode<T>
    {
        //前驱
        private DoubleLinkedListNode<T> _nextDoubleLinkedListNode;
        private DoubleLinkedListNode<T> _prevDoubleLinkedListNode;
 
        //数据
        private T dataValue;
 
        /// <summary>
        ///     无参构造函数 该节点只有默认值，前驱和后继都 ——>null
        /// </summary>
        public DoubleLinkedListNode()
        {
            this.dataValue = default(T);
            this._nextDoubleLinkedListNode = null;
            this._prevDoubleLinkedListNode = null;
        }
 
        /// <summary>
        ///     构造方法：实例化该节点只有传入的data域，前驱和后继都指向null
        /// </summary>
        /// <param name="value"></param>
        public DoubleLinkedListNode(T value)
        {
            this._prevDoubleLinkedListNode = null;
            this.dataValue = value;
            this._nextDoubleLinkedListNode = null;
        }
 
        /// <summary>
        ///     构造函数：实例化一个正常的Node 数据域 前驱后继都有值
        /// </summary>
        /// <param name="value"></param>
        /// <param name="prev"></param>
        /// <param name="next"></param>
        public DoubleLinkedListNode(T value, DoubleLinkedListNode<T> prev, DoubleLinkedListNode<T> next)
        {
            this._prevDoubleLinkedListNode = prev;
            this.dataValue = value;
            this._nextDoubleLinkedListNode = next;
        }
 
        public DoubleLinkedListNode<T> PrevDoubleLinkedListNode
        {
            get { return this._prevDoubleLinkedListNode; }
            set { this._prevDoubleLinkedListNode = value; }
        }
 
        public T DataValue
        {
            get { return this.dataValue; }
            set { this.dataValue = value; }
        }
 
        public DoubleLinkedListNode<T> NextDoubleLinkedListNode
        {
            get { return this._nextDoubleLinkedListNode; }
            set { this._nextDoubleLinkedListNode = value; }
        }
 
        /// <summary>
        ///     Show 方法，调试用
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            T p = this._prevDoubleLinkedListNode == null ? default(T) : this._prevDoubleLinkedListNode.dataValue;
            T n = this._nextDoubleLinkedListNode == null ? default(T) : this._nextDoubleLinkedListNode.dataValue;
            string s = string.Format("Data:{0},Prev:{1},Next:{2}", this.dataValue, p, n);
            return s;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73

接口（ILinkList.cs）

 internal interface ILinkedList<T>
    {
        /// <summary>
        ///     头元素
        /// </summary>
        DoubleLinkedListNode<T> HeadDoubleLinkedListNode { get; }
 
        /// <summary>
        ///     尾元素
        /// </summary>
        DoubleLinkedListNode<T> EndDoubleLinkedListNode { get; }
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 中指定的现有节点后添加指定的新节点。
        /// </summary>
        /// <param name="node"></param>
        /// <param name="newNode"></param>
        void AddAfter(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 中的现有节点后添加新的节点或值。
        /// </summary>
        /// <param name="node"></param>
        /// <param name="t"></param>
        void AddAfter(DoubleLinkedListNode<T> node, T t);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 中指定的现有节点前添加指定的新节点。
        /// </summary>
        /// <param name="node"></param>
        /// <param name="newNode"></param>
        void AddBefore(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 中指定的现有节点前添加包含指定值的新节点。
        /// </summary>
        /// <param name="node"></param>
        /// <param name="t"></param>
        void AddBefore(DoubleLinkedListNode<T> node, T t);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 的开头处添加包含指定值的新节点。
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        DoubleLinkedListNode<T> AddFirst(T value);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 的开头处添加指定的新节点
        /// </summary>
        /// <param name="node"></param>
        void AddFirst(DoubleLinkedListNode<T> node);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 的结尾处添加包含指定值的新节点。
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        DoubleLinkedListNode<T> AddLast(T value);
 
        /// <summary>
        ///     在 LinkedList<(Of <(T>)>) 的结尾处添加指定的新节点
        /// </summary>
        /// <param name="node"></param>
        void AddLast(DoubleLinkedListNode<T> node);
 
        /// <summary>
        ///     从 LinkedList<(Of <(T>)>) 中移除指定的节点。
        /// </summary>
        /// <param name="node"></param>
        bool Remove(DoubleLinkedListNode<T> node);
 
        /// <summary>
        ///     从 LinkedList<(Of <(T>)>) 中按索引删除节点。
        /// </summary>
        /// <param name="node"></param>
        bool Remove(int index);
 
        /// <summary>
        ///     移除头结点
        /// </summary>
        void RemoveHeadNode();
 
        /// <summary>
        ///     移除尾节点
        /// </summary>
        void RemoveEndNode();
 
        /// <summary>
        ///     从 LinkedList<(Of <(T>)>) 中查找第一个匹配项
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        DoubleLinkedListNode<T> Find(T value);
 
        /// <summary>
        ///     从 LinkedList<(Of <(T>)>) 中查找最后一个匹配项
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        DoubleLinkedListNode<T> FindLast(T value);
 
        /// <summary>
        ///     查询元素的索引
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        int IndexOf(T item);
 
        /// <summary>
        ///     能过索引得到元素的元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        T GetElementByIndex(int index);
 
        /// <summary>
        ///     通过索引得到节点对象
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        DoubleLinkedListNode<T> GetNodeByIndex(int index);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123

**双向循环链表（DoubleCircularLinkList.cs）
**

 public class DoubleCircularLinkedList<T> : IEnumerable<T>
    {
        private DoubleLinkedListNode<T> _headNode;
        private DoubleLinkedListNode<T> _nextNode;
        private DoubleLinkedListNode<T> current;
        private int currentIndex;
 
        public DoubleLinkedListNode<T> HeadNode { get; set; }
 
        public DoubleLinkedListNode<T> NextNode { get; set; }
 
        public int Count { get; private set; }
 
 
        /// <summary>
        ///     根据索引获取链表中的节点
        /// </summary>
        /// <param name="index">整型索引</param>
        /// <returns>节点</returns>
        public DoubleLinkedListNode<T> this[int index]
        {
            get
            {
                if (index < 0 || index >= this.Count)
                {
                    throw new Exception("索引值非法,无法得对象节点.");
                }
                DoubleLinkedListNode<T> reNode = this._headNode;
                int i = 0;
                while (reNode != null)
                {
                    if (i == index)
                    {
                        break;
                    }
                    reNode = reNode.NextDoubleLinkedListNode;
                    ++i;
                }
                return reNode;
            }
        }
 
        /// <summary>
        ///     判断链表是否是空的
        /// </summary>
        public bool IsEmpty
        {
            get { return this._headNode == null; }
        }
 
        public void AddAfter(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode)
        {
            this.AddAfter(node, newNode.DataValue);
        }
 
        public void AddAfter(DoubleLinkedListNode<T> node, T t)
        {
            if (node == null || t == null)
            {
                throw new Exception("元素为空，不可以进行插入");
            }
            int index = this.IndexOf(node.DataValue);
 
            if (index != -1)
            {
                DoubleLinkedListNode<T> currNode = this.GetNodeByIndex(index);
                DoubleLinkedListNode<T> upNode = currNode.PrevDoubleLinkedListNode;
                DoubleLinkedListNode<T> nextNode = currNode.NextDoubleLinkedListNode;
                var newNode = new DoubleLinkedListNode<T>(t);
                if (index == 0)
                {
                    this._headNode.NextDoubleLinkedListNode = newNode;
                    newNode.PrevDoubleLinkedListNode = this._headNode;
                    newNode.NextDoubleLinkedListNode = nextNode;
                }
                else if (index == this.Count - 1)
                {
                    newNode.PrevDoubleLinkedListNode = this._nextNode;
                    this._nextNode.NextDoubleLinkedListNode = newNode;
                    this._nextNode = newNode;
                }
                else
                {
                    nextNode.PrevDoubleLinkedListNode = newNode;
                    currNode.NextDoubleLinkedListNode = newNode;
                    newNode.PrevDoubleLinkedListNode = currNode;
                    newNode.NextDoubleLinkedListNode = nextNode;
                }
            }
        }
 
        public void AddBefore(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode)
        {
            this.AddBefore(node, newNode.DataValue);
        }
 
        public void AddBefore(DoubleLinkedListNode<T> node, T t)
        {
            if (node == null || t == null)
            {
                throw new Exception("元素为空，不可以进行插入");
            }
            int index = this.IndexOf(node.DataValue);
 
            if (index != -1)
            {
                DoubleLinkedListNode<T> currNode = this.GetNodeByIndex(index);
                DoubleLinkedListNode<T> upNode = currNode.PrevDoubleLinkedListNode;
                DoubleLinkedListNode<T> nextNode = currNode.NextDoubleLinkedListNode;
                var newNode = new DoubleLinkedListNode<T>(t);
                if (index == 0)
                {
                    this._headNode.PrevDoubleLinkedListNode = newNode;
                    newNode.NextDoubleLinkedListNode = this._headNode;
                    this._headNode = newNode;
                }
                else if (index == this.Count - 1)
                {
                    upNode.NextDoubleLinkedListNode = newNode;
                    newNode.NextDoubleLinkedListNode = this._nextNode;
                    this._nextNode.PrevDoubleLinkedListNode = newNode;
                }
                else
                {
                    upNode.NextDoubleLinkedListNode = newNode;
                    nextNode.PrevDoubleLinkedListNode = newNode;
                    currNode.PrevDoubleLinkedListNode = upNode;
                    currNode.NextDoubleLinkedListNode = nextNode;
                }
            }
        }
 
        /// <summary>
        ///     添加节点到链表的开头
        /// </summary>
        /// <param name="t"></param>
        public DoubleLinkedListNode<T> AddFirst(T value)
        {
            var doubleLinkedListNode = new DoubleLinkedListNode<T>(value);
            //如果头为null
            if (this._headNode == null)
            {
                //把头节点设置为node
                this._headNode = doubleLinkedListNode;
                //因为是空链表，所以头尾一致
                this._headNode = doubleLinkedListNode;
                //大小加一
                this.Count ++;
                return null;
            }
            //原来头节点的上一个为新节点
            this._headNode.PrevDoubleLinkedListNode = doubleLinkedListNode;
            //新节点的下一个为原来的头节点
            doubleLinkedListNode.NextDoubleLinkedListNode = this._headNode;
            //新头节点为新节点
            this._headNode = doubleLinkedListNode;
            //大小加一
            this.Count++;
            return this._headNode;
        }
 
        public void AddFirst(DoubleLinkedListNode<T> node)
        {
            this.AddFirst(node.DataValue);
        }
 
        /// <summary>
        ///     添加节点到链表的末尾
        /// </summary>
        /// <param name="t">要添加的数据</param>
        public DoubleLinkedListNode<T> AddLast(T t)
        {
            var doubleLinkedListNode = new DoubleLinkedListNode<T>(t);
            //当前Node
            this.current = doubleLinkedListNode;
 
 
            //如果头为null   Count =0
            if (this._headNode == null)
            {
                //把头节点设置为当前node
                this._headNode = this.current;
 
                //循环双向链表头尾相连 前驱和后继都为当前node
                this._headNode.PrevDoubleLinkedListNode = this.current;
                this._headNode.NextDoubleLinkedListNode = this.current;
 
 
                //因为是空链表，所以头尾一致
 
                //大小加一
                this.Count++;
 
                return this.current;
            }
 
            //只包含一个头结点 Count=1
            if (this.Count == 1)
            {
                for (int index = 0; index < this.Count; index++)
                {
                    //判定检索原有链表中的尾节点    尾节点必定指向首节点
                    if (this[index].NextDoubleLinkedListNode == this._headNode)
                    {
                        //原尾节点的后置指向当前插入节点
                        this[index].NextDoubleLinkedListNode = this.current;
 
 
                        this[index].PrevDoubleLinkedListNode = this.current;
 
 
                        this.current.PrevDoubleLinkedListNode = this[index];
                        this.current.NextDoubleLinkedListNode = this[index];
                        this.Count++;
                        return this.current;
                    }
                }
            }
            //两个节点以上 Count>=2
            if (this.Count >= 2)
            {
                for (int index = 0; index < this.Count; index++)
                {
                    //判定检索原有链表中的尾节点    尾节点必定指向首节点
                    if (this[index].NextDoubleLinkedListNode == this._headNode)
                    {
                        //原尾节点的后置指向当前插入节点
 
                        this._headNode.PrevDoubleLinkedListNode = this.current;
                        this[index].NextDoubleLinkedListNode = this.current;
 
                        this.current.PrevDoubleLinkedListNode = this[index];
                        this.current.NextDoubleLinkedListNode = this._headNode;
                        this.Count++;
                        return this.current;
                    }
                }
            }
 
            return this.current;
        }
 
        public void AddLast(DoubleLinkedListNode<T> node)
        {
            this.AddLast(node.DataValue);
        }
 
        /// <summary>
        ///     移除链表中的节点
        /// </summary>
        /// <param name="index">要移除的节点的索引</param>
        public bool Remove(DoubleLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new Exception("节点不可以为空，无法进行删除");
            }
            int index = this.IndexOf(node.DataValue);
            return this.Remove(index);
        }
 
        public bool Remove(int index)
        {
            if (index < 0 || index >= this.Count)
            {
                throw new Exception("索引值非法，无法进行删除。");
            }
            bool flag = false;
            DoubleLinkedListNode<T> node = this._headNode;
            int i = 0;
            while (node != null)
            {
                if (i == index)
                {
                    DoubleLinkedListNode<T> upNode = node.PrevDoubleLinkedListNode;
                    DoubleLinkedListNode<T> nextNode = node.NextDoubleLinkedListNode;
 
                    if (index == 0)
                    {
                        this._headNode = node.NextDoubleLinkedListNode;
                        node = null;
                    }
                    else if (index == this.Count - 1)
                    {
                        this._nextNode = upNode;
                        this._nextNode.NextDoubleLinkedListNode = null;
                        node = null;
                    }
                    else
                    {
                        upNode.NextDoubleLinkedListNode = nextNode;
                        nextNode.PrevDoubleLinkedListNode = upNode;
                        node = null;
                    }
                    flag = true;
                    break;
                }
                node = node.NextDoubleLinkedListNode;
                ++i;
            }
            return flag;
        }
 
        /// <summary>
        ///     移除头节点
        /// </summary>
        public void RemoveHeadNode()
        {
            //链表头节点是空的
            if (this.IsEmpty)
            {
                throw new Exception("链表是空的。");
            }
            //如果size为1，那就是清空链表。
            if (this.Count == 1)
            {
                this.Clear();
                return;
            }
            //将头节点设为原头结点的下一个节点，就是下一个节点上移
            this._headNode = this._headNode.NextDoubleLinkedListNode;
            //处理上一步遗留问题，原来的第二个节点的上一个是头结点，现在第二个要变成头节点，那要把它的Prev设为null才能成为头节点
            this._headNode.PrevDoubleLinkedListNode = null;
            //大小减一
            this.Count--;
        }
 
        /// <summary>
        ///     移除尾节点
        /// </summary>
        public void RemoveEndNode()
        {
            //链表头节点是空的
            if (this.IsEmpty)
            {
                throw new Exception("链表是空的。");
            }
            //如果size为1，那就是清空链表。
            if (this.Count == 1)
            {
                this.Clear();
                return;
            }
            //尾节点设置为倒数第二个节点
            this._nextNode = this._headNode.PrevDoubleLinkedListNode;
            //将新尾节点的Next设为null，表示它是新的尾节点
            this._headNode.NextDoubleLinkedListNode = null;
            //大小减一
            this.Count--;
        }
 
        public DoubleLinkedListNode<T> Find(T value)
        {
            throw new NotImplementedException();
        }
 
        public DoubleLinkedListNode<T> FindLast(T value)
        {
            throw new NotImplementedException();
        }
 
        public int IndexOf(T item)
        {
            if (item == null || this.Count == 0 || this._headNode == null)
            {
                throw new Exception("无法得到元素索引");
            }
            int reInt = -1;
            int i = 0;
            DoubleLinkedListNode<T> node = this._headNode;
            while (node != null)
            {
                if (node.DataValue.Equals(item))
                {
                    reInt = i;
                    break;
                }
 
                ++i;
                node = node.NextDoubleLinkedListNode;
            }
 
            return reInt;
        }
 
        public T GetElementByIndex(int index)
        {
            if (index < 0 || index >= this.Count)
            {
                throw new Exception("索引值非法,无法得对象.");
            }
            DoubleLinkedListNode<T> reNode = this._headNode;
            int i = 0;
            while (reNode != null)
            {
                if (i == index)
                {
                    break;
                }
                reNode = reNode.NextDoubleLinkedListNode;
                ++i;
            }
            return reNode.DataValue;
        }
 
        public DoubleLinkedListNode<T> GetNodeByIndex(int index)
        {
            if (index < 0 || index >= this.Count)
            {
                throw new Exception("索引值非法,无法得对象节点.");
            }
            DoubleLinkedListNode<T> reNode = this._headNode;
            int i = 0;
            while (reNode != null)
            {
                if (i == index)
                {
                    break;
                }
                reNode = reNode.NextDoubleLinkedListNode;
                ++i;
            }
            return reNode;
        }
 
        /// <summary>
        ///     清除链表
        /// </summary>
        public void Clear()
        {
            this.Count = 0;
            this.HeadNode = null;
            this.NextNode = null;
        }
 
        private void Reset()
        {
            this.currentIndex = 0;
            this.current = this.HeadNode;
        }
 
        public void ShowtheLinkList()
        {
            var p = new DoubleLinkedListNode<T>();
            p = this._headNode;
            int index = 0;
            int index2 = 0;
            while (p != null)
            {
                string prev = " ";
                string data = " ";
                string next = " ";
                if (p.PrevDoubleLinkedListNode == null)
                {
                    prev = "null";
                }
                else
                {
                    prev = Convert.ToString((p.PrevDoubleLinkedListNode.DataValue as PersonModel).id);
                }
                if (p.DataValue == null)
                {
                    data = "null";
                }
                else
                {
                    data = Convert.ToString((p.DataValue as PersonModel).id);
                }
                if (p.NextDoubleLinkedListNode == null)
                {
                    next = "null";
                }
                else
                {
                    next = Convert.ToString((p.NextDoubleLinkedListNode.DataValue as PersonModel).id);
                }
 
 
                Console.Write("前驱为：{0},数据为：{1},后继为：{2},索引为：{3}\n", prev, data, next, index);
                p = p.NextDoubleLinkedListNode;
                if (index == this.Count - 1)
                {
                    Console.Write("一个轮回");
                    Console.ReadKey();
                }
                ++index;
            }
        }
 
        #region IEnumerable<T> 成员
 
        public IEnumerator<T> GetEnumerator()
        {
            DoubleLinkedListNode<T> currNode = this._headNode;
            while (currNode != null)
            {
                yield return currNode.DataValue;
                currNode = currNode.NextDoubleLinkedListNode;
            }
        }
 
        #endregion
 
        #region IEnumerable 成员
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
 
        #endregion
    }


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403
  • 404
  • 405
  • 406
  • 407
  • 408
  • 409
  • 410
  • 411
  • 412
  • 413
  • 414
  • 415
  • 416
  • 417
  • 418
  • 419
  • 420
  • 421
  • 422
  • 423
  • 424
  • 425
  • 426
  • 427
  • 428
  • 429
  • 430
  • 431
  • 432
  • 433
  • 434
  • 435
  • 436
  • 437
  • 438
  • 439
  • 440
  • 441
  • 442
  • 443
  • 444
  • 445
  • 446
  • 447
  • 448
  • 449
  • 450
  • 451
  • 452
  • 453
  • 454
  • 455
  • 456
  • 457
  • 458
  • 459
  • 460
  • 461
  • 462
  • 463
  • 464
  • 465
  • 466
  • 467
  • 468
  • 469
  • 470
  • 471
  • 472
  • 473
  • 474
  • 475
  • 476
  • 477
  • 478
  • 479
  • 480
  • 481
  • 482
  • 483
  • 484
  • 485
  • 486
  • 487
  • 488
  • 489
  • 490
  • 491
  • 492
  • 493
  • 494
  • 495
  • 496
  • 497
  • 498
  • 499
  • 500
  • 501
  • 502
  • 503
  • 504
  • 505
  • 506
  • 507
  • 508
  • 509
  • 510
  • 511
  • 512
  • 513
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55350
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。