Array vs Linked List
먼저 Array에 대해 알아보자. Array는 미리 크리를 정해 사용하는 static 자료구조이다. 처음 정해 놓은 크기 만큼 연속된 메모리 주소를 할당 받는다. 따라서 크기 수정이 불가하고, 배열 크기 이상의 데이터를 저장할 수 없다.
하지만 연속된 메모리 구조 덕분에 인덱스를 가지고 데이터 접근이 가능하다.
Linked List는 노드가 존재한다. 노드에는 저장된 데이터와 다음 데이터가 있는 메모리 주소를 가지고 있다. 따라서 Array처럼 연속된 메모리가 아니라 임의의 메모리 주소를 가진다. 이 말은 즉, 크기에 제한이 없고, 크기의 제한이 없기에 데이터 추가, 삭제가 자유롭다.
하지만 Array처럼 연속된 메모리 주소가 아니기 때문에 탐색하는 방식은 순차 접근 방식을 이용한다.
-
데이터 탐색
Array: 인덱스 접근 통한 탐색으로 O(1)의 시간복잡도를 가진다.
Linked List: 처음부터 순차적으로 탐색해 O(n)의 시간복잡도를 가진다. -
데이터 추가
Array: 추가 데이터가 맨 뒤라면 O(1), 나머지는 O(n)의 시간복잡도를 가진다. 그리고 Array의 크기를 고려해야 한다.
Linked List: 추가 데이터가 맨 앞이라면 O(1), 나머지는 O(n)의 시간복잡도를 가진다. -
데이터 삭제
Array: 추가 데이터가 맨 뒤라면 O(1), 나머지는 삭제 후 shift 해야하기 때문에 O(n)의 시간복잡도를 가진다.
Linked List: 추가 데이터가 맨 앞이라면 O(1), 나머지는 O(n)의 시간복잡도를 가진다. -
결론
데이터의 접근, 탐색이 중요하면 Array, 데이터 추가, 삭제가 중요하면 Linked List를 사용하지만 상황에 따라 선택하면 된다.
그리고 Linked List는 Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용하면 유용하다.
