[바킹독 실전 알고리즘] 0x04 연결리스트

연결 리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함
2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움(코테에서는 딱히 몰라도 상관 없음)

연결 리스트의 종류



• 단일 연결 리스트는 각 원소가 자산의 다음 원소의 주소를 들고 있는 연결 리스트.
• 이중 연결 리스트는 각 원소가 이전 원소와 다음 원소의 주소를 둘 다 들고 있음. 다만 원소가 가지고 있어야하는 정보가 1개 더 추가되니 메모리를 더 쓴다는 단점
• 원형 연결 리스트는 끝이 처음과 연결되어 있음. 단일 연결리스트나 이중 연결 리스트여도 상관 없음

배열vs연결 리스트

연결리스트는 코테에서는 그리 심화적으로 다루는 유형은 없다 단지 사용방법을 익히면 될듯