Array와 Linked List의 차이점을 설명해보세요
Keyword
index, node, 탐색, 삽입, 삭제
Script
먼저, Array는 연속된 메모리 공간을 사용하고, Linked List는 연속되지 않은 메모리 공간을 사용합니다.
그래서 Array의 경우, index를 통해 각 요소에 접근할 수 있고, 탐색에 필요한 시간복잡도는 O(1)입니다.
하지만 삽입이나 삭제의 경우에는 shift에 필요한 연산이 발생하여 O(n)의 시간복잡도를 가집니다.
반면 Linked List의 경우, shift가 필요없고, 노드 간의 연결을 이어주고 끊어주는 과정을 통해 삽입과 삭제를 O(1) 시간복잡도로 수행합니다. 탐색은 O(n) 시간복잡도로 수행합니다.
정리하면, Array는 추가나 삭제보다 빠른 접근의 이점을 필요로 할때 사용하고, Linked List는 탐색보다는 추가나 삭제에서의 이점을 필요로 할 때 사용한다.
Additional
논리적 저장 순서와 물리적 저장 순서
Array의 경우 논리적 저장 순서와 물리적 저장 순서가 일치한다. 이 덕분에 index를 통해 해당 원소로 접근할 수 있다.
반면, Linked List는 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다. 이 때문에, 탐색을 위해서는 첫번째 원소부터 일일이 전부 노드를 타며 확인을 해야하는 것이다.
Linked List에서 tail을 가르키는 포인터를 별도로 갖고있는 이유
Linked List는 기본적으로 삽입과 삭제에 있어 O(1)의 시간복잡도를 가진다. 하지만 Array와 달리 탐색을 위해서는, 노드의 연결을 타고 원하는 위치를 찾아야하기 때문에, 탐색에 있어서 O(n)의 시간복잡도가 발생합니다. 이 때문에, 결국 원하는 위치에 삽입과 삭제를 하려면 O(n)의 시간복잡도가 소요됩니다.
Linked List는 양 끝에서 발생하는 삽입과 삭제나 특정 주소를 포인팅하고 있는 곳에 삽입과 삭제를 할때에 유리하다.
하지만 만약 tail을 가르키는 별도의 포인터가 존재하지 않는 경우, tail을 찾기 위해 O(n)의 시간복잡도를 가지는 연산이 필요해진다.
Array는 Random Access가 가능하다.
Linked List 같은 경우는 Random Access가 불가하다. 원하는 곳에 접근하기 위해서는 처음부터 탐색이 필요하기 때문이다.
반면 Array의 경우는 index를 통한 Random Access가 가능하다. 그래서 Random Access와 빠른 접근이 요구되는 경우는 배열을 사용하는 것이 유리하다.
Array와 Linked List를 사용하면 좋을 데이터 예시는 각각 무엇인가?
Array과 같은 경우는 일반적으로 불규칙적인 정보를 저장하거나, 이후에 자주 접근할 정보를 저장할 때 사용할 수 있다. 예를 들어 메뉴판 데이터를 저장한다고하면, Linked List보다 Array가 더 효율적일 것이다. 랜덤으로 메뉴를 뽑을 수도 있고, 각 메뉴가 추가나 삭제되는 경우보다 접근되는 경우가 훨씬 많이 발생할테니, 추가나 삭제 연산보다 탐색이 효과적인 Array를 쓰는 것이 좋다.
Linked List와 같은 경우는 history 데이터를 저장할 때 유용하게 사용할 수 있다. 문서 편집기를 사용할 때, 사용자 기록을 doubly linked list를 활용하여 저장하면, 사용자가 이전 기록으로 돌아가거나 다시 이후 기록으로 이동할 때 유리하게 사용할 수 있을 것이다. 이 경우는 history 데이터 중간에 추가나 삭제 연산이 발생하더라도, Array보다 빠른 시간복잡도로 연산을 수행할 수 있다.
Array와 ArrayList의 차이점
Array는 고정 길이 자료 구조인 반면 ArrayList는 가변 길이 자료 구조이다.
Array는 정해진 길이의 배열이 모두 사용되면, 새로운 데이터를 추가하고 싶을 때는 새로운 배열을 만들어주어야 한다. 반면, ArrayList는 내부적으로는 배열로 구성되어있으나, capacity를 넘어가면 일반적으로 배열의 크기를 1.5배 증가시키면서 배열의 크기를 늘린다.
동적 할당, 정적 할당
정적 할당은 컴파일 단계에서 필요한 메모리 공간을 할당하고, 동적 할당은 실행 단계에서 메모리 공간을 할당해주는 것이다.
Array가 선언되면, 컴파일 과정에서 메모리가 Stack 영역에 할당된다 (정적 메모리 할당).
반면, Linked List가 선언되면, 런타임 환경에서 메모리가 Heap 영역에 할당된다(동적 메모리 할당).
