Array(배열) vs LinkedList(연결리스트)

Array (배열)

• 데이터 접근 : O(1) (인덱스만 알고 있으면)
• 값을 삭제, 삽입할때 : O(n) # 맨끝에 삽입하는 경우 O(1)이지만 이러한 경우는 자주있지 않다.
• 물리적 주소 : 순차적 (연속)
• 사이즈 : 선언할 때 고정

조회는 빠르나, 삽입/삭제시 배열의 연속성을 유지하기위해 앞당기거나, 뒤로 미루는 데이터 이동 발생으로 오래걸림
-> 조회할 때, 데이터의 삽입/삭제가 적을때 사용

LinkedList (연결리스트)

• 데이터 접근 : O(n) (하나씩 접근하여 찾음)
• 값을 삭제, 삽입할때 : O(1)
• 물리적 주소 : 순차적이지 않음 (랜덤)
• 사이즈 : 동적 (삽입때마다 늘어남)

조회는 느리나, 삽입/삭제시 연결되는 논리적 주소만 바꿔주면 되기 때문에 빠름
-> 조회보다 삽입/삭제가 빈번할 때, 크기가 정해지지 않았을때 사용