[자료구조] 싱글 연결 리스트(Singly Linked List), 더블 연결 리스트(Double Linked List), 원형 연결 리스트(Circle Linked List)

기술 면접 스터디 중 싱글, 더블, 원형 연결 리스트의 개념이 애매해서 정리해는 시간을 갖는다!

1️⃣싱글 연결 리스트(Singly Linked List)

• 구조 : 각 노드가 데이터 + 다음 노드 포인터(next)만 가진다.
• 특징
  • 앞에서 뒤로 단방향 탐색만 가능
  • 메모리 사용이 적음 (포인터 1개).
  • 삽입/삭제가 특정 위치(앞, 중간)에서 배열보다 유리
• 단점
  • 역방향 탐색 불가
  • 중간 노드 삭제 시 이전 노드 탐색이 필요 → O(n)
• 사용 예시
  • 단순 큐 구현
  • 가비지 컬렉션

---

2️⃣더블 연결 리스트 (Doubly Linked List)

• 구조 : 각 노드가 데이터 + 이전(prev) 포인터 +다음(next) 포인터를 가진다
• 특징
  • 앞/뒤 양방향 탐색 가능
  • 삽입/삭제 시 이전 노드를 몰라도 O(1)로 가능(포인터만 조작하면 된다)
• 단점
  • 메모리 사용량 증가(포인터 2개 필요)
  • 구현 복잡도 상승
• 사용 예시
  • Deque, LRU Cache(양방향 탐색, 중간 삭제가 빠른 자료구조 필요할 때)
  • 운영체제의 프로세스 관리(프로세스 제어 블록을 양방향 리스트로 연결)

---

3️⃣원형 연결 리스트 (Circular Linked List)

• 구조 : 마지막 노드의 포인터가 처음 노드(head)를 가리킴
• 특징
  • 끝과 처음이 이어져 있다 → 순환 구조
  • 싱글/더블 모두 원형으로 구현 가능
• 단점
  • 순회 중 무한 루프 주의 필요
  • 구현이 상대적으로 복잡
• 사용 예시
  • 라운드 로빈(Round Robin) 스케줄링 (운영체제)
  • 버퍼 구조(원형 큐)
    

---

📊비교

자료구조	포인터 개수	탐색 방향	장점	단점	대표 활용
싱글 링크드 리스트	1개 (next)	한 방향만	구현 간단, 메모리 절약	역방향 탐색 불가	단순 큐
더블 링크드 리스트	2개 (prev, next)	양방향	양방향 탐색 가능, 중간 삭제 용이	메모리 사용 많음	LRU Cache, Deque
원형 링크드 리스트	1~2개 (구현 방식)	한 방향/양방향 순환	순환 구조 활용	무한 루프 주의	라운드 로빈 스케줄링

연산	싱글 링크드 리스트	더블 링크드 리스트	원형 링크드 리스트 (단일/이중)
탐색 (Search)	O(n)	O(n)	O(n)
삽입 (앞/뒤)	O(1) (head/tail 참조 시)	O(1) (head/tail 참조 시)	O(1) (head/tail 참조 시)
삽입 (중간)	O(n) (위치 탐색 후 O(1))	O(n) (위치 탐색 후 O(1))	O(n) (위치 탐색 후 O(1))
삭제 (앞/뒤)	O(1) (head 삭제 쉬움, tail 삭제는 O(n) 필요)	O(1) (head/tail 모두 가능)	O(1) (head/tail 모두 가능)
삭제 (중간)	O(n) (이전 노드 필요)	O(1) (노드 참조 시 prev/next만 연결 변경)	O(1) (노드 참조 시 가능)
순회 (Traversal)	O(n)	O(n)	O(n) (순환 구조라 무한 루프 주의)

---

📌LRU Cache(Least Recently Used Cache)

• 정의 : 가장 오랫동안 사용되지 않은 데이터를 제거하는 캐시 알고리즘
• 구현 방식
  • HashMap + 더블 연결 리스트 조합
    • HashMap → 키(key)로 데이터 O(1) 조회
    • Doubly Linked List → 최근 사용된 순서 관리(앞 : 최신, 뒤: 오래된)
• 시간 복잡도
  • 조회 : O(1)
  • 삽입/갱신 : O(1)
• 활용 예시
  - 웹 브라우저 캐시
  - 데이터베이스 페이지 교체
  - 메모리 캐싱 시스템
  👉 LRU는 더블 링크드 리스트 + 해시맵 조합의 대표 사례