귀염둥이의 메모

연결 리스트(Linked List) 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. k번째 원소를 확인/변경하기 위해 O(k)가 필요하다. 임의의 위치에 원소를 추가, 제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) : 각 원소가 자신의 다음 원소의 주소를 갖고 있다. 이중 연결 리스트(Doubly Linked List) : 각 원소가 자신의 이전 원소와 다음 원소의 주소 둘다를 갖고 있다. 원형 연결 리스트(Circular Linked List) : 끝이 처음과 연결되어있다. 배열 vs 연결 리스트 메모리 상의 배치는 배열은 연속..