[C++] 배열과 연결 리스트의 차이

1. 속도

  - 배열은 인덱스만 알고 있다면 O(1)만에 접근 가능

  - 연결리스트는 O(n) : 각 위치를 따라가서 접근하기 때문에 상대적으로 느림.

 

2. 데이터 삽입/삭제

   - 배열에 공간이 있고 맨 끝에 삽입한다면 O(1), 만약 공간에 여유가 없다면 realloc() 또는 새롭게 할당 필요.

   - 연결 리스트는 삽입/삭제가 자유로움.