C#数据结构与算法（六）：链表——双链表（Double-LinkedList）

vic-tory 2020-06-16 原文

1.对比单向链表

单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找

单向链表不能自我删除，需要靠辅助节点，而双向链表可以自我删除

对于单向链表的删除，我们首先要找到单向链表待删除节点的前一个节点，然后前一个节点的下一个节点指向删除节点的后一个节点。

2.双向链表的思路

3.代码实现

    public class ListNode
    {
        public ListNode(int id, string name, string nickName)
        {
            this.Id = id;
            this.Name = name;
            this.NickName = nickName;
        }
        public int Id { get; set; }

        public string Name { get; set; }

        public string NickName { get; set; }

        public ListNode Next { get; set; }

        public ListNode Pre { get; set; }
    }

  public class DoubleLinkedList
    {
        public ListNode HeadNode;

        public DoubleLinkedList()
        {
            HeadNode = new ListNode(0, "", "");
        }

        public void GetList()
        {
            var temp = HeadNode.Next;

            while (temp != null)
            {
                Console.WriteLine($"id={temp.Id},name={temp.Name},nickName={temp.NickName}");

                temp = temp.Next;
            }
        }

        public void Add(ListNode listNode)
        {
            var temp = HeadNode;

            //如果temp.Next为null就表示temp为最后一个节点；
            while (temp.Next != null)
            {
                temp = temp.Next;
            }
            //把最后的节点指向待添加的节点
            temp.Next = listNode;

            //将待添加的前一个节点指向temp
            listNode.Pre = temp;
        }

        public void Update(ListNode listNode)
        {
            var temp = HeadNode;

            //bool flag = false;

            while (temp.Next != null)
            {
                if (temp.Next.Id == listNode.Id)
                {
                    //flag = true;
                    temp.Next.Name = listNode.Name;

                    temp.Next.NickName = listNode.NickName;

                    break;
                }

                temp = temp.Next;
            }

            //if (flag)
            //{
            //    temp.Next.Name = listNode.Name;
            //    temp.Next.NickName = listNode.NickName;
            //}
            //else Console.WriteLine("未找到");
        }

        public void Delete(int id)
        {
            /*{
                var temp = HeadNode;

                while (temp.Next != null)
                {
                    if (temp.Next.Id == id)
                    {
                        if (temp.Next.Next != null)
                            temp.Next.Next.Pre = temp;
                        temp.Next.Pre.Next = temp.Next.Next;
                    }
                    temp = temp.Next;
                }
            }*/

            var temp = HeadNode.Next;

            while (temp != null)
            {
                if (temp.Id == id)
                {
                    //如果是最后一个节点，那么就不需要执行下面的temp.Next.Pre = temp.Pre;
                    if (temp.Next != null)

                        temp.Next.Pre = temp.Pre;//将temp的后一个节点的前一个指针指向temp的前一个节点

                    temp.Pre.Next = temp.Next;//将temp的前一个节点的后一个指针指向temp的后一个节点
                }

                temp = temp.Next;
            }
        }

        public static void Test()
        {
            Console.WriteLine("双向链表的测试\n");

            ListNode listNode1 = new ListNode(1, "宋江", "及时雨");
            ListNode listNode2 = new ListNode(2, "卢俊义", "玉麒麟");
            ListNode listNode3 = new ListNode(3, "吴用", "智多星");
            ListNode listNode4 = new ListNode(4, "林冲", "豹子头");

            DoubleLinkedList linkedList = new DoubleLinkedList();

            //添加链表数据
            linkedList.Add(listNode1);
            linkedList.Add(listNode2);
            linkedList.Add(listNode3);
            linkedList.Add(listNode4);

            //获取链表所有数据        
            linkedList.GetList();

            linkedList.Update(new ListNode(1, "宋", "及时"));

            Console.WriteLine("\n获取链表修改后的所有数据\n");
            linkedList.GetList();


            linkedList.Delete(1);

            Console.WriteLine("\n获取链表删除后的所有数据\n");
            linkedList.GetList();
        }
    }