배열(Array), 연결 리스트(Linked List)
어떤 자료구조를 사용하냐에 따라 프로그램의 성능과 메모리 관리의 효율성이 달라지기도 한다.
👉🏻 상황에 적절한 자료구조 선택이 중요!
배열과 연결 리스트는 모두 데이터를 저장하고 관리하기 위한 자료구조!
배열
배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
A B C D E
1 2 3 4 5
👉🏻 인덱스와 번호에 대응하는 데이터들로 이루어져 있음
인덱스?
배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치들을 가리킴
배열은 같은 종류의 데이터들이 순차적으로 저장되어 있어 인덱스(index)를 통한 접근이 용이
연결 리스트
(연결 리스트 종류에 따라 포인터들이 가리키는 노드는 달라질 수 있음)
연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다. 일반적인 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.
노드?
데이터와 다음 노드를 가리키는 포인터로 이루어져 있는 것
첫 번째 노드를 'head'라 하며 마지막 노드를 'tail'이라고 한다.
여기에서 데이터는 노드가 저장하는 실제 값, 포인터를 통해 다음 노드를 찾아갈 수 있다.
데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 되는 것
연결 리스트는 배열과 다르게 메모리를 연속적으로 사용하지 않는다.
또한, 데이터가 삭제되거나 추가되면 해당 노드를 가리키는 포인터만 변경해 주면 되기 때문에 배열보다 삭제나 추가가 용이하다!
배열 vs 연결 리스트
| 배열 | 연결리스트 | |
|---|---|---|
| 장점 | 인덱스를 통한 빠른 접근 가능 | 삽입과 삭제가 용이 |
| 단점 | - 삽입과 삭제가 오래 걸림 - 배열 중간에 있는 데이터가 삭제되면, 공간 낭비 발생 | - 임의 접근 불가 - 처음부터 탐색을 진행해야 함 |
| 용도 | 빠른 접근 요구되고, 데이터의 삽입과 삭제가 적을 때 | 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 |
참고자료
hello, world!