배열(Array, Static Array)

• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
• 메모리상에서 연속적으로 저장되어 있는 특징을 갖기 때문에, index를 통한 접근이 용이하다.
• 배열의 크기는 처음 생성할 때 정하며, 이후에는 변경할 수 없다.

시간 복잡도

• 탐색 : $O(1)$
  • 단, 접근하고자 하는 인덱스를 알고 있어야 한다.
  • 순차적으로 탐색 시에는 $O(n)$
• 삽입 및 삭제
  • 배열의 처음 또는 중간에 삽입 및 삭제 : $O(n)$ (삽입 지점 이후의 데이터를 옮겨야 하기 때문)
  • 배열의 끝에 삽입 및 삭제 : $O(1)$

연결리스트 (Linked List)

• 여러 개의 노드 들이 순차적으로 연결된 형태를 갖는 자료구조
• 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.

시간 복잡도

• 탐색 : $O(n)$
• 삽입 및 삭제 : $O(1)$
  • 연결리스트의 처음에 삽입 및 삭제 : $O(1)$
  • 연결리스트의 중간에 삽입 및 삭제 : $O(n)$ (탐색 시간 소요)
  • 연결리스트의 끝에 삽입 및 삭제
    • 끝을 가리키는 별도의 포인터를 갖는 경우 : $O(1)$
    • 끝을 가리키는 포인터를 갖지 않는 경우 : $O(n)$ (탐색 시간 소요)

Array vs Linked List

	Array	Linked List
특징	- 연속된 메모리 공간에 존재 - 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당 - Stack 영역에 메모리 할당	- 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재 - 런타임 환경에서 메모리가 할당되는 동적 메모리 할당 - Heap 영역에 메모리 할당
장점	인덱스를 통한 빠른 접근이 가능하다.	삽입과 삭제가 용이하다.
단점	삽입과 삭제가 오래 걸린다. 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.	임의 접근이 불가능하여, 처음부터 탐색을 진행해야 한다.
시간복잡도	조회 : O(1) 삽입 및 삭제 : O(n)	조회 : O(n) 삽입 및 삭제 : O(1)
용도	빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때	삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

Dynamic Array (Array List)

• 고정된 길이를 갖는 Array의 한계를 극복하기 위해 나온 자료구조

배열의 한계

• Array는 길이를 바꿀 수 없다.
  • 길이를 바꾸기 위해서는 새로운 길이의 배열을 메모리에 따로 할당하고, 데이터를 복사한 후, 기존의 배열의 삭제하는 세 가지 과정을 거쳐야한다. (비효율적)
• Array는 데이터가 없어도 메모리를 차지하기 때문에, element 가 삭제되어도 빈자리(null)가 남게 된다. (inner fragmentation)
  • 조건문을 통해 데이터가 null인 경우 삭제할 수도 있는데, 앞서 언급한 것처럼 데이터 삭제 시 O(n)의 시간복잡도를 가지기 때문에 비효율적이다.
• 연속된 메모리에 할당되기 때문에, 메모리 공간이 있음에도 outer fragmentation이 발생할 수 있다.

• Dynamic Array 는 크기가 가변적으로 변하는 선형리스트이다.
  • 따라서 크기가 고정되어 있는 배열을 사용하면 비효율적인 작업을 할 때나 처음부터 배열을 크기를 알 수 없는 경우에 사용한다.
• 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점이 유사하다.
  • 하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 Dynamic Array는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고 있다.

시간 복잡도

• 배열의 크기를 변경하는 resize() 연산 : $O(n)$
  • 새로운 크기의 배열을 만든 후 기존 배열을 복사하는 방식으로 진행되기 때문
  • resize의 대표적인 방법으로는 Doubling 이 있으며, 데이터를 추가하다가 메모리를 초과하게 되면 기존 배열의 size 보다 두 배 큰 배열을 선언하고 데이터를 일일이 옮긴다. ($O(n)$)
• 데이터를 배열의 맨 끝에 추가하는 append() 연산 : $O(1)$
  • 재할당 전략 : 데이터가 추가될 때, 배열의 크기를 기존 배열의 크기만큼 늘리는 전략
  • 재할당 전략을 사용하지 않고 데이터의 메모리 크기만큼 배열의 크기를 늘린다면, append()연산을 n번 진행한다고 했을 때 $n(n+1)/(2*n)$만큼, 즉 $O(n)$의 시간 복잡도를 가진다.
    • $(n + 2n + 3n + ... + n^2)/n = (n+1)/2 = O(n)$
  • 재할당 전략을 사용하고 기존 배열에 데이터가 꽉찬 상태에서 데이터가 추가될 때 기존 배열의 크기만큼 배열의 크기를 늘린다면, append() 연산을 n번 진행한다고 했을 때 $O(n/n) = O(1)$만큼의 시간 복잡도를 가진다. 이는 resize() 연산의 시간 복잡도가 $O(n)$이고 이를 평균내면 $O(1)$이기 때문이다.

예상 면접 질문

1. Array는 어떤 자료구조 인가요?
   • 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요?
2. Dynamic Array는 어떤 자료구조 인가요?
   • Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.
3. Linked List에 대해서 설명해 주세요.
4. Array vs Linked list를 비교해서 설명해주세요.
   • 어느 상황에 Linked list를 쓰는게 Array보다 더 나을까요?
   • 어느 상황에 Array를 쓰는게 Linked list보다 더 나을까요?
   • Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나요?

References

[자료구조] 배열과 연결리스트 (Array & LinkedList)
[자료구조] Array와 Linked List의 차이는 무엇일까?
[자료 구조] Array, Dynamic Array, Linked List