[면접준비] Array, LinkedList에 대해 설명해주시고 각각 어떻게 사용하는지 말씀해주세요. (24/04/08)

Array

1. 정의 
   • 고정된 크기의 연속적인 메모리 공간에 원소들을 저장하는 자료구조
2. 특징
   • 고정된 크기 : 생성시 크기가 정해지며, 이후에 크기를 동적으로 변경하기는 어렵다.
   • 인덱싱 : 인덱스를 사용해 접근, 접근에 O(1)시간이 걸림.
   • 메모리 사용 : 연속적인 메모리 공간을 사용하므로 메모리 관리에 용이함.

LinkedList

1. 정의
   
   • 노드들의 집함. 각 노드는 데이터와 데이터를 가리키는 포인터로 구성되어 있음.
2. 특징
   • 동적 크기 : 크기를 동적으로 변경할 수 있기 때문에 노드를 추가하거나 삭제하면서 크기 조절 가능.
   • 포인터 : 링크드 리스트에서 각 노드들은 다음 노드를 가리키는 포인터를 포함하고 있다.
   • 메모리 사용 : 비연속적인 메모리 공간을 사용한다.

 

답변

Array와 LinkedList는 데이터를 저장하는 자료구조 입니다.

배열(array)는 고정된 크기의 연속적인 메모리 공간을 사용하는 자료구조로, 

O(1)시간에 인덱싱으로 원소에 접근합니다. 중간 원소 추가와 삭제에는 O(n)시간이 걸립니다.

연결 리스트(LinkedList)는 노드들의 집합으로, 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있습니다.

크기를 동적으로 조절할 수 있으며, 원소 조회에 O(n)시간이 걸리고 추가 삭제에 걸리는 시간은 위치에 따라 달라집니다.

원소를 자주 추가/삭제 할 경우 링크드 리스트가, 원소에 빠르게 접근해야 할 경우 배열이 더욱 적절합니다.

따라서, 상황에 맞게 적합한 구조를 선택하여 사용해야 합니다.