Lecture overview -- Keyboard shortcut: 'u'  Previous page: Sample use of class <b><kbd>LinkedList<T></kbd></b> -- Keyboard shortcut: 'p'  Next page: Using Collections through Interfaces -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home  Page 20 : 36
Object-oriented Programming in C#
Collection Classes
Time complexity overview: Collection classes

Assume that we work on a collection with n elements

OperationCollection<T>List<T>LinkedList<T>
this[i] O(1) O(1) -
Count O(1) O(1) O(1)
Add(e) O(1) or O(n) O(1) or O(n) O(1)
Insert(i,e) O(n) O(n) -
Remove(e) O(n) O(n) O(n)
IndexOf(e) O(n) O(n) -
Contains(e) O(n) O(n) O(n)
BinarySearch(e)-O(log n) -
Sort()-O(n log n) or O(n2)-
AddBefore(lln)--O(1)
AddAfter(lln,e)--O(1)
Remove(lln)--O(1)
RemoveFirst()--O(1)
RemoveLast()--O(1)

Time complexities of important operations in the classes Collection<T>, List<T>, and LinkedList<T>.