728x90
배열 (Array)
[ 배열의 특징 ]
- 순서가 있습니다. (메모리 순서대로)
- 연속된 공간을 '미리' 정해서 사용해야 합니다. (확정된 메모리 공간을 할당받아 써야 하므로)
- N번째 데이터에 접근하기 위해 복잡한 과정 필요없이 그냥 덧셈과 곱셈 한번이면 가능합니다. (n번째 데이터 접근 : 시작 주소 + (n-1) * 해당 자료형 크기)
💡 배열의 시간복잡도
- 데이터 읽기, 수정 : O(1)
- 데이터 추가, 삭제 : O(N)
- 예외 : 배열에 빈 공간이 존재하는걸 허용하며 짜는 경우라면 마지막 데이터의 추가, 삭제는 O(1) </aside>
리스트 (LinkedList)
링크드 리스트는 일반적인 리스트로 불리며, 노드로 연결된 데이터를 저장하는 자료구조입니다. 링크드 리스트는 데이터의 순서를 유지할 수 없지만, 데이터를 추가하거나 삭제하는 것이 쉽습니다. 또한, 배열과 달리 배열의 크기를 우리가 지정하거나 변경할 필요가 없습니다.
- 배열은 메모리 자체에 순서대로 들어가 있으므로 다음 데이터는 물론이고, n번째 데이터도 쉽게 알 수 있다.
- 하지만 리스트는 현재 그림상으로는 리스트에서 첫번째 데이터인 '12'의 위치는 알 수 있지만 n번째 데이터는 커녕 바로 다음 데이터도 어디에 있는지 알 수 없다.
[ 배열 vs 리스트 ]
- 리스트
- 일반적으로 데이터의 추가, 삭제가 많은 경우 리스트를 사용하는 것이 효율이 좋습니다.
- 배열
- 데이터가 자주 추가, 삭제 되지 않고, 읽고 수정하는 경우가 많을 때 배열을 사용하는 것이 효율이 좋습니다.