Loading...
墨滴

莫激

2021/12/23  阅读:34  主题:默认主题

c#中双向链表

双链表实现过程

定义一个节点类

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

namespace partical
{
    class LinkedNode<T>
    {

        private T date;//节点中的数值
        private LinkedNode<T> next; //后节点接口
        private LinkedNode<T> pre; //前节点接口
        public LinkedNode<T> Pre
        {
            get
            {
                return pre;
            }
            set
            {
                pre = value;
            }
        }
        public T Date
        {
            set
            {
                date = value;
            }
            get
            {
                return date;
            }
        }

        public LinkedNode<T> Next
        {
            set
            {
                next = value;
            }
            get
            {
                return next;
            }
        }
        public LinkedNode()
        {

        }
        public LinkedNode(value)
        {
            date = value;
        }
        
    }
}

给定一个接口

单链表接口

  • 以下是单链表所拥有的方法,用接口是为了方便我们去实现相应的方法,而不用去想有什么方法漏实现的,接口相当于帮我们先规整好的
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace partical
{
    interface Ilinked<T>
    {
        //添加
        void Add(T vlaue);
        //删除
        reMove(int index);
        //插入
        void Insert(int index, T value);
        //查询数值
        GetEle(int index);
        //索引查询
        T this[int index]
        {
            get;
        }
        //清空
        void clear();
        //得到长度
        int GetLength();
        //判断是否有空
        bool isEmpty();
        //找出位置
        int Locate(value);
    }
}

双链表接口

  • 以下是双链表所需的方法,在单链表基础上添加双链表所需的方法
  • 需要注意在双链表方法中,还不够谨慎,就是当数值是最后一个时,应该怎么添加,因为有点懒得弄了哈哈哈哈
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace partical
{
    interface IlinkedSecond<T>
    {
        void AddFirst(value)//在链表首部添加数据
        void AddLast(value);//在链表尾部添加数据
        void AddBefore(value, T newValue);//在链表中的value值前面插入newValue
        void AddAfter(value, T newValue);//在链表中的value值后面插入newValue
        bool contains(value);//链表中是否含有value
    }
}

