CS/자료구조와 알고리즘 (10) 썸네일형 리스트형 연결리스트 연결리스트란 무엇인가? -원소들을 저장할때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결리스트의 성질은? K번째 원소를 확인/변경하기 위해 O(K)가 소요됨 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 쉬움 추가적으로 필요한 공간(Overhead)가 O(n)이 필요(주소값) 연결리스트의 종류 단일 연결 리스트 이중 연결 리스트 원형 연결 리스트 연결리스트의 용도는? 임의의 위치에서 원소를 추가/삭제가 빈번할때(ex. 메모장) 커서 이동이 빈번할때 STL list L = {1,2}; list auto t = L.begin(); L.push_front(10); // 10 1 2 cout 배열(array) 배열이 무엇인가? -메모리상에 원소를 연속하게 배치한 자료구조 Vector(C++)는 무엇인가? -배열과 유사하나 크기를 자유자재로 변경이 가능 배열의 성질은? O(1)에 K번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양이 거의 없음 Cache hit rate가 높음(확률적으로 바로 옆의 메모리를 쓰는 경우가 많음) 메모리상에 연속된 구간을 잡아야해서 할당에 제약이 걸림 배열의 용도는? 데이터를 자주 바꾸지 않고 쌓아둘때 입력값을 담아둘때 인덱스에 해당하는 원소를 O(1)으로 접근할때 문제해결에 있어서 배열의 활용 방식은? ex1) 알파벳 갯수 세기: freg[c - 'a']++; ex2) 인덱스를 활용한 카운팅 STL vector v1(4,5); // {5,5,5,5} cout 이전 1 2 다음