배열의 장점
- 읽기, 쓰기와 같은 참조에는 O(1)의 성능
- 배열의 해당 인덱스로 바로 접근이 가능
배열의 단점
- 배열 생성 시, 연속된 메모리 공간이 필요
- 배열의 초기 크기를 모르면 메모리가 낭비될 수 있음
배열의 보완
- 저장하려는 데이터를 메모리에 분산하고,
노드로 연결
노드
데이터를 담는 변수와다음 노드의 위치를 가리키는 변수로 이루어져 있습니다.
데이터가 필요한 만큼 노드를 생성하여 데이터를 저장하고 연결할 다음 노드를 연결
✅ 노드의 주소만 알고 있으면 해당 노드에 연결된 모든 노드에 접근할 수 있습니다.
연결리스트 장점
배열과의 비교
- 배열에서는 초기 크기를 알 수 없는 경우, 예상보다 넉넉하게 메모리 공간을 확보하게 되고 그로 인해 낭비되는 메모리가 있을 가능성이 큰 반면, 연결리스트는 비어있는 메모리 공간 아무 곳에 데이터를 추가하고 연결만 해주면 되기 때문에
배열에서 발생할 수 있는 메모리 낭비가 없습니다.
- 배열에서는 데이터를 추가할 경우, 추가된 데이터 뒤에 있는 데이터들은 추가 된 만큼 뒤로 밀려나기 때문에 오버헤드가 많이 발생합니다.
*오버헤드 : 추가적인 작업과 시간 소모
(`연결리스트`에서 `1`과 `3`사이에 `2`를 추가하는 그림 예시)
- 연결리스트에서는 데이터 추가 시, 빈 메모리 아무 곳에나 데이터를 생성하고 연결만 해주면 됩니다.
연결리스트 단점
배열과의 비교
- 배열은 메모리의 연속된 공간에 할당되기 때문에 시작 주소만 알면, 찾고자 하는 데이터에를 쉽게 찾을 수 있습니다.
- 배열의 시작주소에서 n만큼 더한 주소에 접근하면 됩니다. (`배열`에서 n번째 index의 값을 찾는 그림 예시)
이렇게 배열에서 n번째 index의 바로 접근하기 때문에, O(1)의 성능을 가집니다.
반면,
연결리스트는 각 데이터가 저장되어 있는 위치가 전부 떨어져 있기 때문에,
n번째 값에 도달하기 위해서는 첫 번째 노드에서 부터 다음 노드를 찾고
또 다음 노드를 찾는 순으로 찾을 때 까지 이동을 해야 합니다.
(`연결리스트`에서 n번째 index의 값을 찾는 그림 예시)연결 리스트에서 데이터 참조는 O(n)의 성능을 가집니다.
비교표
| 배열 | 연결리스트 | |
|---|---|---|
| 크기 | 고정 | 동적 |
| 주소 | 연속 | 불연속 |
| 데이터 참조 | O(1) | O(n) |
| 삽입과 삭제 | O(n) | O(n) |
- 데이터의 개수가 자주 변경되지 않고, 참조가 많이 일어난다면
O(1)의 성능을 가지는 배열이 훨씬 좋은 선택일 것 입니다.
- 데이터의 삽입과 삭제가 자주일어난다면
배열은 초기에 크기가 결정되기 때문에 연결리스트가 더 좋은 선택일 것 입니다.
