英文:
Does C# store the address of the last element in a LinkedList?
问题
假设我们在C#中有一个链表，如下所示：
LinkedList<int> LList = new LinkedList<int>({1, 2, 3, 4, 5, 6});
链表作为一种数据结构的一个关键特性是，我们不能像数组一样直接访问第i个元素。
但是当我们访问LList.Last时，我认为C#已经知道了最后一个元素的地址，因此它不需要遍历整个链表。
这是否属实？我在哪里可以确认这个信息？
我尝试在文档中查找，但在这个细节层面上我找不到任何信息。
英文:
Suppode we have a linked list in C#, say
LinkedList<int> LList = new LinkedList<int>({1, 2, 3, 4, 5, 6});
A key characteristic of a linked list as a data structure is that we don't have direct access to the i-th element like we do with an array.
But when we access LList.Last, I assume that C# already has the address of the last element, so that it doesn't have to go through the whole list.
Is this actually the case? Where can I confirm this information?
I've tried to look in the documentation, but I couldn't find anything in this level of detail.
答案1
得分: 4
从文档：
检索此属性的值是O(1)操作。
虽然它没有明确说明它是如何实现的，但它是O(1)操作的事实强烈暗示着直接指向最后一个元素的指针（或至少以某种方式引用最后一个节点而无需遍历）。
LinkedList 本身的文档表明它是一个“双向链表”，意味着每个节点都有指向下一个和前一个节点的指针，因此对最后一个节点的引用很容易：
var lastNode = this.Head.Prev; // this.Head points to the “first” node
英文:
From the documentation:
>Retrieving the value of this property is an O(1) operation.
While it doesn't say exactly how it is implemented, the fast that it's an O(1) operation strongly suggests that there's a pointer directly to the last element (or at least some way to reference the last node without traversal).
The documentation for LinkedList itself states that it's a "doubly-linked list", meaning that each node has a pointer to the next and previous nodes, so a reference to the last node is trivial:
var lastNode = this.Head.Prev; // this.Head points to the "first" node
答案2
得分: 1
这是实现的一部分。文档中说它是一个"双向链表"。据我所知，要直接访问链表中的最后一个元素，你需要：
- 直接引用最后一个元素（通常称为"Tail"）
或者
- 使用循环链表（第一个元素指向的上一个元素是最后一个元素）。
以下是在Microsoft .NET Reference Source中的实现方式（我不确定在更近期的版本如.NET Core / .NET中是如何实现的）：
public class LinkedList<T>
{
// This LinkedList is a doubly-Linked circular list.
public LinkedListNode<T> Last {
get { return head == null? null: head.prev;}
}
}
在这个实现中，它是一个循环链表，因此你可以在O(1)时间内直接访问最后一个元素。
英文:
It's part of the implementation. Documentation says it's a "double linked list". AFAIK to directly access the last element in a linked list you need :
- a direct reference to the last element (usually called "Tail")
OR
- a circular linked list (the previous element pointed by the first element is the last element).
Here is how it's implemented in Microsoft .NET Reference Source (I'm not sure how it's done in more recent versions like .NET Core / .NET) :
public class LinkedList<T>
{
// This LinkedList is a doubly-Linked circular list.
public LinkedListNode<T> Last {
get { return head == null? null: head.prev;}
}
}
In that implementation, it's a circular linked list and so you can directly access the last element in O(1) time.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论