CSE 250 Lecture 6: 3.7.17 recitation 6 remove, node and vector O(n), iterators
8 Mar 2017
School
Department
Course
Professor
Document Summary
Node(int v, node* n = nullptr): //n defaults to nullptr if not specified bool remove(int item) //one way to add this. We use two pointers because we cannot move backwards through the list. Once we reach the item we are looking for, we have to be able to access the item before it if (list == nullptr) { return false; } Node* prev = list; if (list -> value == item) { These two are equivalent list = prev -> next; prev -> next = nullptr; delete prev; Removing m items takes o(mn) while(remove(3)) {} push/pop_front push/pop_back. O(n) go through all o(1) size is kept up isempty contains operator[] O(n) to get from item 0 to item n-1, we have to traverse whole list. List: have to traverse through whole list to find the end, vector, without changing capacity, it is only o(1) if we have to double the size, then we have o(n, average: only takes o(1)
