CODEWITHSUNDEEP
c#listimplementation
hamid.sh
hamid.sh

Reputation: 1066

Implementation of List<T> in C#?

First I'm sorry for my bad English, then my question;

I know that there are many questions like this one, in here, but I didn't find a straight answer. Is List<T> implemented using some sort of "linked list" mechanism? Or it is just an over-engineered array?

I'm interested in performance issues of lists, like sorting, inserting and deleting items. E.g. for insertion action, 'linked list' just defines some new connections, but array needs to shift its values. What about list?

Upvotes: 0

Views: 881

Answers (4)

appcoder
appcoder

Reputation: 649

No, List is not an linked list and its just a convenient strongly typed array. I would not call it over engineered array, but its one of the best features introduced from C# 2.0. If performance with generic list is a concern they can be optmized based on use cases but just inserting does not take much time even in a huge list.

Upvotes: 2

Hans Passant
Hans Passant

Reputation: 941327

Yes, List<> is an array. And yes, Insert() is an O(n) operation.

It is important that it works that way, modern processors are very dependent on their caches. The RAM in your machine is very slow, much slower than the processor. The caches make sequential access to memory fast. Which is the opposite of what a LinkedList<> does. A single cache miss costs hundreds of cpu cycles. Do note another significant disadvantage of LinkedList<>, indexing it costs O(n) unless you can index sequentially. It is always O(1) for List.

These are but rough guidelines, nobody can advice you to replace your List with a LinkedList. Only a profiler can do that.

Upvotes: 6

Karl Anderson
Karl Anderson

Reputation: 34846

I would consider List<T> an over-engineered array more than a "linked list".

As for performance, since List<T> is not inherently sorted, then the performance is dependent upon the sorting algorithm (bubble sort is extremely slow as every item needs to checked).

Inserting and deleting items into a List<T> is quite simple and performance can be improved for inserting items by using List<T>.Add() vs. List<T>.Insert(), as .Add() will add it to the end of the list.

For a thorough treatment of the performance and general use cases for various .NET collection types, then read C#/.NET Fundamentals: Choosing the Right Collection Class

Upvotes: 2

Nikhil Agrawal
Nikhil Agrawal

Reputation: 48558

I would say it is just an over-engineered array. For Linked List you need LinkedList<T>. For more on LinkedList<T> read this

Upvotes: 3

Related Questions