Array & Linked List

Array

Array란 ?

Array는 연관된 data를 메모리상에 연속적, 순차적 으로 미리 할당된 크기만큼 저장하는 자료구조 이다.

Dynamic Array

Array는 size를 미리 선언하여 고정되어 있다. size를 변경하려면 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당해야한다. 이것을 Dynamic array라고 한다. 저장공간이 가득차게 되면 resize를 하여 유동적으로(자동적으로) size를 저장하는 자료구조 이다.

• Doubling : resize의 대표적 방법으로, 메모리를 초과하게 되면 기존 배열의 size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮기는 방법이다.

• 분할상환 시간복잡도(Amortized time complexity)

Linked List

Linked List란?

Linked List는 Node라는 구조체로 이루어져 있다. 데이터 값과 다음 Node의 address를 저장해야한다. 물리적인 메모리상에서는 비연속적으로 저장되지만, 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조 이다. 또한, 데이터가 추가되는 시점에서 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용할 수 있다.

Array vs Linked List

—	Array	Linked List
저장	연속적으로 저장	비연속적으로 저장 (논리적 연속성)
조회	O(1)	O(n)
삽입/삭제	O(n)	O(1)

따라서,

Array

• 조회 작업이 많을 때
• 저장할 데이터의 개수를 미리 알고 있을 때
• 메모리를 적게 쓰는게 중요할 상황일 때

Linked List

• 삽입 / 삭제 작업이 많을 때
• 저장할 데이터의 개수를 예측할 수 없을 때
• 조회 작업이 별로 없을 때