개념
배열 (Array)
연속된 메모리 블록에 요소를 저장하는 자료구조입니다.
각 요소는 인덱스를 통해 직접 접근할 수 있어, 고정된 크기의 데이터를 다룰 때 효율적입니다.
링크드 리스트 (Linked List)
요소(노드)가 포인터로 연결된 자료구조입니다.
각 노드는 데이터를 저장하는 공간과 다음 노드를 가리키는 포인터로 구성됩니다.
노드가 동적으로 메모리에 할당되므로, 배열과 달리 크기가 가변적입니다.
시간 복잡도
배열 (Array)
접근: O(1) – 인덱스를 통해 즉시 접근할 수 있습니다.
삽입/삭제: O(n) – 요소를 삽입하거나 삭제할 때, 다른 요소를 이동해야 하므로 시간이 걸립니다.
링크드 리스트 (Linked List)
접근: O(n) – 인덱스를 통한 직접 접근이 불가능하고, 첫 노드부터 순차적으로 탐색해야 합니다.
삽입/삭제: O(1) (앞이나 뒤에서 삽입/삭제 시) – 포인터를 변경하는 것만으로 가능하므로 빠릅니다. 그러나 중간에 삽입이나 삭제는 탐색이 필요해 O(n)이 될 수 있습니다.
가비지 컬렉션(GC)
배열 (Array)
배열은 연속된 메모리 블록을 할당받기 때문에, 요소가 할당된 상태에서 연속된 블록으로 유지됩니다.
단일 메모리 할당/해제가 이뤄지므로, GC 부담이 적고 메모리 단편화가 줄어듭니다.
메모리에 오래 남아 있는 요소는 적으므로 GC의 빈도와 부담이 낮습니다.
링크드 리스트 (Linked List)
노드마다 개별적으로 동적 메모리를 할당받으므로, 사용이 끝난 노드가 많아지면 GC가 빈번하게 작동하게 됩니다.
각 노드의 포인터로 연결되어 있어, 참조가 복잡하게 얽히면 사용되지 않는 노드도 메모리에서 해제되지 않는 경우가 발생할 수 있습니다.
메모리 단편화가 발생할 수 있으며, 이는 GC 성능에 악영향을 미칩니다.
