Is List<T> a linked list?

Question

Is System.Collections.Generic.List<T> a type of linked list(not the LinkedList<T> class)?

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence.

^{A linked list whose nodes contain two fields: an integer value and a link to the next node.
The last node is linked to a terminator used to signify the end of the list.}

wikipedia.org

If it is, what kind of linked list is it?

Answer 1

No, List<T> is backed by an array - it's essentially a generic version of ArrayList from .NET 1.0. From the docs:

The List<T> class is the generic equivalent of the ArrayList class. It implements the IList<T> generic interface using an array whose size is dynamically increased as required.

Note that due to being backed by an array, its access via indexers is O(1) as opposed to the O(N) for a linked list.

If you want a linked list, use LinkedList<T>. Note that this is a doubly-linked list. I don't believe .NET exposes a singly-linked list type.

Answer 2

List<T>, from a... technical perspective, is NOT a type of linked list.

If you want to have a linked list in C# :

• either use the built-in LinkedList<T> type (for double-linked lists)
• or create an implementation of your own (if you want a singly-linked one) - here's an example