배열과 링크드 리스트의 차이점은 무엇인가요? (자바 기준)

답변

배열(Array)과 링크드 리스트(Linked List)는 모두 데이터를 저장하는 자료구조이지만, 그 구조와 동작 방식에서 몇 가지 중요한 차이점이 있습니다.

 

배열은 고정된 크기의 데이터를 저장할 때 유리합니다. 예를 들어, 주식 시장에서 특정 날의 주가 변동을 저장하는 경우를 생각할 수 있습니다. 이 경우, 하루 동안 24시간 동안 주가를 매시간 기록한다고 가정할 때, 하루의 주가 데이터를 배열에 저장하는 것이 적합합니다. 배열을 사용하면 특정 시간의 주가를 O(1) 시간 복잡도로 빠르게 조회할 수 있습니다.

 

링크드 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하는 경우에 유리합니다. 예를 들어, 음악 재생 목록(playlist)을 관리할 때 링크드 리스트를 사용하는 것이 적합합니다. 사용자가 언제든지 재생 목록에 노래를 추가하거나 삭제할 수 있기 때문입니다. 링크드 리스트를 사용하면 재생 목록의 시작이나 중간에 노래를 추가하거나 삭제할 때 효율적입니다.

 

구체적으로는 다음과 같은 차이점이 있습니다. 

 

1. 메모리 할당 방식:
   • 배열: 배열은 고정 크기의 연속된 메모리 블록을 사용하여 데이터를 저장합니다. 배열을 선언할 때 크기를 미리 지정해야 하며, 이 크기는 변경할 수 없습니다. 예를 들어, int[] arr = new int[10];과 같이 선언합니다.
   • 링크드 리스트: 링크드 리스트는 동적으로 메모리를 할당하며, 각 요소(Node)는 데이터와 다음 요소에 대한 참조(포인터)를 포함합니다. 메모리 상에서 연속되지 않은 위치에 요소들이 저장될 수 있습니다. 예를 들어, Node 클래스를 사용하여 링크드 리스트를 구현할 수 있습니다.
2. 데이터 접근 속도:
   • 배열: 배열은 인덱스를 사용하여 O(1) 시간 복잡도로 임의의 위치에 있는 요소에 접근할 수 있습니다. 예를 들어, arr[3]은 즉시 네 번째 요소에 접근합니다.
   • 링크드 리스트: 링크드 리스트는 첫 번째 노드부터 순차적으로 탐색해야 하므로, 임의의 위치에 접근하는 데 O(n) 시간이 소요됩니다. 예를 들어, 네 번째 요소에 접근하려면 첫 번째 노드부터 네 번째 노드까지 순차적으로 접근해야 합니다.
3. 삽입 및 삭제:
   • 배열: 배열의 중간에 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동시켜야 하므로 O(n) 시간이 소요됩니다.
   • 링크드 리스트: 링크드 리스트는 특정 위치에 요소를 삽입하거나 삭제할 때, 해당 위치의 이전 노드만 수정하면 되므로 O(1) 시간 안에 작업이 가능합니다(단, 삽입/삭제 위치를 찾는 데 O(n) 시간이 소요될 수 있음).
4. 메모리 효율성:
   • 배열: 배열은 메모리를 연속적으로 할당하기 때문에, 메모리의 빈 공간을 효과적으로 사용할 수 있지만, 크기를 미리 지정해야 하기 때문에 메모리 낭비가 발생할 수 있습니다.
   • 링크드 리스트: 링크드 리스트는 동적 메모리 할당을 통해 필요한 만큼만 메모리를 사용하지만, 각 노드가 데이터 외에도 다음 노드에 대한 참조(포인터)를 저장해야 하므로 추가적인 메모리 오버헤드가 발생합니다.

 

질문의 의도

이 질문의 의도는 면접자가 기본적인 데이터 구조에 대한 이해를 가지고 있는지, 그리고 각각의 데이터 구조가 어떤 상황에서 적합한지 설명할 수 있는지를 평가하려는 것이다. 자바에서 배열과 링크드 리스트를 사용할 때의 장단점, 성능 차이 등을 알고 있는지를 확인하려는 목적이다. 또한, 면접자는 이러한 차이점을 설명할 때 관련된 시간 복잡도와 메모리 사용의 효율성에 대한 이해를 가지고 있는지를 보여줘야 한다.