[자료구조] Array, List

이창민·2022년 7월 18일
0

자료구조

목록 보기
1/5

Array

  • 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조
  • 논리적 저장 순서와 물리적 저장 순서 일치
  • 해당 인덱스로 해당 원소에 접근
  • 인덱스는 value에 대한 유일무이한 식별자

장점

  • 원소의 인덱스를 알면 접근시 O(1)
  • 데이터가 모여있기 때문에 cache hit rate가 높음

단점

  • 원소를 중간에 삽입이나 삭제시 한칸씩 땡기거나 밀어줘야하기 때문에 O(N)
  • 크기가 고정되어 사용하지 않는 공간 낭비

List

  • 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음
  • 원소들 간의 순서가 있는 데이터의 모임
  • 원소들은 자기 다음이 어떤 원소인지 기억하고 있음
  • 인덱스는 몇번째 데이터인가 정도의 의미

장점

  • 원소의 삽입이나 삭제시 원소의 다음 원소만 바꿔주면 되기 때문에 O(1)
  • 크기가 정해져 있지 않음

단점

  • 배열과 다르게 검색시 처음부터 찾아가야하기 때문에 O(N)
  • 각 원소는 다음 원소를 알고 있어야하기 때문에 추가적인 메모리 사용
  • 데이터의 순차성이 보장되지 않기 때문에 cache hit가 어려움
profile
android 를 공부해보아요

0개의 댓글