공대생 정리노트

Array-Based List Insert : inefficient in Array. O(n) Array-Based List에서 insert 함수와 Remove 함수는 for문을 사용하므로 O(n)이 걸린다. Array Based List 장점 : 1. element의 위치를 안다면 O(1) 시간에 acccess 할 수 있다. 2. 프로그래밍하기 쉽다(배열 사용) 단점 : 1. input size가 Array size(max size) 넘어가면 extra work가 필요하다. 2. insert가 worst case의 경우 O(n)이 걸리고 best case의 경우 O(1)이 걸리는데 gap이 너무 크다. remove도 마찬가지. Space : list size가 max size(Array size)와 비..