배열 VS 연결 리스트 #8
Description
배열 VS 연결 리스트
| 배열 | 연결 리스트 | |
|---|---|---|
| k번째 원소의 접근1 | O(1) | O(k) |
| 임의 위치에 원소 추가/제거1 | O(N) | O(1) |
| 메모리 상의 배치 | 연속 | 불연속 |
| 추가적으로 필요한 공간(Overhead) | 없음 | O(N) |
-
추가하고 싶은 위치의 주소를 알고 있을 경우, 임의 위치에 원소 추가/제거가 O(1)이 걸림. 알고 있지 않은 경우(ex 3번째 원소 뒤에 84를 추가), 해당 위치까지 찾아가는 시간이 걸리기 때문에 O(1)이 아님.
-
연결리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야함. 따라서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요함. (64비트 컴퓨터면 8N) 즉, N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.
손코딩 문제
1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 List의 길이를 효율적으로 구하는 방법?
- 동일한 노드가 나올 때까지 계속 다음 노드로 가면 됨. 공간복잡도는 O(1), 시간복잡도는 O(N)
2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법?
- 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함.
- 그 후 다시 두 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날때까지 두 시작점을 동시에 한 칸씩 전진시키면 됨. 공간복잡도 O(1), 시간복잡도 O(A+B)
3. 주어진 연결 리스트 안에 사이클이 있는지 판단하라
- Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
- 내가 생각한 답: 연결리스트의 개수를 구한 다음에 각 노드의 next값을 봤는데 -1이 나오지 않으면 사이클 존재 ( -> 안됨. 왜냐하면 사이클이 있는경우에는 연결 리스트의 개수를 제대로 구할 수 없다)
- 정답: 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있는 경우, 두 커서는 반드시 만나게 된다. 반대로 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달함.