배열

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

특징

• 고정된 저장 공간(fixed-size)
• 순차적인 데이터 저장(order)
• 중복을 허용하고 순서가 있다.
• 랜덤 접근(random access)가 가능

  • 랜덤접근(직접 접근)
    • 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
  • 순차적 접근
    • 데이터를 저장된 순서대로 검색한다.

메모리 할당

• Array는 compile 단계에서 memory allocation이 일어납니다. 이를 Static Memory Allocation이라고 합니다. 이 경우 Stack memory영역에 할당됩니다.

장단점

• 장점
  • 인덱스(index)로 해당 원소(element)에 접근할 수 있어 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다.
• 단점
  • 선언시에 Array의 크기를 미리 정해야 된다는 것입니다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있다.
  • 삽입 또는 삭제의 과정에서 각 원소들을 shift 해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n)이 된다는 단점이 있습니다.
  • Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다 → dynamic Array로 해결

시간복잡도

	Array
access	$O(1)$
append	$O(1)$
마지막 원소delete	$O(1)$
insertion	$O(n)$
deletion	$O(n)$
search	$O(n)$

Dynamic Array

• Dynamic Array는 Array의 특징중에 fixed-size의 한계점을 보완하고자 고안된 자료구조이다.
• Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조

Resize

• Data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 되게 하는것
• Doubling
  • 데이터를 추가하다가 메모리를 초과하게 되면 기존 배열의size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮기는 방법입니다.
  • n개의 데이터를 일일이 옮겨야 하므로 소요
• append의 시간 복잡도 : amortized O(1)
• 나머지 작업운 배열과 시간복잡도가 같다.

append의 총과정을 살펴보면 데이터를 마지막 인덱스에 추가하는 O(1) 작업이 대다수이고,

size를 넘어설때는 size를 두 배 늘리고 데이터를 일일이 옮기는 과정 resize가 발생 (O(n)이 가끔발생

→ 가끔 발생하는 O(n)의 resize하는 시간을 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써 전체적으로 O(1)시간이 걸린다고 판단한다.

벡터

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모른다면 벡터를 써야한다.
• 중복을 허용하고, 순서가 있으며 랜덤 접근이 가능하다.
• 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1)이 소요
• 맨뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)이 소요

연결 리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
• Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장한다.

특징

• 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진다.
• 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.
• prev 포인터와 next포인터로 앞과 뒤의 노드를 연결한다.

장단점

• 장점
  • 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결할 수 있습니다.
• 단점
  • LinkedList는 원하는 위치에 한 번에 접근할 수 없다
  • 첫번째 원소부터 다 확인해봐야하므로 O(n)의 시간복잡도가 소요

메모리 할당

• Linked List의 경우 runtime 단계에서 새로운 node가 추가될 때마다 memory allocation이 일어납니다. 이를 Dynamic Memory Allocation이라고 부릅니다. Heap메모리 영역에 할당됩니다.

종류

• 싱글 연결 리스트
  • next 포인터만 가진다.
• 이중 연결 리스트
  • next 포인터와 prev포인터 모두 가진다.
• 원형 이중 연결리스트
  • 마지막 노드 next 포인터가 헤드 노드를 가리킨다.