array vs linked list

1 minute read

Array vs Linked List

우선 배열 자료구조 부터 알아보겠습니다.

프로그래밍언어에서, 컴퓨터 과학에서 사용하는 자료구조중 하나입니다.

Array 자료구조가 가지고있는 특징으로는 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조를 뜻합니다.

각 원소들에 붙은 번호를 Index 라고 합니다.

Array 자료구조는 논리적 저장순서와 물리적 저장순서가 일치합니다. 따라서 Index 곧바로 해당 원소에 접근할수있습니다.

그렇기때문에 해당 원소에 접근하는 시간 복잡도는 O(1) 에 해당합니다. 즉, Random Access가 가능합니다.

메모리 주소가 연속될것을 요구하기때문에 배열의 크기를 늘리는것은 불가능합니다.

그렇기때문에 배열의 크기를 늘리고싶을때에는 크기가 큰 다른 새 배열을 만든후에 기존내용을 복사하거나,

배열의 일부를Linked List 등으로 다른곳과 연결하는등의 방법이있습니다.

하지만 삭제와 삽입 등의 과정에서는 해당 원소에 접근 한후 또 다른 작업을 추가로 해줘야 하기때문에 시간이 더 걸리게됩니다.

또한 배열의 원소중 특정 원소를 삭제할경우에 연속적인 형태의 구조성이 깨지게 됩니다.

빈 공간이 생기게 되며 그 원소보다 큰 인덱스의 원소들을 당겨줘야 (Shift) 하므로 더 많은 비용이 발생하게됩니다.

그렇기 때문에 시간복잡도는 O(n) 이 됩니다.

이 역시 컴퓨터 자료구조의 일종으로 어떤 데이터 묶음(노드)을 저장할때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 저장됩니다.

마치 서로 연결된 기차와 같은 모습이 됩니다.

배열에서는 자료마다 Index가 존재해 특정 자료를 찾는데에 비용이 적게드는 반면 Linked List는 좀 더 어려운 단점이존재합니다.

배열과 달리 추가/삭제에 대해 최적화 되어있으나 탐색에는 좀더 불리합니다.

Linked List는 삭제에도 O(n), 탐색에도 O(n)의 시간복잡도가 소요됩니다.

보통 Linked List 는 Tree 구조의 뼈대가 되는 자료구조입니다.

사실 반드시 어느것이 훌륭하다 라고 정의하기는 어렵습니다.

탐색속도는 Array가 더 빠르며, 삭제/삽입 은 Linked List 가 좀 더 우월합니다.

만약 프로그램을 만들때 삽입과 삭제가 빈번할것으로 예상된다면 Linked List

데이터의 탐색이 좀 더 빈번할것으로 예상이 된다면 Array 를 사용하는것이 좋습니다.

또한 Array 자료구조는 Array 를 선언 하자마자 Stack 영역에 정적 메모리 할당이 이루어지며,

Linked List 자료구조는 새로운 Node 가 추가될때마다 Heap 영역에 동적 메모리 할당이 이루어집니다.

만일 데이터의 최대 크기가 미리 예상되는 경우 Linked List 가 좀 더 편리하고 성능이 우월합니다.