[자료구조] 2중 연결 리스트(Doubly linked list) Introduction

bolee·2022년 9월 27일
0

자료구조

목록 보기
7/10
post-thumbnail

널널한 개발자 TV의 자료구조 강의 시리즈를 정리할 것이다.

2중 연결 리스트

  • 2중 연결 리스트는 연결에 사용된 포인터 숫자가 2개이다.
  • 포인터 하나는 자신의 이전을 가리키고, 다른 하나는 자신의 다음을 가리키는 것이 특징이다.
  • 양방향 접근이 가능하다.
  • 말하자면 방향이 다른 단일 연결 리스트(Single Linked List) 2개를 중첩하고 합성한 개념이라고 할 수 있다.

2중 연결 리스트 구현 시 고려사항

  • 더미 헤드(Dummy Head)/테일 노드(Tail Node)를 넣는다.
  • head.next == &tail이면 Empty
  • 노드가 하나만 있어도 prev, next 포인터는 절대 NULL이 될 수 없다!(Head와 Tail 때문에)

구현 전 필요한 함수 목록 정의

  • InitList() / ReleaseList()
  • PrintList()
  • FindNode()
  • DeleteNode()
  • InsertAtHead() / InsertAtTail()
  • GetLength() / GetSize()

구현 전 고려할 사항

  • 열거형 상수 정의가 필요한가?
    • 예를 들어 에러 발생 시 에러에 대한 값을 열거형 상수로 처리하여 코드의 가독성을 높일지?
  • 연결 리스트로 관리할 대상 자료와 자료구조 그 자체를 분리할 것인가?
    • 분리 해야 한다.
  • 에러 코드에 대해 정의할 것인가?
    • 열거형 상수 또는 symbolic 상수로 사용할 지 고민해야 함
  • UI와 자료구조를 분리할 것인가?
    • UI, Data Structure, Control(제어 체계) 을 분리 시킬 방법을 찾아 분리하는 것이 좋다.

구현 전 필요한 전역변수 정의

  • Dummy head, tail 포인터 (혹은 노드)
  • 전체 노드 개수를 저장하는 변수

참고 자료

0개의 댓글