[알고리즘 자료구조] 배열(Array)과 연결 리스트(Linked List)를 비교해 보자!
- 2023-06-15 10:33
- SW마에스트로
코딩 테스트의 중요성이 강조됨과 더불어
어떤 자료구조를 사용하냐에 따라 프로그램의
성능과 메모리 관리의 효율성이 달라지기도 하는데요!
그렇기에 상황에 적절한 자료구조
선택이 더욱더 중요해지고 있습니다!
그래서 오늘은 자료구조에서 자주 비교하는 주제인!
배열과 연결 리스트를 비교해 보는 시간을
가져보도록 하겠습니다!
배열과 연결 리스트는 모두 데이터를 저장하고
관리하기 위한 자료구조입니다.
하지만 배열과 연결 리스트는 데이터를 저장하고 접근하는
방식이 다르기 때문에 각각의 장단점을
이해하는 것이 중요합니다!
그럼 먼저 배열에 대해 알아볼까요~?
배열이란?
배열은 입력된 데이터들이
메모리 공간에서 연속적으로 저장되어 있는 자료구조입니다.
위의 사진과 같이 번호(인덱스)와 번호에 대응하는
데이터들로 이루어져 있죠!
인덱스란?
여기서 인덱스란?
배열의 시작점으로부터 값이 저장되어 있는
상대적인 위치들을 가리킵니다.
따라서 배열은 같은 종류의 데이터들이 순차적으로 저장되어 있어 인덱스(index)를 통한 접근이 용이합니다.
다음으로 연결 리스트에 대해 알아보겠습니다.
연결 리스트란?
연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조입니다. 일반적인 종류로는 단일 연결 리스트,
이중 연결 리스트, 원형 연결 리스트가 있습니다.
노드란?
여기서 노드란? 데이터와 다음 노드를 가리키는 포인터로
이루어져 있는 것입니다. 첫 번째 노드를 ‘head’라 하며 마지막 노드를 ‘tail’이라고 합니다.
여기서 데이터는 노드가 저장하는 실제 값이고, 포인터를
통해 다음 노드를 찾아갈 수 있습니다.
위의 사진처럼 데이터를 담고 있는 노드들이 연결되어
있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을
담당하게 되는 것입니다.
연결 리스트는 배열과 다르게 메모리를 연속적으로 사용하지 않습니다.
또한, 데이터가 삭제되거나 추가되면 해당 노드를 가리키는
포인터만 변경해 주면 되기 때문에
배열보다 삭제나 추가에 용이합니다!
마지막으로 배열과 연결 리스트에 장단점에 대해
비교해 보겠습니다!
배열 vs 연결 리스트
배열은 빠른 접근과 메모리 공간 효율성을 가지고 있으며,
배열 기반의 자료구조와 알고리즘에 유용합니다.
그러나 크기 제한과 삽입/삭제의 어려움이 있습니다.
반면에 연결 리스트는 중간 삽입/삭제가 용이합니다.
그러나 접근이 느리고 추가적인 메모리 사용과
연결 관리의 부담이 있습니다.
따라서 배열은 데이터 크기가 고정되어 있고 빠른 접근이
필요한 경우 유리하며, 연결 리스트는 동적 크기 조정과
유연한 삽입/삭제가 필요한 경우 유리합니다!
즉 상황에 맞는 자료구조를 적절히 선택하여
사용해야겠죠?
오늘은 배열과 연결 리스트의 간단한 개념과
각각의 장단점을 비교해 봤는데요!
각각의 자료구조 개념을 아는 거뿐만 아니라
상황에 맞는 자료구조를 선택하여
사용하는 능력도 중요한 거 같습니다!
그럼 다음에는 더욱 유익한
알.자.구로 돌아오겠습니다!
감사합니다!
