[List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교

순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교

List를 구현하는 방법에는 순차 리스트(배열), 연결 리스트 존재한다.

    ※ 관련 연산: 삽입(insert), 접근(access) 및 탐색(search), 삭제(delete)

각각의 구현방식마다 장/단점이 존재하며, 주어진 상황에 따라 적합한 방식을 선택해야 한다.

    ex) PS와 같이 제한조건이 명시되어 있다면 정적할당 방식이 유리

 

순차 리스트 (정적 배열)

- 배열로 구현되어 있기 때문에 순차 및 임의 접근 (random access)이 가능하다. 

- 크기가 고정 : 공간이 낭비되거나 재할당(reallocation)이 필요할 수 있다

- 배열의 중간에 데이터를 삽입 및 삭제하는 경우 다수의 원소를 이동하므로

  이로 인한 오버헤드가 크다 → 시간 복잡도 : O(N)

 

구현 예시

▶ [스택] Stack 이란?  

[스택] Stack 이란?

▶ [큐] Queue란?  

[큐] Queue란?

 

연결 리스트 (동적 할당)

- 데이터 삽입, 삭제하는 경우 O(1)에 가능하다

- 리스트 길이 제한이 없다. (최대 메모리 공간 내에서)

- 인덱스를 통한 임의 접근(random access)이 어렵다

   따라서 특정한 원소를 탐색하는 경우 최대 O(N) 의 시간이 필요할 수 있다

- 일반적으로 자기 참조 구조체를 이용하여 구현한다.  

 

구현 예시

▶ [스택] Stack (동적할당, 연결리스트 구현)

[스택] Stack (동적할당, 연결리스트 구현)

▶ [큐] Queue (동적할당, 연결리스트 구현)

[큐] Queue (동적할당, 연결리스트 구현)

 

동적할당 단점

- new, delete (혹은 malloc, calloc)에 따른 할당 시간 비용

- 메모리 단편화(fragmentation)에 의한 누수(Leakage)

- 할당 실패 시 프로그램이 Holding 상태

▶ 정적할당과 동적할당의 특징을 구현해놓은 형태로 Memory Pool 방식이 존재한다.

 

Memory Pool 방식

연결리스트를 정적할당한 형태로, 순차 리스트 + (동적) 연결리스트의 장점을 합친 형태

- 필요한 만큼 미리 확보해서 사용 (재활용 하지 않으므로 공간 해제 불필요)

- 동적할당이 실제 메모리 공간에서 할당을 했다면 Memory Pool 방식은 초기에

  일정 공간을 정적할당하고, 해당 공간을 필요할 때마다 포인터로 동적으로 연결해주는 방식

 

특징

- 정적할당이기 때문에 Memory 낭비는 있을 수 있지만, PS에서는 크게 문제되지 않습니다.

- new, delete와 같은 비용소모가 없으며, 정적할당이기에 삭제 등을 비롯해서 구현이 용이

- 연결리스트를 이용하기 때문에 중간 삽입/삭제, 2개 이상 자식 노드 요구 등 다양한 문제에 대처 가능.

 

구현 예시

▶ [스택] Stack (Memory Pool 방식 구현)

[스택] Stack (Memory Pool 방식 구현)

▶ [큐] Queue (Memory Pool 방식 구현)

[큐] Queue (Memory Pool 방식 구현)

 

Reference

- [스택] Stack 이란?

- [스택] Stack (동적할당, 연결리스트 구현)

- [스택] Stack (Memory Pool 방식 구현)

- [큐] Queue란?  

- [큐] Queue (동적할당, 연결리스트 구현)

- [큐] Queue (Memory Pool 방식 구현)

 

관련 문제

- [BOJ] 2983 개구리 공주 

- [BOJ] 3217 malloc 

- [BOJ] 2533 사회망 서비스(SNS) 

- [Jungol] 2462 키 순서 

- [BOJ] 17616 등수 찾기