双链表实现过程

  • 其实就是在单链表的基础上添加几个双链表需要的方法,当然也因为加了双链表,在添加、删除、插入等也要进行相应的调整
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace partical
{
    class LinkedList1<T> : Ilinked<T>,IlinkedSecond<T>
    {
        LinkedNode<T> head = new LinkedNode<T>();
        LinkedNode<T> last = new LinkedNode<T>();

        public LinkedList1()
        {
            head = null;       
        }
        //添加
        public void Add(value)
        {
            LinkedNode<T> newNode = new LinkedNode<T>(value);
            if (head == null)
            {
                head = newNode;
                last = newNode;
            }
            else
            {
                LinkedNode<T> temp = head;
                while (true)
                {
                    if (temp.Next!=null)
                    {
                        temp = temp.Next;
                    }
                    else
                    {
                        break;
                    }
                }
                
                temp.Next = newNode;
                last = newNode;
            }
        }
        
  //插入
        public void Insert(int index, T value)
        {
            LinkedNode<T> newNode = new LinkedNode<T>(value);
            if (index == 0)
            {
                newNode.Next = head;
                head = newNode;
            }
            else
            {
                LinkedNode<T> temp = head;
                for (int i = 1; i <= index-1; i++)
                {
                    temp = temp.Next;
                }
                LinkedNode<T> preNode = temp;
                LinkedNode<T> currentNode = temp.Next;
                preNode.Next = newNode;
                newNode.Next = currentNode;
                if (currentNode.Next == null)
                {
                    last = currentNode;
                }
            }
        }
        
        //移除
        public T reMove(int index)
        {
            T data = default(T);
            if (index==0)
            {
                head = head.Next;
                data = head.Date;
            }
            else
            {
                LinkedNode<T> temp = head;
                for (int i = 1 ; i <= index-1; i++)
                {
                    temp = temp.Next;
                }
                LinkedNode<T> preNode = temp;
                LinkedNode<T> currentNode = temp.Next;
                LinkedNode<T> nextNode = temp.Next.Next;
                preNode.Next = nextNode;
                data = currentNode.Date;
                
            }
            return data;
        }
        
        //清空
        public void clear()
        {

            head = null;
        }

  //获取长度
        public int GetLength()
        {
            if (head == null)
            {
                return 0;
            }
            LinkedNode<T> temp = head;
            int num = 1;
            while (true)
            {
                if (temp.Next != null)
                {
                    num++;
                    temp = temp.Next;
                }
                else
                {
                    break;
                }
            }
            return num;
        }

      //是否为空
        public bool isEmpty()
        {
            return head == null;
        }

  //查找位置
        public int Locate(value)
        {
            int index = 1;
            LinkedNode<T> tamp = head;
            if (head == null)
            {
                return -1;
            }
            else
            {
                while (true)
                {
                    if (tamp.Date.Equals(value))
                    {
                        return index;
                    }
                    else
                    {
                        if (tamp.Next!=null)
                        {
                            tamp = tamp.Next;
                            index++;
                        }
                        else
                        {
                            break;
                        }
                        
                    }
                }
            }
            
            return index;
        }
        
        //查找值(用索引器)
        public T this[int index]
        {
            get
            {
                LinkedNode<T> tamp = head;
                for (int i = 1; i <= index; i++)
                {
                    tamp = tamp.Next;
                }
                return tamp.Date;
            }
        }
        
        //查找值
        public T GetEle(int index)
        {
            return this[index];
        }

  //在链表首部添加
        public void AddFirst(value)
        {
            LinkedNode<T> newNode = new LinkedNode<T>(value);
            newNode.Next = head;
            head = newNode;
        }
  //在链表尾部添加
        public void AddLast(value)
        {
            LinkedNode<T> newNode = new LinkedNode<T>(value);
            newNode.Pre = last;
            last = newNode;
        }
  //在链表中value值前添加newValue
        public void AddBefore(value, T newvalue)//在value前面插入newValue
        {
            //遍历寻找value
            LinkedNode<T> tamp = head;
            LinkedNode<T> newValue = new LinkedNode<T>(newvalue);
            while (true)
            {
                if (tamp!=null)
                {
                    
                    if (tamp.Date.Equals(value))
                    {
                        break;
                    }
                    tamp = tamp.Next;
                }
                else
                {
                    Console.WriteLine("找不到{0}",value);
                }
            }
            if (tamp==head)
            {
                newValue.Next = tamp;//tamp==head
                head = newValue;
            }
            else
            {
                LinkedNode<T> preNode = tamp.Pre;
                preNode.Next = newValue;
                newValue.Next = tamp;
            }
           

        }
  //在链表中value值后添加newValue
        public void AddAfter(value, T newvalue)
        {
            //遍历找出value
            LinkedNode<T> newValue = new LinkedNode<T>(newvalue);
            LinkedNode<T> tamp = head;
            while (true)
            {
                if (tamp!=null)
                {
                    if (tamp.Date.Equals(value))
                    {
                        break;
                    }
                    tamp = tamp.Next;
                }
                else
                {
                    Console.WriteLine("找不到{0}",value);
                }
            }
            if (tamp==last)
            {
                newValue.Pre = tamp;
                last = newValue;
            }
            else
            {
                LinkedNode<T> nextNode = tamp.Next;
                tamp.Next = newValue;
                newValue.Next = nextNode;
            }
            
        }

        public bool contains(value)
        {
            LinkedNode<T> tamp = head;
            while (true)
            {
                if (tamp!=null)
                {
                    if (tamp.Date.Equals(value))
                    {
                        break;
                    }
                    tamp = tamp.Next;
                    
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
    }
}

莫激

2021/12/23  阅读:34  主题:默认主题

作者介绍

莫激