[면접 꿀팁] 배열(Array)과 링크드 리스트(Linked list)의 특징

안녕하세요? 오늘은 신입 개발자 면접에서 빈번하게 등장하는 배열과 링크드 리스트의 특징을 파악하고 비교해보겠습니다.

일단, 배열과 링크드 리스트는 데이터를 저장하고 관리하는 데 사용되는 두 가지 기본적인 자료 구조입니다.

배열과 링크드 리스트 그림. 출처: C언어로 쉽게 풀어쓴 자료구조

배열(Array)

• 연속된 메모리 공간에 데이터를 저장합니다.
• 인덱스를 사용하여 원소에 빠르게 접근할 수 있습니다. O(1)의 시간 복잡도를 가집니다.
• 고정된 크기를 가지며, 크기 변경이 어렵습니다. 미리 할당된 메모리 크기를 초과하면 새로운 메모리 공간을 할당하고 데이터를 복사해야 합니다.
• 원소를 삽입하거나 삭제할 때, 원소들을 이동시켜야 하므로 시간이 오래 걸릴 수 있습니다. 일반적으로 O(n)의 시간 복잡도를 가집니다.
• 메모리 사용이 효율적입니다. 각 원소는 인덱스로 접근되며, 추가적인 메모리를 사용하지 않습니다.

링크드 리스트(Linked List)

• 각 노드가 데이터와 다음 노드에 대한 참조(포인터)를 포함하며, 노드들이 연속되지 않은 메모리 공간에 저장됩니다.
• 원소에 접근하기 위해서는 리스트를 순차적으로 탐색해야 하며, O(n)의 시간 복잡도를 가집니다.
• 크기 변경이 쉽습니다. 새 노드를 동적으로 할당하거나 제거함으로써 리스트의 크기를 변경할 수 있습니다.
• 원소를 삽입하거나 삭제할 때, 포인터를 업데이트만 하면 되므로 상대적으로 빠른 시간에 처리할 수 있습니다. 일반적으로 O(1)의 시간 복잡도를 가집니다(단, 삽입이나 삭제할 위치를 찾는 과정은 O(n)의 시간 복잡도를 가집니다).
• 메모리 사용이 비효율적일 수 있습니다. 각 노드는 데이터와 포인터를 저장해야 하므로, 추가적인 메모리를 사용합니다.

어떻게 사용해야 하는가?

두 자료 구조는 각각의 특성에 따라 사용 목적과 상황이 다릅니다. 배열은 인덱스를 사용한 빠른 접근이 필요하거나 크기가 고정된 경우에 적합하며, 링크드 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하거나 크기가 가변적인 경우에 적합합니다.