I'm working on SPOJ problem where you have to write an algorithm that based on input string conditions outputs new string, but you can't exceede time limit. problem link

The fastest i could get was by using two stacks, but time limit was still exceeded, now I tried implementing doubly linked list, but it's twice slower than when I used stack. Do you have any idea on how can I increase performance of implemented linked list, or maybe should I use other data structure for this problem? Thought of implementing Node as a structure but not really sure if you can do that.

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());
            }

        }

    }

}

CodePudding user response：

An implementation using a linked list will not be as fast as one that uses StringBuilder, but assuming you are asking about a linked list based implementation I would suggest not to reimplement LinkedList. Just use the native one.

This means you don't have to change much in your code, just this:

• Define the type of the list nodes as char: new LinkedList<char>();
• Instead of .Head use .First
• Instead of .Print use string.Join("", list)

However, there are these problems in your code:

• When the input is >, you should allow the logic to execute when node is null. Currently you continue, but a null may mean that your "cursor" is in front of the non-empty list, so you should still deal with it, and move the "cursor" to list.First

• When the input is -, you should still perform the removal even when node.Previous is null, because it is not the previous node that gets removed, but the current node. We should imagine the cursor to be between two consecutive nodes, and your removal logic shows that you took as rule that the cursor is between the current node and node.Next. You could also have taken another approach (with the cursor is just before node), but important is that all your logic is consistent with this choice.

• When executing the logic for - -- in line with the previous point -- you should take into account that node.Previous could be null, and in that case you cannot do the removal as you have it. Instead, you could first assign the node reference to a temporary variable, then move the cursor, and then delete the node that is referenced by the temporary reference.

Here is the corrected code, using the native LinkedList implementation. I moved the logic for doing nothing (your continue) inside each separate case, as I find that easier to 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));
        }
    }
}