LRU Cache 이란 ?
여기서의 캐시에는 최대 저장공간이 있다
정해놓은 max_size 보다 cache 가 크다면 overflow 가 발생한다.
여기서 캐시 오버 플로우가 발생할 때
데이터를 지워주는 규칙이 있는데
기본적으로는 가장 오래된 데이터를 지우지만,
정확히는 가장 오래 전에 사용된 데이터를 지운다.
이러한 규칙을 LRU(페이지 교체 알고리즘) 라고 한다.
캐시의 맥스 사이즈를 지켜주기 위함이다.
해시 맵
데이터를 저장하는 put(key, value)
데이터를 가져오는 get(key) => value
이를 해시 맵으로 구현할 수 있다
하지만 해시 맵 의 경우에는
캐시의 max- size가 넘어가는 경우에
어떤 데이터가 가장 과거에 사용되었는지 알 수 없다.
이를 해결하는게 관건인데
대표적으로 array , linkedList 가 있다
array 는 [1,2,3,4] 에 5를 추가하는 과정에서
1을 삭제하고[2,3,4,5] 이런식으로 기존의 2 3 4 들도 전부 위치를 옮겨야하는 점에서
O(1)의 시간복잡도가 요구되는 문제를 O(N) 으로 처리해서 불가능하다
그렇다면 결국 LinkedList 로 해결해야 하는데 꽤 복잡한 과정이라 생각된다.
LinkedList
Node 라는 단위로 구성되어 있는
LinkedList 는 길이가 정해져 있지 않은 데이터의 연결된 집합이다.
LinkedList의 구조
데이터 / 다음 노드를 가르키는 레퍼런스 값 의 구조로 연결연결 되어 있다.
처음은 head로 시작해 끝은 tail 로 끝난다.
우선 단 방향 , 양 방향의 LinkedList를 살펴보자.
Linked List(단 방향)
말 그대로 단 방향은 head 로 시작해 이전 값을 모르고
오직 내 다음 친구만 알고 있는 상태다.
그래서 검색을 할때는 head 부터 시작해 한개씩 노드를 검색을 해야한다.
이렇게 한 방향으로만 이동할 수 있는 Linked List 를 단 방향 Linked List 라고 한다.
단 방향 Linked List의 시간 복잡도
insert : O(1) 자신이 추가하려는 위치의 이전 노드를 알 경우에 O(1)이 된다.
모를는 경우 위치를 조회한 뒤에 작업이 이루어지기 때문에 O(n)이 된다.
Remove : head : O(1) , middle: O(1)
Lookup : O(n)
Find : O(n)
Assign : O(n)
doubly-Linked List (양 방향)
단 방향이 내 다음 노드만 알고 있는 구조라면,
양 방향은 이전 노드의 값도 알고 있는 구조이다.
양 방향 Linked List의 시간 복잡도
insert : O(1) 이 역시도 추가하려는 위치의 이전 노드를 알 경우에 O(1) 이 된다.
Remove : O(1)
Lookup : O(n)
Find : O(n)
Assign : O(n)
