高手来,如何用C#实现一个添加,移出操作的时间复杂度为O(1)的双向链表,什么ArrayList,Queue,LinkedList都可以不用说了,说了也不给分.

Question

高手来,如何用C#实现一个添加,移出操作的时间复杂度为O(1)的双向链表,什么ArrayList,Queue,LinkedList都可以不用说了,说了也不给分.
这些的时间复杂度都不是O(1)
可以用不安全代码....

Answer 1

纯.net的阿...可不要让我用C++写个DLL,然后调用阿....怕怕...

Answer 2

我就不说ArrayList,Queue,LinkedList
楼主给分！

Answer 3

我这可不是作业...是项目中的问题...
look
http://blog.csdn.net/zhiang75/archive/2007/11/07/1871987.aspx

Answer 4

public class MyQueue
    {
        public class Node
        {
            public Node(object data)
            {
                Data = data;
            }            public Node NextNode = null;
            public Node UpNode = null;
            public object Data = null;
        }
        Node beginNode = null;
        Node endNode = null;        public override string ToString()
        {
            return count.ToString();
        }        int count = 0;        public int Count
        {
            get
            {
                return count;
            }
            set
            {
                count = value;
            }
        }        public Node Dequeue()
        {
            if (beginNode.NextNode == null && count>1)
            {
                return null;
            }
            
            
            Node Rerurn = beginNode;
            if (Rerurn != null)
            {
                beginNode = beginNode.NextNode;
                --count;
                Rerurn.NextNode = null;
                Rerurn.UpNode = null;            }                        return Rerurn;
        }        public void Enqueue(Node node)
        {
            if (beginNode == null)
            {
                beginNode = node;
                endNode = node;
            }
            else
            {
                node.UpNode = endNode;
                endNode.NextNode = node;
                endNode = node;
                endNode.NextNode = null;
            }
            ++count;
        }
    }这个是我写的,问题是不是O(1)奇怪的.net
奇怪的问题...

Answer 5

.net奇怪吗？如果你学过基础的数据结构应该知道，链表的时间负责度不可能是o(1)的，hashtable才有可能

Answer 6

在我看来，你自己没有有创意的想法，
提出一个要求让别人完全给你实现，就是作业；//高手呢?.....都跑哪里去了?
不会你的问题或对你的问题不感兴趣的就不是高手？时间复杂度是个理论值，一般指的是自己实现的代码
但调用.NET类库中的方法可能一个语句内部实现却很复杂
要求O(1)没有意义，
另不安全代码、垃圾回收什么的，不知与时间复杂度有何关系？