LinkedList vs List

Question

Possible Duplicate:
When should I use a List vs a LinkedList

If I expect not to use the access by index for my data structure how much do I save by using LinkedList over List ? If if am not 100% sure I will never use access by index, I would like to know the difference.

Suppose I have N instances. inserting and removing in a LinkedList will only be a o(1) op , where as in List it may me be O(n), but since it it optimized, it would be nice to know what the difference is for some values of n. say N = 1,000,000 and N = 1,000,000,000

@Mr. Dissapointment: Disappointed now? :P (sorry couldn't resist) — Tony The Lion, May 03 '11 at 14:22
A LinkList is not a generic collection its a LinkList, a List is the generic version of a simple array. Your question is like asking if a cat will enjoy eating dog food. — Security Hound, May 03 '11 at 14:24
@Tony: Oh, Tony, ...almost always, but I much prefer disappointing others. — Grant Thomas, May 03 '11 at 14:26
@Ramhound: No, the answer to that question depends on the cat. The answer to *this* question is that you should always use the generic collections, if possible. The internal storage algorithms are sufficiently optimized to the point that you're not supposed to have to worry about whether it's a linked list or an array or a hashtable or whatever. — Cody Gray - on strike, May 03 '11 at 14:28
@Disappointment: I sincerely hope that is a joke?! (about disappointing others) — Tony The Lion, May 03 '11 at 14:29
@Cody - I don't disagree. I think my point was he has no idea what a LinkedList is * meow *. — Security Hound, May 03 '11 at 14:30
@Ramhound I have implemened a LinkedList myself ;-), so yes I think I know what it is. (why would you bash me for asking this?) As I said I would like to know how much time I will save by using LinkedList. Let me try to answer it myself then. Suppose I have N instances. inserting and removing in a LinkedList will only be a o(1) op , where as in List is may me O(n), but since it it optimized, it would be nice to know what the difference is for some values of n. — HCP, May 04 '11 at 08:26

score 8 · Accepted Answer · edited May 23 '17 at 12:34

8

List<T> is just a wrapper over an Array. LinkedList<T> is only at it's most efficient if you are accessing sequential data (either forwards or backwards).

Linked lists provide very fast insertion or deletion of a list member. Each member in a linked list contains a pointer to the next member in the list so to insert a member at position i:

update the pointer in member i-1 to point to the new member
set the pointer in the new member to point to member i

Check this: When should I use a List vs a LinkedList

edited May 23 '17 at 12:34

Community

1
1

answered May 03 '11 at 14:25

Priyank

10,503
2
27
25

+1000 If I could for taking the time to answer a vague question ( with the correct answer ). – Security Hound May 03 '11 at 14:31
Ehhh, the claim that `List` is "just a wrapper over an array" is problematic. First of all, it's not strictly true, the specific implementation depends on the size of the collection. And second, it's an implementation detail that's not guaranteed to remain forever consistent. That's not something you should consider when choosing to use `List`. The point is to let the collection class manage your data using the most appropriate algorithm, and you just get on with your life. If you care about the implementation details, you're already using the wrong framework. – Cody Gray - on strike May 03 '11 at 14:35
@Cody: I have to agree on underline implementation logic. It is upto Microsoft. – Priyank May 03 '11 at 14:48

score 3 · Answer 2 · answered May 03 '11 at 14:24

LinkedList<T> is useful if you perform many random insertions and deletions of items in your list. Otherwise a List<T> is probably the best choice as it carries no overhead for linking the elements in the list (and also can be indexed).

However, if you are concerned about performance you really need to test your actual code.

LinkedList vs List

2 Answers2

Linked