- 자료구조는 크게 연속방식과 연결 방식으로 나뉜다. 연속 방식은 메모리 공간을 기반으로 두고 있고 연결 방식은 포인터를 기반으로 두고 있다. 이중에서 배열은 연속 방식, 링크드 리스는 연결 방식을 사용하고 있다.
1. 배열
1.1 탐색
- 배열은 위에서 말한대로 이미 지정된 크기의 연속된 메모리 주소를 할당받고 있다. 따라서 크기 수정이 불가능하다.(동적 배열은 가능)
- 이 때문에 인덱스를 가지고 있어 탐색을 하는데 O(1)의 시간복잡도만을 가진다.
- 예시로 4바이트 int 배열에서 3번째 값의 주소는 2(=3-1)*4 = 8에 의해 ox08에 존재한다.
1.2 추가 및 삭제
- 하지만 변경의 경우 맨 뒤의 데이터가 아니라면 기존 데이터들을 옮겨야 하기 때문에 O(n)의 시간 복잡도가 걸린다.
2. 링크드 리스트
2.1 탐색
- 링크드리스트는 동적인 자료구조로 노드라는 공간에 저장 데이터와 그 다음 값의 메모리 주소를 가지고 있다. 따라서 데이터를 추가하고 삭제하는데 자유롭다.
- 하지만 탐색 시, 리스트는 순차적으로 head부터 목표까지 하나씩 탐색을 해야하기 때문에 O(n)의 시간복잡도를 가지고 있다.
2.2 추가 및 삭제
- 연결리스트는 데이터를 추가 및 삭제하는데 있어 O(1)의 시간복잡도를 가진다. 하지만 추가하려는 위치가 맨 앞이 아니라면 탐색을 해야하므로 O(n)의 시간 복잡도가 추가된다.
3. 탐색은 배열이 좋은건 알겠는데 삽입/삭제는 왜 링크드리스트가 좋을까?
-
처음에 이 이론을 듣고 둘다 삽입/삭제가 O(n)이면 탐색이라도 O(1)인 배열만 쓰는게 맞지 않나?라고 생각했는데 삽입/삭제가 많은 로직이라면 링크드 리스트가 맞다고들 한다.
-
서칭도 해보고 고민도 해본 결과, 삽입/삭제 시 실질적으로 탐색 연산이 들어가 O(n)이지만, 내부적으로 중간 포인터의 위치를 따로 저장해두거나 삽입, 삭제 시 해당 위치를 캐싱해두고 위치 데이터가 쌓이면서 좀 더 빠른 탐색이 가능해져서라고 결론을 지었다.
-
찜찜하니 계속 찾아보며 업데이트 해보겠다.
