Time complexity overview: Collection classes

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

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

Operation	`Collection<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(n²)	-
`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>.

Wikipedia: Big O Notation