C# 提高链表的性能

Question

我正在研究 SPOJ 问题，您必须编写一个算法，根据输入字符串条件输出新字符串，但不能超过时间限制。 problem link

我能得到的最快的是使用两个堆栈，但仍然超过了时间限制，现在我尝试实现双向链表，但它比我使用堆栈时慢两倍。您是否知道如何提高已实现链表的性能，或者我应该使用其他数据结构来解决这个问题？考虑将 Node 实现为一个结构，但不确定是否可以做到。

using System;


namespace spoj
{
    class LinkedList
    {
        private Node head;
        private Node tail;
        private int length;

        public Node Head { get => head; }
        public Node Tail { get => tail; }
        public int Length { get => length; }

        public LinkedList(Node head = null, Node tail = null, int length = 0)
        {
            this.head = head;
            this.tail = tail;
            this.length = length;
        }

        public void AddFirst(char value)
        {
            var addFirst = new Node(value);
            addFirst.Next = head;
            addFirst.Previous = null;
            if (head != null)
                head.Previous = addFirst;
            head = addFirst;
            length++;
        }

        public void Remove(Node node)
        {
            if (node.Previous == null)
            {
                head = node.Next;
                head.Previous = null;
                length--;
            }
            else if (node.Next == null)
            {
                tail = node.Previous;
                tail.Next = null;
                length--;
            }
            else
            {
                Node temp1 = node.Previous;
                Node temp2 = node.Next;
                temp1.Next = temp2;
                temp2.Previous = temp1;
                length--;
            }
        }

        public void AddAfter(Node node, char input)
        {
            var newNode = new Node(input);
            if (node.Next == null)
            {
                node.Next = newNode;
                newNode.Previous = node;
                length++;
            }
            else
            {
                Node temp1 = node;
                Node temp2 = node.Next;
                temp1.Next = newNode;
                newNode.Previous = temp1;
                newNode.Next = temp2;
                temp2.Previous = newNode;
                length++;
            }
        }

        public string Print()
        {
            string temp = "";
            if (head == null)
                return temp;
            for (int i = 0; i < length; i++)
            {
                temp += head.Value;
                head = head.Next;
            }
            return temp;
        }


    }
    class Node
    {
        private char value;
        private Node next;
        private Node previous;

        public char Value { get => value; }
        public Node Next { get => next; set { next = value; } }
        public Node Previous { get => previous; set { previous = value; } }

        public Node(char value)
        {
            this.value = value;
            next = null;
            previous = null;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

            int testNum = Int32.Parse(Console.ReadLine());

            for (int i = 0; i < testNum; i++)
            {
                var list = new LinkedList();
                string input = Console.ReadLine();
                var node = list.Head;

                for (int j = 0; j < input.Length; j++)
                {
                    if ((input[j] == '<' && node == null) | (input[j] == '>' && (node == null || node.Next == null)) | (input[j] == '-' && (node == null || node.Previous == null)))
                        continue;
                    else if (input[j] == '<')
                    {
                        node = node.Previous;
                    }
                    else if (input[j] == '>')
                    {
                        node = node.Next;
                    }
                    else if (input[j] == '-')
                    {
                        node = node.Previous;
                        list.Remove(node.Next);
                    }
                    else
                    {
                        if (node == null)
                        {
                            list.AddFirst(input[j]);
                            node = list.Head;
                            continue;
                        }
                        list.AddAfter(node, input[j]);
                        node = node.Next;
                    }
                }

                Console.WriteLine(list.Print());
            }

        }

    }

}

Answer 1

使用链表的实现不会像使用 StringBuilder, but assuming you are asking about a linked list based implementation I would suggest not to reimplement LinkedList. Just use the native one 的那样快。

这意味着您无需对代码进行太多更改，只需更改：

定义列表节点的类型为char:new LinkedList<char>();
而不是 .Head 使用 .First
而不是 .Print 使用 string.Join("", list)

但是，您的代码中存在这些问题：

当输入为>时，您应该允许逻辑在node为null时执行。目前你continue，但是一个null可能意味着你的“光标”在non-empty列表的前面，所以你还是应该处理它，将“光标”移动到list.First
当输入为-时，即使node.Previous为null，你仍然应该执行删除，因为它不是 previous 节点被移除，但是 current 节点。我们应该想象光标位于两个连续的节点之间，并且您的删除逻辑表明您将光标位于当前 node 和 node.Next 之间作为规则。您也可以采取另一种方法（光标位于 before node），但重要的是您的所有逻辑都与此选择一致。
在执行 - 的逻辑时——与上一点一致——你应该考虑到 node.Previous 可能是 null，并且在那种情况下，您不能像您那样进行删除。相反，您可以先将节点引用分配给临时变量，然后移动光标，然后删除临时引用所引用的节点。

这是更正后的代码，使用本机 LinkedList 实现。我在每个单独的案例中移动了无所事事的逻辑（你的 continue），因为我发现更容易 understand/debug:

using System;
using System.Collections.Generic;

public class Test
{
    public static void Main()
    {
        int testNum = Int32.Parse(Console.ReadLine());

        for (int i = 0; i < testNum; i++)
        {
            var list = new LinkedList<char>();
            string input = Console.ReadLine();
            var node = list.First;
            for (int j = 0; j < input.Length; j++)
            {
                if (input[j] == '<')
                {
                    if (node != null)
                        node = node.Previous;
                }
                else if (input[j] == '>')
                {
                    if (node == null || node.Next != null)
                        node = node == null ? list.First : node.Next;
                }
                else if (input[j] == '-')
                {
                    if (node != null) {
                        var temp = node;
                        node = node.Previous;
                        list.Remove(temp);
                    }
                }
                else
                {
                    node = node == null ? list.AddFirst(input[j]) 
                                        : list.AddAfter(node, input[j]);
                }
            }
            Console.WriteLine(string.Join("", list));
        }
    }
}

C# 提高链表的性能

C# Increasing performance of a Linked List

c#

data-structures

stack

doubly-linked-list