예약번호가 1001, 1002, 1003처럼 차례로 있다면 줄을 세워 놓는 것이 자연스럽다.
하지만 예약 취소가 자주 일어나고 중간에 새로운 데이터가 계속 들어온다면 다른 방법이 더 편할 수도 있다.
데이터의 ‘모양’을 정하는 일
컵에는 물을 담기 좋고, 서랍에는 물건을 나누어 넣기 좋다.
데이터도 마찬가지다. 순서대로 처리할지, 중간 삽입이 잦은지, 가장 마지막에 들어온 것을 먼저 꺼낼지에 따라 적합한 구조가 달라진다.
자료구조를 고를 때는 저장 방식보다 ‘어떤 작업이 자주 일어나는가’를 먼저 본다. 순서대로 읽는 일이 많은지, 중간 삽입·삭제가 잦은지, 가장 최근 값부터 꺼내야 하는지에 따라 유리한 구조가 달라진다.
배열은 빠르게 찾기 쉽다
좌석 번호처럼 순서가 분명한 데이터를 떠올려 보자.
배열은 데이터가 연속된 구조에 놓이므로 몇 번째 데이터인지 알고 있다면 원하는 위치에 바로 접근하기 쉽다.
반면 중간에 데이터를 끼워 넣거나 빼려면 뒤쪽 데이터를 이동해야 할 수 있다.
연결된 데이터는 움직이기 쉽다
이번에는 각 데이터가 다음 데이터의 위치를 알려 주는 모습을 떠올려 보자.
ILLUST B | ILL-02 | 배열과 연결 리스트 비교 | 자료구조 비교 세트로 제작데이터가 메모리에서 꼭 붙어 있을 필요가 없고, 중간에 값을 추가할 때도 연결 정보만 바꾸면 되는 경우가 많다.
대신 특정 번째 데이터를 찾으려면 앞에서부터 연결을 따라가야 하는 경우가 많다.
연결 리스트의 장점은 원소 사이의 연결만 바꾸어 구조를 수정할 수 있다는 데 있다. 반대로 특정 위치의 값을 바로 찾기 어렵기 때문에 탐색이 자주 필요한 문제라면 배열이 더 단순하고 빠를 수 있다. 자료구조는 항상 사용 목적과 함께 선택한다.