Array 와 Linked List

0. 들어가며

개발을하며 정말 많이 볼 수 있는 Array와 Linked List에 대한 설명과 특징들에 대하여 기술하겠습니다.

 

1. Array의 특징

• 배열은 메모리상 연속된 공간에 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 입니다.
• 기존 size 보다 더 많은 데이터를 저장하려면 사이즈를 재설정하는 과정이 필요합니다.
• 조회가 빨라서 해당 작업이 많이 사용될때 좋은 자료구조입니다.
• 크기를 미리 정해야하므로 메모리 공간의 낭비나 overhead가 발생할 수 있습니다.
• 이를 예방하기위해 동적으로 배열의 크기를 조절하는 Dynamic Array를 사용할 수 있습니다.

 

Dynamic Array

• 저장공간이 가득 차게되면 doubling등의 resizing을 통해 동적으로 크기를 조절하는 자료구조
• LinkedList와 비교했을 때
  • 조회, 할당(get): O(1)
  • 마지막 원소에 데이터 추가, 삭제: O(1)
  • 마지막이 아닌 원소 데이터 추가, 삭제: O(n)
  • resize를 진행할때 overhead 발생

2. Linked List의 특징

• Linked List는 Node라는 구조체로 이루어져있는데, 각 Node는 데이터와 다음 원소의 주소값을 저장합니다.
• 물리적 메모리상 비연속적으로 저장되어있지만 주소값을 가져 논리적 연속성을 가집니다.
• 데이터가 추가되는 시점에 메모리를 할당하여, 메모리 공간을 효율적으로 사용할 수 있습니다.
• 주소값을 추가로 저장해야하므로 메모리 공간 또한 추가적으로 사용됩니다.

3. 두 자료구조의 비교

	Array	LinkedList
조회, 할당	O(1)	O(n)
마지막 원소에 추가, 삭제	O(1)	O(1)
마지막이 아닌 원소에 추가, 삭제	O(n)	O(1)

• LinkedList의 원소 추가 및 삭제의 경우 O(1)이지만 실질적으로 추가 및 삭제하려는 원소의 index까지 이동해야하므로 전체 과정은 O(n)이라고 할 수 있습니다.
• Array의 경우 마지막 원소에 추가, 삭제는 동적Array를 가정했습니다. 동적 Array의 경우 배열 사이즈보다 많은 원소를 추가하면 더블링을 통해 배열을 리사이징하게됩니다. 이때 더블링은 O(n)이 필요합니다
• 두 자료구조 모두 Heap영역에 할당이 일어납니다

4. 결론

조회 및 할당을 많이 하는 경우에 Array를 사용하는것이 좋습니다. 그 외에 전체 데이터 크기를 단언 하기 힘들거나 삽입 삭제를 자주할때 LinkedList를 사용하는것이 좋습니다.