代码之家 › 专栏 › 技术社区 › stackoverflowuser

应该使用哪种方法:数组还是链表?

linked-list data-structures arrays c#

stackoverflowuser · 技术社区 · 15 年前

我计划在不使用 Queue<T> Arrays 和 LinkedList<T>

像这样的

public class BoundedQueue<T>
{
   private T[] queue;
   int queueSize;

   public BoundedQueue(int size)
   {
      this.queueSize = size;
      queue = new T[size + 1];
   }
}

而不是

public class BoundedQueue<T>
{
   private LinkedList<T> queue;
   int queueSize;

   public BoundedQueue(int size)
   {
      this.queueSize = size;
      queue = new LinkedList<T>();
   }
}

我之所以选择数组是因为效率和集合的大小是固定的。我想听听其他的意见。谢谢。

6 回复 | 直到 15 年前

Mark Byers 15 年前

你当然应该使用 Queue<T> LinkedList<T> 但是对于一个通用的图书馆,你会想要更快的。

您可以通过使用.NETReflector了解它是如何在.NET中实现的。以下是它的字段:

private T[] _array;
private const int _DefaultCapacity = 4;
private static T[] _emptyArray;
private const int _GrowFactor = 200;
private int _head;
private const int _MinimumGrow = 4;
private const int _ShrinkThreshold = 0x20;
private int _size;
[NonSerialized]
private object _syncRoot;
private int _tail;
private int _version;

如您所见,它使用一个数组。对于涉及如何调整数组大小的许多字段来说,这也是相当复杂的。即使您正在实现一个有界数组,您也希望允许数组可以大于容量,以避免在内存中不断移动项。

关于线程安全,这两种类型都不提供任何保证。例如,在 链接列表<T> 上面写着:

此类型不是线程安全的。如果LinkedList需要由多个线程访问,则需要实现它们自己的同步机制。

codekaizen 12 年前

但不,这与CPU缓存的工作方式极不兼容

孩子们读了之后哭了 are here

Dan Tao 15 年前

我不知道你为什么要排除使用 Queue<T> 在内部,尤其是考虑到你准备使用 LinkedList<T> (它们在同一个集合中)。A 排队<T> 将为您提供最佳的性能和内存使用率。你的班级可以是这样的:

public class BoundedQueue<T>
{
    private Queue<T> _queue;
    private int _maxSize;

    public BoundedQueue(int maxSize)
    {
        if (maxSize <= 0)
            throw new ArgumentOutOfRangeException("maxSize");

        _queue = new Queue<T>(maxSize);
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _queue.Count; }
    }

    /// <summary>
    /// Adds a new item to the queue and, if the queue is at its
    /// maximum capacity, also removes the oldest item
    /// </summary>
    /// <returns>
    /// True if an item was dequeued during this operation;
    /// otherwise, false
    /// </returns>
    public bool EnqueueDequeue(T value, out T dequeued)
    {
        dequeued = default(T);
        bool dequeueOccurred = false;

        if (_queue.Count == _maxSize)
        {
            dequeued = _queue.Dequeue();
            dequeueOccurred = true;
        }

        _queue.Enqueue(value);

        return dequeueOccurred;
    }
}

排队<T>

gtrak 15 年前

例如,如果你有[1,2,3,4,5],头是1,你加上6,你会从后面掉5,我猜是6。6将是新的头,但数组的内容将是[1,2,3,4,6]。

David Menard 15 年前

阵列: -如果不在末尾插入(以及删除),则向数组中添加项的成本相对较高,因为必须移动所有数组元素。 -如果在末尾添加对象,则效率非常高

链接列表: -必须使用访问器(迭代器)访问元素。

所以你试图实现一个队列。。。但是什么样的队伍?

如果实现先进先出(或后进后出)队列(如堆栈),最好使用链表,因为可以始终使用相同的访问器访问列表的前端或后端。

但是,如果您想要一个队列,并且必须不断地访问不同位置的元素,那么就使用数组吧!

根据我对你任务的了解,我会推荐一个链表。。。但你会最清楚的!

只有当队列中有很多元素时,这才是一个问题。如果你保持在几千以下,那就没有了

希望有帮助

mattmc3 15 年前

[1, 2, 3] -> [2, 3, 4] 还是最后一件要换成这样 [1, 2, 3] -> [1, 2, 4] ? 如果是前者,那么我推荐LinkedList。如果是后者,则为数组或列表<T>很好。我只是想我会问,因为你的对象的行为将决定适当的行动过程,而这种行为从来没有被定义为我所能说的。也许除了我以外的每个人都知道你所说的“有界队列”是什么意思,但我不想假设。