双向链表与单链表的区别

1. 单链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找
2. 单链表不能自我删除，需要靠被删除节点的前一个节点删除，而双向链表可以自我删除
3. 双向链表比单链表更占用空间，因为多了一个pre指针

   结构

双向链表的节点

    //链表的节点
    public class LinkNode2
    {
        #region 数据域
        public int index;
        public string str;
        #endregion
        #region 指针域
        public LinkNode2 pre;//上一个节点
        public LinkNode2 next;//下一个节点
        #endregion
        //创建这个节点时，存如数据
        public LinkNode2(int index, string str)
        {
            this.index = index;
            this.str = str;
        }
    }

双向链表对象类

    public class DoubleLinkList
    {
        public LinkNode2 head = new LinkNode2(0, "");
        //显示链表数据
        public void show()
        {
            LinkNode2 temp = head.next;
            while (temp != null)
            {
                Console.WriteLine(temp.index+temp.str);
                temp = temp.next;
            }
        }
        //1.添加节点到尾部
        //2.插入节点
        //3.删除节点
    }

1.添加节点到尾部

在DoubleLinkList类里面的方法

        //添加到双链表的末尾
        public void AddLast(LinkNode2 newnode)
        {
            LinkNode2 temp = head;
            while (true)
            {
                if(temp.next==null)
                {
                    temp.next = newnode;
                    newnode.pre = temp;
                    break;
                }
                temp = temp.next;
            }
        }

2.插入节点

在DoubleLinkList类里面的方法

        //按照编号的顺序升序添加，(重复的也可以添加)
        public void AddOrder(LinkNode2 newnode)
        {
            LinkNode2 temp = head;
            while (true)
            {
                if (temp.next == null)
                {
                    temp.next = newnode;
                    newnode.pre = temp;
                    break;
                }
                if (temp.next.index >= newnode.index)//这是升序
                {
                    //看图，就能明白
                    newnode.next = temp.next;
                    temp.next.pre = newnode;
                    temp.next = newnode;
                    newnode.pre = temp;
                    break;
                }
                temp = temp.next;
            }
        }

3.删除节点

在DoubleLinkList类里面的方法

        //根据index删除节点
        public void Delete(int index)
        {
            LinkNode2 temp = head.next;
            while (true)
            {
                if (temp == null)
                {
                    Console.WriteLine("没有这个数据");
                    break;
                }
                if (temp.index == index)//找到了这个数据
                {
                    temp.pre.next = temp.next;
                    if(temp.next!=null)//不是最后一个节点才给下一个节点的pre引用，不然temp.next==null,temp.next.pre要空指针
                        temp.next.pre = temp.pre;
                    break;
                }
                temp = temp.next;
            }
        }