Doubly Linked List & Circular Linked List

2023. 4. 13. 20:46·📚 Data Architect/Data Structure
목차
  1. 💡 이중 연결 리스트 & 원형 연결 리스트
  2. 이중 연결 리스트
  3. 원형 연결 리스트

💡 이중 연결 리스트 & 원형 연결 리스트

전에 만들었던 단순 연결 리스트에 previous 필드를 추가한다
즉, 이중 연결 리스트의 Node 구성은 next & prev & data 3개의 요소가 들어감


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

tail.next가 null이 아닌 연결 리스트의 노드를 가리키는 연결리스트


단순 연결 리스트의 단점
tail 포인터가 있더라도 removeLast()를 하기 위한 시간복잡도는 O(n)으로
마지막 요소부터 앞으로 넘어갈 방법이 없으므로 비효율적이다.
무조건 처음부터 시작해서 마지막의 2번째 요소까지 와야 마지막 요소를 삭제 할 수 있었다


왼쪽 - 이중 연결 리스트 & 오른쪽 - 원형 연결 리스트


이중 연결 리스트

  • previous 필드를 추가함으로써 처음부터 순회를 하지 않고 임의의 포인터도 만들 필요가 없으며,
    시간 복잡도도 O(1)로 바뀐다
  • tail.previous.next = null로 가리키고 tail = tail.previous 로 포인터를 이동해주면
    기존의 마지막 요소를 가리키는 대상이 전부 없으지므로 가비지 컬렉션 대상이 되고
    남은 data 객체를 반환하고 필요에 따라 currentSize도 반영해주면 된다

원형 연결 리스트

  • 임시 포인터 2개를 활용해서 리스트가 원형인지 확인할 수 있다
  • tail이 head를 가리키는 경우
    • head에서 시작해서 임시포인터가 null이 될떄 까지 반복하면 시간복잡도는 O(n)
    • tail.next를 사용한다면 시간복잡도는 O(1)
    • 임시 포인터를 만들어 임시포인터.next == head
  • tail이 리스트의 다른 요소를 가리키는 경우
    • tail에서 시작하여 tail 포인터가 다시 나타나는지 확인, 이때 시간복잡도는 O(n)
    • 임시 포인터 2개를 사용하여 시작점을 잡고 currentSize 만큼 떨어진 노드까지 확인 후,
      시작점을 다음으로 옮겨갈때까지 반복, 이때 시간복잡도는 O(n^2) 이다
저작자표시 (새창열림)

'📚 Data Architect > Data Structure' 카테고리의 다른 글

Queue  (0) 2023.04.13
Stack  (0) 2023.04.13
Singly Linked List (단순 연결 리스트)  (0) 2023.04.13
Iterator  (0) 2023.04.13
Time Complexity (시간 복잡도 - Big O Notation)  (0) 2023.04.13
  1. 💡 이중 연결 리스트 & 원형 연결 리스트
  2. 이중 연결 리스트
  3. 원형 연결 리스트
'📚 Data Architect/Data Structure' 카테고리의 다른 글
  • Queue
  • Stack
  • Singly Linked List (단순 연결 리스트)
  • Iterator
신건우
신건우
조용한 개발자
  • 신건우
    우주먼지
    신건우
  • 전체
    오늘
    어제
    • 분류 전체보기 (422)
      • 📘 Frontend (71)
        • Markup (1)
        • Style Sheet (2)
        • Dart (8)
        • Javascript (12)
        • TypeScript (1)
        • Vue (36)
        • React (2)
        • Flutter (9)
      • 📘 Backend (143)
        • Java (34)
        • Concurrency (19)
        • Reflection (1)
        • Kotlin (29)
        • Python (1)
        • Spring (42)
        • Spring Cloud (5)
        • Message Broker (5)
        • Streaming (2)
        • 기능 개발 (5)
      • 💻 Server (6)
        • Linux (6)
      • ❌ Error Handling (11)
      • 📦 Database (62)
        • SQL (31)
        • NoSQL (2)
        • JPQL (9)
        • QueryDSL (12)
        • Basic (4)
        • Firebase (4)
      • ⚙️ Ops (57)
        • CS (6)
        • AWS (9)
        • Docker (8)
        • Kubernetes (13)
        • MSA (1)
        • CI & CD (20)
      • 📚 Data Architect (48)
        • Data Structure (10)
        • Algorithm (8)
        • Programmers (17)
        • BaekJoon (5)
        • CodeUp (4)
        • Design Pattern (4)
        • AI (0)
      • ⚒️ Management & Tool (8)
        • Git (7)
        • IntelliJ (1)
      • 📄 Document (10)
        • Project 설계 (6)
        • Server Migration (3)
      • 📄 책읽기 (2)
        • 시작하세요! 도커 & 쿠버네티스 (2)
      • 🎮 Game (4)
        • Stardew Vally (1)
        • Path of Exile (3)
  • 블로그 메뉴

    • 링크

      • Github
    • 공지사항

    • 인기 글

    • 태그

      React #Markdown
      Lock #Thread #Concurrency
      GStreamer #Pipeline
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.0
    신건우
    Doubly Linked List & Circular Linked List
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.