본문 바로가기

# Foundation/자료구조

환형 배열 (원형 배열)

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

배열의 특성과 한계

  • 메모리 위에서 일렬로 인접하게 저장된다.
  • 한번 정해진 데이터의 수용량을 확장하기 힘들다.
  • 어떤 위치든 빠르게 데이터를 얻을 수 있다.  (상수시간)
  • 처음이나 중간에 데이터를 삽입하려면 데이터를 한칸씩 뒤로 밀어내야 한다.  (선형시간)
  • 처음이나 중간에 데이터를 삭제하려면 데이터를 한칸씩 앞으로 당겨야 한다.  (선형시간)
  • 마지막 위치에서 데이터를 삽입/삭제하는 것은 빠르다.  (상수시간)



환형 배열 (원형 배열)

배열의 처음과 끝을 유동적으로 바뀔 수 있게 변경한 형태.

인덱스 관리비용을 지불하고,  첫 지점에서의 삽입/삭제 성능을 얻을 수 있다.




환형 배열의 특성

  • 배열의 처음과 끝을 의미하는 포인터 2개를 관리.  (Front,  Rear)
  • 첫 지점에서의 삽입/삭제성능이 상수시간으로 향상됨.





'# Foundation > 자료구조' 카테고리의 다른 글

그래프 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04
큐 ADT  (0) 2019.02.03
스택 ADT  (0) 2019.02.03
해시 테이블 ADT  (0) 2019.02.03