4.6 연습 문제¶

4.6.1 개념 확인¶

배열과 단일 연결 리스트에 모두 [A, B, C, D, E]가 순서대로 저장되어 있다. 네 번째 원소 D를 읽으려고 한다.

배열에서는 어떤 인덱스를 바로 사용할 수 있는가?
단일 연결 리스트에서는 머리 노드 A부터 next를 따라 어떤 노드를 차례대로 거쳐야 하는가?
읽으려는 원소가 뒤쪽에 있을수록 두 구조에 필요한 단계 수는 어떻게 변하는가? 위치를 기준으로 반복해서 읽을 때는 어느 구조가 더 적합하며, 그 이유는 무엇인가?

참고 답안

인덱스가 0부터 시작한다면 네 번째 원소의 인덱스는 3이므로, 배열에서는 arr[3]을 바로 읽을 수 있다.
단일 연결 리스트는 맨 앞부터 시작해야 한다. 접근 경로는 A → B → C → D이며, next를 따라 3번 이동해야 한다.
배열은 시작 주소와 인덱스로 원소의 위치를 바로 계산할 수 있으므로 위치를 기준으로 접근하는 시간 복잡도가 \(O(1)\)이다. 단일 연결 리스트에서 \(k\)번째 노드에 접근하려면 머리 노드부터 next를 따라 \(k-1\)번 이동해야 하므로, 최악의 경우 \(O(n)\) 시간이 필요하다.

여기서는 위치를 기준으로 읽는 연산만 비교한 것이며, 연결 리스트가 모든 연산에서 더 느리다는 뜻은 아니다.

배열과 단일 연결 리스트에 모두 A, B, C, D가 저장되어 있다. B 뒤에 X를 삽입하려고 한다.

참고 답안

배열에서는 먼저 D를 오른쪽으로 한 칸 옮기고, 다음으로 C를 오른쪽으로 한 칸 옮긴 뒤, X를 인덱스 2에 넣는다. 결과는 [A, B, X, C, D]다.
B.next는 원래 C를 가리킨다. 먼저 X.next = B.next로 설정하여 X가 C를 가리키게 하고, 다음으로 B.next = X로 설정한다. 결과는 A → B → X → C → D다. 기존 연결을 저장하지 않은 채 B.next를 먼저 덮어쓰면 C를 찾지 못할 수 있다.
B의 위치를 알고 있다면 연결 리스트의 삽입은 연결 두 개만 수정하면 되므로 \(O(1)\) 시간에 완료할 수 있다. 맨 앞부터 B를 찾아야 한다면 탐색 자체에 \(O(n)\) 시간이 걸릴 수 있다.

배열로 구현한 리스트의 현재 내용은 [A, B, C]이고, 길이는 size = 3, 용량은 capacity = 4다. 용량이 부족해지면 새 배열의 용량을 기존의 2배로 늘리기로 한다.

참고 답안

D는 마지막 빈자리에 넣을 수 있다. 내용은 [A, B, C, D]가 되고, size = 4, capacity = 4이며 용량 확장은 필요 없다.
이어서 E를 추가할 때는 빈자리가 없으므로 용량이 8인 새 배열을 만들어야 한다. 기존 원소 A, B, C, D 네 개를 복사한 뒤 E를 넣는다. 이때 size = 5, capacity = 8이다.
원래 배열 자체의 길이가 늘어난 것은 아니다. 더 큰 새 배열을 만들고 기존 원소를 복사한 뒤, 새 배열을 내부 저장 공간으로 사용하기 때문에 사용자에게는 용량이 늘어난 것으로 보인다.

배열 digits에는 음이 아닌 정수의 각 자릿수가 왼쪽부터 저장되어 있다. 예를 들어 [3, 0, 8]은 308을 나타낸다. 숫자 0은 [0]으로 나타내며, 그 밖의 입력은 첫 번째 자릿수가 0이 아니다.

십진수의 세로셈 덧셈 과정을 따라 이 정수에 1을 더한 뒤, 결과를 같은 배열 형식으로 반환하라. digits를 직접 수정해도 된다. 맨 앞에 새로운 자리 올림이 생기면 더 긴 배열을 반환할 수 있다.

풀이 힌트

단일 연결 리스트의 머리 노드 head가 주어진다. 각 노드에는 값과 다음 노드를 가리키는 next가 있다.

반복 방식으로 모든 노드 사이의 연결 방향을 뒤집고, 뒤집힌 리스트의 머리 노드를 반환하라. 새로운 연결 리스트 노드를 만들어서는 안 된다.

풀이 힌트