# 배열과 링크드리스트

## 배열
- 배열은 연속적인 메모리 공간에 동일한 타입의 데이터를 순서대로 저장합니다.
- 인덱스를 이용하여 O(1)의 시간복잡도로 특정요소에 접근할 수 있다.
- 배열의 중간에 요소를 삽입하거나 삭제하는 작업은 O(n)의 시간 복잡도를 가집니다. 이는 해당 연산을 수행하면서 요소들을 이동시켜야 하기 때문입니다.
- 중간에 값을 추가할수있다, 하지만 추가하게된다면 전체적으로 한칸씩 이동하게 되기때문에 전체를 순회해야한다.

## 링크드 리스트
- 링크드 리스트는 각 요소가 데이터와 다음 노드를 가리키는 포인터를 포함하는 노드들로 이루어져 있습니다. 이중 링크드 리스트의 경우 이전 노드를 가리키는 포인터도 포함합니다.

- 특정 노드값에 접근하려면 첫 노드부터 시작해서 연결된노드를 따라가서 특정값을 찾아야한다.O(n)

- 노드의 위치를 알고 있다면 삽입/삭제는 O(1)이다. 다만, 특정 위치에 삽입하거나 삭제하기 전에 그 위치를 찾기위해 노드를 순회할때에는 O(n)이다.

## 1부터 10까지의 숫자를 저장하고 접근하는 경우의 차이

### 배열
- 배열에 1부터 10까지 저장되어 있다면, 예를 들어 숫자 '10'의 위치를 찾기 위해서는 인덱스 접근을 사용하여 바로 해당 위치를 알 수 있습니다. 예: let numbers = [1, 2, 3, ... 10]; print(numbers[9]) // 출력: 10
- 배열 같은경우에는 10이 어디있는지 찾아내서 인덱스 위치값을 반환하면 나타난다

### 링크드 리스트
- 링크드 리스트에서는 첫 번째 노드부터 시작하여 각 노드를 순회하면서 숫자 '10'을 찾아야 합니다. 각 노드를 방문하며 값을 확인해야 하므로 더 많은 시간이 걸립니다. 예: let firstNode = Node(value: 1, next: Node(value: 2, ... )); // 10번 노드까지 순회해야 함
- 하지만 링크드은 10이 어디있는지 알수없다 현재값이 10인지 다음값이전값이 10인지 만 알수있기에 10을 찾아 다음 다음 이렇게 넘어가서 찾아야 한다.

### 배열에서의 삽입 및 삭제
- 배열에서 특정 위치에 데이터를 삽입하거나 삭제할 때, 그 위치 뒤에 있는 모든 요소들을 이동시켜야 합니다. 이는 다음과 같은 특징을 가집니다:

- 삽입: 삽입할 위치를 결정한 후, 그 위치부터 배열 끝까지 모든 요소를 한 칸씩 뒤로 이동시켜야 합니다. 이 과정은 O(n) 시간 복잡도를 가지며, 이는 배열의 크기가 커질수록 성능에 더 큰 영향을 미칩니다.
- 삭제: 삭제할 요소를 제거한 후, 그 위치 뒤에 있는 모든 요소를 한 칸씩 앞으로 이동시켜야 합니다. 이 역시 O(n) 시간 복잡도를 가지며, 배열 크기에 따라 비용이 증가합니다.

### 링크드 리스트에서의 삽입 및 삭제
- 링크드 리스트에서는 노드 사이의 연결만 조정하면 됩니다. 특정 위치에서 삽입 또는 삭제를 하기 위한 절차는 다음과 같습니다:

- 삽입: 삽입할 위치의 바로 앞 노드를 찾은 다음, 새 노드의 포인터를 조정하여 연결합니다. 이전 노드를 알고 있다면, 이 작업은 O(1)의 시간 복잡도를 가집니다. 위치를 찾기 위해서는 최악의 경우 O(n) 시간이 걸릴 수 있습니다.
- 삭제: 삭제할 노드의 이전 노드를 찾은 후, 삭제할 노드를 건너뛰어 다음 노드에 연결합니다. 이 작업도 노드의 위치를 알고 있으면 O(1)의 시간 복잡도를 가집니다.

## 그래서 언제 선택하는것이 좋은가?

### 링크드 리스트를 선택해야 할 때:
- 동적 크기 조절이 필요할 때: 링크드 리스트는 노드의 추가와 제거가 자유로우며, 실시간으로 크기가 조절될 필요가 있을 때 유리합니다. 크기를 미리 정하지 않아도 되므로, 데이터의 양이 불확실할 때 적합합니다.
- 빈번한 삽입과 삭제가 필요한 위치: 중간에 요소를 자주 삽입하거나 삭제해야 하는 경우, 링크드 리스트는 포인터만 수정하면 되므로 배열에 비해 효율적입니다. 특히 링크드 리스트의 시작 부분이나 알려진 위치에서의 삽입 및 삭제는 매우 빠릅니다.
- 메모리 사용 최적화: 링크드 리스트는 필요할 때마다 메모리를 할당하므로 큰 블록의 메모리를 한 번에 할당할 필요가 없어 메모리 효율성이 높습니다.

### 배열을 선택해야 할 때:
- 인덱스를 통한 빠른 접근이 필요할 때: 배열은 인덱스를 통해 O(1)의 시간 복잡도로 요소에 접근할 수 있습니다. 데이터에 빈번하고 무작위로 접근해야 하는 경우 배열이 효율적입니다.
- 메모리 상의 연속성: 배열은 메모리 상에서 연속적인 공간에 데이터를 저장하기 때문에 CPU 캐시 활용이 더 효율적이며, 이는 성능을 크게 향상시킬 수 있습니다.
- 공간 효율성: 링크드 리스트에 비해 배열은 각 요소의 메모리 오버헤드가 적습니다. 링크드 리스트는 각 노드의 포인터를 위한 추가 메모리가 필요하지만 배열은 데이터만 저장합니다.

결론적으로, 데이터의 크기가 변하지 않고, 빠른 접근이 주로 필요하다면 배열을, 데이터가 동적으로 변하고 중간에 자주 삽입 또는 삭제가 이루어진다면 링크드 리스트를 선택하는 것이 일반적으로 좋은 방법입니다.