The List structure is what many languages would call a vector or an array. So complexity of insertion/deletion is indeed O(n).
List
O(n)
