2022.11.10 TIL 알고리즘

배열

배열은 크기가 정해진 데이터의 공간 정적으로 선언 시 크기 변경 불가능

각 원소에 즉시 접근 가능, 시간 복잡도 O(1)

원소 추가,삭제 시

새로운 공간을 할당해야 함, 비효율적 O(N)

 

Lingked List(연결 리스트)

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

Head와 Next를 통해 중간에 원소 삽입,삭제가 용이함  O(1)

반면 조회는 첫 원소부터 차례대로 조회하므로 시간 복잡도는  O(N)

 

자료구조 선택 시 고려사항
삽입시각, 삭제시간, 검색시간, 정렬여부

 

간단한 개념이고 많이 학습했지만 그때마다 헷갈리는 자료구조