In-Memory DB 구현 7편 - 이중 연결 리스트로 List 명령어 구현하기
들어가며 이번 포스팅에서는 이중 연결 리스트를 직접 구현하고, 저장소를 다중 타입으로 확장하여 LPUSH, RPUSH, LPOP, RPOP, LRANGE 명령어를 추가한다. 배열과 연결 리스트의 근본적인 차이부터 시작해서 왜 이중 연결 리스트가 이 상황에 적합한지, 그리고 포인터로 노드 간 연결을 어떻게 구현하는지를 다룬다. 배열과 연결 리스트 데이터를 순차적으로 저장하는 가장 기본적인 두 자료구조가 배열과 연결 리스트이다. 이 둘의 핵심 차이는 메모리 배치에 있다. 배열은 연속된 메모리 공간에 요소를 나란히 저장한다. 컴파일러가 시작 주소 + (인덱스 × 요소 크기)로 바로 계산할 수 있기 때문에 인덱스 접근이 O(1)이다. 하지만 앞쪽에 요소를 삽입하거나 삭제하면 나머지 요소를 전부 한 칸씩 밀거나 당겨야 하므로 O(n)이 된다. go의 슬라이스([]string)가 내부적으로 배열 기반이다. ...