双向链表及C#的实现

双向链表图解

程序实现

下面的实现中没有使用头节点（即头节点就是首节点）

Node类

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

namespace test
{
    class Node<T>
    {
        T data; //数据域
        Node<T> next;   //后继节点
        Node<T> pre;    //前驱节点

        internal Node<T> Next { get => next; set => next = value; }
        internal Node<T> Pre { get => pre; set => pre = value; }
        public T Data { get => data; set => data = value; }

        //构造器
        public Node(T value, Node<T> next, Node<T> pre)
        {
            Data = value;
            Next = next;
            Pre = pre;
        }

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

        //构造器
        public Node(Node<T> next,Node<T> pre)
        {
            Next = next;
            Pre = pre;
        }

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

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

DoubleList类

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

namespace test
{
    class DoubleList<T>
    {
        Node<T> head; //头节点

        internal Node<T> Head { get => head; set => head = value; }

        //构造器
        public DoubleList() { Head = null; }

        /// <summary>
        /// 链表判空
        /// </summary>
        /// <returns>为空返回true</returns>
        public bool IsEmpty() { return Head == null; }

        /// <summary>
        /// 取链表长度
        /// </summary>
        /// <returns>链表长度</returns>
        public int GetLenth()
        {
            //链表为空
            if (IsEmpty()) { return 0; }
            //只有一个元素
            if (Head.Next == null) { return 1; }
            //遍历链表
            Node<T> c = Head;
            int i = 1;
            while (c.Next != null)
            {
                c = c.Next;
                ++i;
            }
            return i;
        }

        /// <summary>
        /// 在末尾添加新元素
        /// </summary>
        public void Append(T value)
        {
            Node<T> item = new Node<T>(value);

            //链表为空时，直接覆盖首节点
            if (IsEmpty()) { Head = item; return; }

            //只有一个元素时，直接挂载
            if (Head.Next == null)
            {
                Head.Next = item;
                item.Pre = Head;
                return;
            }

            //遍历至末尾添加
            Node<T> c = Head;
            while (c.Next != null) { c = c.Next; }
            c.Next = item;
            item.Pre = c;
        }

        /// <summary>
        /// 在指定位置后插入元素
        /// </summary>
        /// <param name="value">元素值</param>
        /// <param name="i">元素位置</param>
        public void Insert(T value, int i)
        {
            //插入位置大于链表总长度
            if (GetLenth() < i)
            {
                Console.WriteLine("插入位置不正确");
                return;
            }

            Node<T> c = new Node<T>(value);//新节点

            //插入到头节点位置
            if (i == 1)
            {
                Head.Next.Pre = c;  //头节点的后继节点的前驱指向新节点
                c.Next = Head.Next; //新节点的后继指向头节点的后继节点
                c.Pre = Head;   //新节点的前驱指向头节点
                Head.Next = c;  //头节点的后继指向新节点
                return;
            }

            //遍历插入
            int j = 1;
            Node<T> cur = Head;
            while (cur.Next != null && i > j)
            {
                cur = cur.Next;
                ++j;
            }
            if (j == i)
            {
                cur.Next.Pre = c;   //当前节点的后继节点的前驱指向新节点
                c.Next = cur.Next;  //新节点的后继指向当前节点
                c.Pre = cur;    //新节点的前驱指向当前节点
                cur.Next = c;   //当前节点的后继指向新节点
            }
            else
            {
                Console.WriteLine("位置错误");
            }
        }

        /// <summary>
        /// 删除指定位置的元素
        /// </summary>
        /// <param name="i"></param>
        public void Delete(int i)
        {
            if (GetLenth() < i)
            {
                Console.WriteLine("位置不正确");
                return;
            }

            //删除首节点
            if (i == 1)
            {
                Head = Head.Next;
                Head.Pre = null;
                return;
            }

            //遍历删除
            Node<T> c = Head;
            int j = 1;
            while (c.Next != null && j < i)
            {
                c = c.Next;
                ++j;
            }
            if (j == i)
            {
                //如果是最后一个节点，直接将其前驱节点的后继节点置为空，将其前驱节点置为空
                if (c.Next == null)
                {
                    c.Pre.Next = null;
                    c.Pre = null;
                }
                else
                {
                    c.Next.Pre = c.Pre;
                    c.Pre.Next = c.Next;
                }
            }
            else {
                Console.WriteLine("位置错误");
            }
        }

        /// <summary>
        /// 根据位置获取元素值
        /// </summary>
        /// <param name="i">元素位置</param>
        /// <returns>元素值</returns>
        public T GetElem(int i)
        {
            if (GetLenth() < i)
            {
                Console.WriteLine("位置不正确");
                return default(T);
            }

            if (i == 1)
            {
                return Head.Data;
            }

            Node<T> c = Head;
            int j = 1;
            while (c.Next != null && j < i)
            {
                c = c.Next;
                ++j;
            }
            if (i == j)
            {
                return c.Data;
            }
            else
            {
                Console.WriteLine("位置错误");
                return default(T);
            }
        }

        /// <summary>
        /// 根据元素值，获取元素位置
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public int GetPos(T data)
        {
            if (IsEmpty())
            {
                Console.WriteLine("链表为空");
                return -1;
            }

            if (Head.Data.Equals(data))
            {
                return 1;
            }

            Node<T> c = Head;
            int i = 1;
            int length = GetLenth();
            while (c != null && !c.Data.Equals(data) && i <= length)
            {
                c = c.Next;
                ++i;
            }
            if (i <= length)
                return i;
            else
                return -1;
        }
    }
}

Program类

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            DoubleList<string> link = new DoubleList<string>();
            link.Append("123");
            link.Append("456");
            link.Append("789");

            //link.Insert("qwe", 1);
            //link.Insert("asd", 2);
            //link.Delete(2);
            //Console.WriteLine(link.GetElem(1));
            Console.WriteLine(link.GetPos("789"));

            Node<string> c = link.Head;
            Console.WriteLine("---正序输出");

            while (c.Next!=null) {
                Console.WriteLine(c.Data);
                c = c.Next;
            }
            Console.WriteLine(c.Data);

            Console.WriteLine("---逆序输出");
            while (c != null)
            {
                Console.WriteLine(c.Data);
                c = c.Pre;
            }
            Console.WriteLine("---长度");
            Console.WriteLine(link.GetLenth());
        }
    }
}