배열과 연결 리스트는 아주 기초적인 선형 자료구조입니다. 보통 다른 자료구조를 구현하기 위한 수단으로 이용됩니다.
배열
배열은 가장 기초적이면서 다루기 쉬운 자료구조입니다. 적절하게 인덱스를 핸들링할 수 있다면 다루기 쉬운 자료구조입니다.
하지만, 처음에 배열을 선언할 때, 크기를 지정해줘야 한다는 문제점이 있죠. 문제상황을 해결할 때, 필요한 배열의 크기를 가늠할 수 없다면 활용하기 쉽지 않습니다.
이런 문제는 크게 두 가지 방법으로 해결이 가능한데, 하나는 동적인 방법으로 배열의 크기를 재설정하는 것이고 다른 하나는 연결 리스트를 활용하는 것 입니다.
동적 배열은 지정된 배열의 크기가 부족할 때, 사이즈가 더 큰 새로운 배열을 할당해 기존 배열의 자료를 복사한 다음, 포인터를 옮기는 방식으로 구현이 가능합니다.
if(용량 == size){
int new_size = size * 2;
int *new_array = new int[new_size];
for(int i = 0; i < size; i++){
new_array[i] = old_array[i];
}
delete[] old;
size = new_size;
old_array = new_array;
연결 리스트
연결 리스트를 이용해 배열의 용량 문제 뿐 아니라 삭제, 삽입 등과 같은 연산을 행할 때의 번거로움 또한 해결할 수 있습니다.
연결 리스트는 자료와 포인터로 이루어진 노드라는 구조체를 활용합니다.
struct node{
dataType *next;
dataType element;
}
head라고 불리는 더미노드를 시작점으로 두고 새로운 자료를 저장할 때마다, 노드를 생성해 이전 노드와 연결만 해주면 됩니다.
그리고 추가 또는 마지막 노드 삭제를 편하게 하기 위해 마지막 노드를 포인터로 지정하는 것이 좋습니다. 마지막 노드의 next는 null로 설정해주면 되겠습니다.
배열에서 삭제와 삽입이 번거로운 반면에 연결 리스트에서는 간편합니다.
삭제는 원하는 자료를 가진 노드를 탐색후 이전 노드의 포인터를 다다음 노드로 이어주기만 하면 됩니다.
삽입은 새로운 노드를 생성한 후 원하는 위치 이전의 노드가 새로운 노드와 이어주고 새로운 노드와 그 다음 노드를 이어주기만 하면 됩니다.
배열과 연결 리스트 비교
가장 큰 차이점은 한번에 접근이 가능하냐 아니냐 인것 같습니다.
배열의 경우, 원하는 위치의 자료에 접근하기 위해서는 인덱스를 이용해 직접적으로 접근이 가능하지만 연결 리스트의 경우, 탐색을 기반으로 원하는 위치의 자료에 접근해야하기 때문에 그만큼 수행시간이 늘어나게 되죠.
삽입, 삭제 할 때, 배열과 연결 리스트 모두 탐색이 필요합니다.
하지만, 배열 같은 경우 삽입, 삭제한 위치 이후의 자료들을 따로 처리해줘야 한다는 점에서 연결 리스트의 강점을 확인할 수 있습니다.
따라서, 만약 1. 필요한 배열의 크기를 알고 2. 삽입, 삭제와 같은 연산이 필요 없을 경우에는 배열을 이용하는 것이 편하고 이외의 경우에는 연결리스트가 더 좋은 선택이 될 수 있겠네요.
앞서 말한 것과 같이, 배열과 연결 리스트 모두 다른 자료구조를 구현하기 위한 수단적인 자료구조입니다.
이제부터 그 자료구조들에 대해서 다뤄보면서 배열, 연결 리스트 두 가지 방법으로 구현하는 방법에 대해서도 다룰 것이기 때문에 각각의 특징을 잘 알아 두는 것이 좋겠습니다.
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!