1. 배열(Array)

---

배열(Array) 특징

[Array]

• 시간복잡도 : O(N)
• 크기를 재조정하는 연산을 수행해서 크기를 늘릴 수 있지만, 상당한 연산량이 요구된다.
• 무작위 접근(random access)가 가능하다.

[장단점]

장점

• 인덱스를 통한 검색에 적합 → 특정 자료 탐색 시간 소요 LinkedList에 비해 적음

단점

• 삽입, 삭제 오래걸림
• 크기가 한정되서 결국 포화상태에 이름
• 크기를 재조정하는 연산수행시 상당한 연산량 요구됨

동적 배열(Dynamic Array (=vector))

배열의 크기를 자동적으로 resizing하는 array이다.

data를 계속 추가하다 기존에 할당된 memory를 초과하면 size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 된다.

[Dynamic Array 장단점]

Dynamic array 장점

• size를 고민할 필요가 없다

Dynamic array 단점

• resize 시, 낮은 퍼포먼스가 발생한다
• resize에 시간이 많이 걸리므로 필요한 것 이상의 memory 공간을 할당받기 때문에 사용되지 못하고 낭비되는 메모리 공간 발생

Doubling : 동적 배열 확장

개념 : 크기를 약 두 배로 증가시키는 방법

• 배열의 이전 크기의 2배로 늘려주고 데이터를 옮긴다.

Doubling 장점

• 시간 효율성 : 요소를 추가할 때마다 확장하는 것이 아니라서, 잦은 메모리 재할당이 피할 수 있다.
  • 삽입 작업의 평균적인 시간복잡도를 상수 시간(O(1))로 만들어준다.
• 공간 효율성 : 크기가 두배로 증가한다. -> 이는 불필요한 공간 낭비를 줄여준다 ??
• 성능 최적화 : 빈번한 메모리 할당 및 복사 작업 감소로 인해 성능이 향상된다.

Doubling 단점

• 메모리 낭비 가능성 : 배열의 크기를 두 배로 증가시킬 때, 실제 사용되는 양보다 훨씬 많은 메모리를 할당할 수 있다. 특히 배열의 현재 크기가 큰 경우, 이러한 낭비는 더욱 두드러질 수 있다.
• 불필요한 재할당: 배열의 크기가 현재 요구되는 크기보다 훨씬 클 때, 배열의 크기를 줄이지 않으면 메모리가 낭비될 수 있다.

Q. 2차원 배열의 물리적 주소는 어떻게 되는가 ?

• 1.행우선 방법과 2.열우선 방법이 있다. 아래처럼 행우선은 행을 먼저 저장하고 열우선은 열을 먼저 저장한다.
  

2. 연결 리스트(Linked List)

---

✨LinkedList

• 장점 : 몇 개의 참조자만 바꿈으로써 삽입, 삭제 빠른 시간안에 수행 가능
• 순차접근(sequential access)이 가능 ⇒ 단방향성

즉, LinkedList는 탐색은 느리고, 삽입, 삭제가 빠르다.

시간복잡도

탐색 : O(N)
삽입,삭제: O(1)이지만, 탐색하고 삽입 or 삭제하므로 O(N)

[LinkedList 장단점]

장점

• 삽입, 삭제 빠름
• 동적 크기조정 , 메모리 관리의 장점
• 리스트 내에서 자료의 이동 불필요
• 사용후 기억장소의 재사용이 가능 (참조지역성)
• 무한개수의 자료 삽입 가능 (메모리 용량이 무한하다고 할때)
• 자료의 최대개수 영향 안받음

단점

• 크기가 한정되서 결국 포화상태에 이름
• 크기를 재조정하는 연산수행시 상당한 연산량 요구됨
• 참조 지역성(참조한 데이터 다시 참조 가능성 높고 주변 데이터 역시 참조될 가능성 높음)때문에 ArrayList가 훨씬 빠르다.

  • ArrayList는 연속된 공간에 저장되어 있기 때문에 참조 지역성을 이용할 수 있음

• 인덱스를 통한 검색에 적합하지 않음 (why? 단방향성이라서) → 특정 자료 탐색 시간 소요 많음
• 참조자를 위해 추가적인 메모리를 할당해야 한다.

[LinkedList 삽입 과정]

삽입 과정

삭제 과정