COSI 12b Lecture Notes - Lecture 11: Time Complexity
21 Oct 2018
School
Department
Course
Professor
Document Summary
Shifting elements, via adding or removing, can significantly slow the program. Arraylists internally store data in an array it is very good at reading a specific element at a specified position. Reading and replacing elements has constant time o(1). The program will run at the same speed regardless of the number of elements. Adding an element or removing an element from a specific index that causes shifting runs on linear time o(n). In linear time the number of elements affects speed. Linkedlist internally stores data as a sequence of nodes. It adds elements to the front of a list faster than arraylist by not shifting the elements (each of which is an object in a linkedlist). However, it is slower than arraylist when adding/removing in the middle of the list. Additionally, it is slower at looping through elements because it will start from index 0 every time. Iterators can be used to solve this problem.
