배열 리스트와 연결 리스트 비교

• 배열 리스트와 연결 리스트는 서로 다른 특징을 갖고 있습니다.
• 상황에 따라 배열 리스트가 장점이 되는 경우가 있고, 연결 리스트가 장점이 되는 경우가 있습니다. 배열 리스트와 연결 리스트의 장단점을 비교해볼까요?

배열 리스트

• 배열 리스트는 배열을 사용한 리스트입니다.

장점

• 배열 리스트는 데이터의 위치를 인덱싱(Indexing)할 수 있습니다.
• 따라서 데이터의 조회(참조) 및 출력에 대해 매우 빠른 접근(O(1))이 가능합니다.

단점

• 배열 리스트는 크기가 고정되어 있습니다. 따라서 메모리가 효율적이지 못합니다. 위 그림에서 3번과 4번 인덱스가 사용하지 않는 데이터임에도 메모리 공간을 차지하고 있습니다.
• 또한 중간에 존재하는 데이터를 삭제하는 경우 뒤에 존재하는 모든 데이터를 한 칸씩 앞으로 이동해야 합니다.

연결 리스트

• 연결 리스트는 포인터를 사용하여 다음 노드를 가리키고 있습니다. 노드란 자료구조에서 데이터의 한 단위입니다. 앞서 연결 리스트에서 다음과 같이 노드를 정의하였습니다.

1
2
3
4
5

typedef struct _Node
{
    ListData data;
    struct _Node* next;
} Node;

• 연결 리스트는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있습니다.

장점

• 연결 리스트는 크기에 제한을 갖지 않습니다. 엄밀히 말하면 힙 영역에 노드를 생성할 여유 메모리가 존재하지 않을 때까지 리스트를 확장할 수 있습니다.
• 또한 데이터를 삭제하는 과정에서 배열 리스트와는 다르게 많은 데이터를 이동할 필요가 없습니다. 이전 노드의 연결만 수정하면 되기 때문입니다.

단점

• 찾고자 하는 노드의 인덱스 정보가 없어 데이터를 조회하는 경우 상대적으로 많은 연산이 필요합니다. 현재 노드가 몇 번째 노드인지 파악하기 힘들기 때문입니다.
• 배열 리스트에 비해 상대적으로 구현이 어렵습니다. 배열 리스트는 별도의 노드를 만들 필요 없이 데이터의 배열을 이용하여 쉽게 구현하였습니다. 반면 연결 리스트는 노드의 생성을 위해 동적 할당을 수행하고, 노드를 연결하는 포인터를 활용하기 때문에 비교적 구현 난이도가 높습니다.

정리

• 실무에서는 상대적으로 배열 리스트는 잘 사용하지 않습니다. 그렇다고 하여 배열 리스트의 존재나 방법, 원리 같은 개념을 공부하지 않을 수는 없습니다.
• 배열 리스트가 필요한 경우가 있을 수 있고, 배열 리스트를 앎에 있어서 요구하는 난이도가 매우 낮기 때문에 잘 알아두면 좋습니다.