선형 자료 구조
선형 자료 구조
일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열입니다. 배열과 같이 일렬로 늘어선 자료등르 저장하기 위한 자료 구조인 동적 배열과 연결 리스트에 대해 다룹니다. 이 두 자료 구조는 배열과 비슷하지만, 배열에서 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있도록 도와줍니다. 두 자료 구조는 서로 다른 특성을 갖고 있습니다.
동적 배열
배열의 가장 큰 문제는 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료는 저장할 수 없다. 이와 같은 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변하는
동적 배열이다.
동적 배열의 특징
- 원소들은 메모리의 연속된 위치에 저장된다.
- 주어진 위취의 원소를 반환하거나 변경하는 동작은 O(1)에 할 수 있다.
- 배열의 크기를 변경하는
resize()연산이 가능하며 시간은 O(N)이 걸린다. - 주어진 원소를 배열 맨 끝에 추가해 크기를 1 늘리는
append()연산을 지원한다.
연결 리스트
배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위취에서 원소를 삭제하는 것은 시간이 오래 걸리는 작업입니다. 해당 위치뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문입니다. 평균적인 경우 이 작업들에는 원소의 개수에 선형 비례하는 시간이 걸립니다. 이와 같은 문제를 해결하기 위한 고안된 자료 구조가
연결 리스트로, 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해줍니다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있다면, 연결 리스트는 원소들이 메모리 여기 저기 흩어져 있고 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현됩니다.
동적 배열과 연결 리스트의 비교
동적 배열과 연결 리스트의 가증 큰 차이점은 삽입과 삭제 그리고 임의의 원소에 접근하는데 드는 시간입니다. 삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 결우에는 동적 배열이 거의 항상 더 좋은 선택입니다. 임의의 원소를 접근하는 것이 아닝라 모든 원소들을 순회하며 삽입과 삭제를 한다면 연결 리스트가 좋은 선택입니다.
| 작업 | 동적 배열 | 연결 리스트 |
|---|---|---|
| 이전/다음 원소 찾기 | O(1) | O(1) |
| 맨 뒤에 원소 추가/삭제하기 | O(1) | O(1) |
| 맨 뒤 이외의 위치에 원소 추가/삭제하기 | O(n) | O(1) |
| 임의의 위치의 원소 찾기 | O(1) | O(n) |
| 크기 구하기 | O(1) | O(n) 구현에 따라 O(1) |
문제: 조세푸스 문제(JOSEPHUS, 하)
