* Doubly Linked List를 구현한 클래서 DList를 정의하여라.
* Doubly Linked List는 Linked List와 매우 유사하나, 각 노드가 리스트의 다음노드 (next) 뿐만 아니라 이전노드 (prev)도 알고 있는 자료구조를 말한다. 아래 그림은 Doubly Linked List의 예를 보여준다.
* DList는 LList처럼 첫번째 노드를 가리키는 head뿐만 아니라 마지막 노드를 가리키는 tail도 갖고 있다.
* 첫번째 노드의 prev 와 마지막 노드의 next 값은 NULL로 정한다.
* DList가 비어있을 때에는 head와 tail 모두 NULL값을 갖고 있다.
* Class DList는 다음과 같은 함수를 지원해야 한다.
bool isEmpty() : DList가 비어있으면 참을, 아니면 거짓을 리턴한다.
void append(T data) : 리스트의 맨 마지막 노드 다음으로 한 노드를 추가하고 그 값은 data로 한다.
void prepend(T data) : 리스트의 맨 처음 노드 앞으로 한 노드를 추가하고 그 값은 data로 한다. 리스트가 비어 있으면 append와 prepend의 결과는 같다.
void print() : 리스트에 보관된 모든 데이터를 다음과 같은 형식으로 출력한다.
1 ↔ 2 ↔ 3 ↔ 4
비어있으면 Empty라고 출력한다.
int count() : 리스트에 보관된 노드 수를 리턴한다.
Node<T> *find(T data) : 리스트 내에 data를 갖고 있는 첫번째 노드를 찾아서 그 주소를 리턴한다. 존재하지 않으면 NULL을 리턴한다.
void insert(Node<T> *n, T data) : 주어진 노드 n 바로 뒤에 새로운 노드를 추가하고 값을 data로 한다. n 값이 NULL 이면 추가하지 않는다.
void remove(T data) : data값을 갖고 있는 모든 노드를 삭제한다. 존재하지 않으면 삭제하지 않는다.
제출할 파일:
#include <iostream>
template <class T>
class DList {
Node<T> *head;
Node<T> *tail;
public:
// 작성
};
int main() {
// 자신의 테스트 코드를 넣는다.
}
class/os2014f/hw11.txt · Last modified: 2017/06/17 09:36 (external edit) · [
Old revisions]