연결 리스트가 무엇인지 알아보고, 구현도 해볼 것이다. 1. 정의와 성질 연결 리스트 정의 연결 리스트란 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 배열과는 다르게 이곳 저곳 흩어져있다. 연결 리스트 성질 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요 - 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) - 배열과 비교앴을 때 큰 차이가 있는 성질이고, 연결 리스트의 큰 장점이다. 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 - 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할..