널널한 개발자 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 포인터 (혹은 노드)
- 전체 노드 개수를 저장하는 변수
