#include <iostream>
using namespace std;
class Node2 {
int data;
public:
Node2* prev;
Node2* next;
public:
Node2(int val = 0) : data(val), prev(NULL), next(NULL) { }
Node2* getPrev() { return prev; }
Node2* getNext() { return next; }
void setPrev(Node2* p) { prev = p; }
void setNext(Node2* n) { next = n; }
void display() { printf("%d", data); }
bool hasData(int val) { return data == val; }
void insertNext(Node2* n) {
if (n != NULL) {
n->prev = this;
n->next = next;
if (next != NULL) next->prev = n;
next = n;
}
}
Node2* remove() {
if (prev != NULL) prev->next = next;
if (next != NULL) next->prev = prev;
return this;
}
};
class DblLinkedList {
Node2 org; // 헤드 노드
Node2* current; // 현재 선택된 노드 : 현재 곡
public:
DblLinkedList() : org(0), current(0) { } // 생성자
~DblLinkedList() { clear(); } // 소멸자
void clear() { while (!isEmpty()) delete remove(0); } // 모든 노드 삭제
Node2* getHead() { return org.getNext(); } // 헤드 노드 반환
bool isEmpty() { return getHead() == NULL; } // 리스트가 empty이면 true 반환
Node2* find(int val); //데이터가 val인 노드를 찾아서 반환
void replace(int pos, Node2* n); //위치 pos에 있는 노드를 n으로 대체
int size(); //리스트의 총 노드 개수 반환
void display(); //리스트의 모든 노드들 출력
Node2* getEntry(int pos); //pos번째 노드 반환
int insert(int pos, Node2* n); //pos 위치에 노드 삽입
Node2* remove(int pos); //pos 위치에 있는 노드 삭제
int removeNode(int pos); //pos 위치에 있는 노드 삭제
int toFirst(int pos); //1번째 위치로 이동
int toLast(int pos); //마지막 위치로 이동
int toNext(int pos); //다음 위치로 이동
int toPrev(int pos); //이전 위치로 이동
int toNextNext(int pos); //다음 다음 위치로 이동
int toPrevPrev(int pos); //이전 이전 위치로 이동
void printCurrent() { return current->display(); } // 현재 노드 출력
};
//노드 검색: 데이터가 val인 노드를 찾아서 반환
Node2* DblLinkedList::find(int val) {
for (Node2* p = getHead(); p != NULL; p = p->getNext())
if (p->hasData(val)) return p;
return NULL;
}
//노드 대체: 위치 pos에 있는 노드를 n으로 대체
void DblLinkedList::replace(int pos, Node2* n) {
Node2* prev = getEntry(pos - 1);
if (prev != NULL) {
delete prev->getNext()->remove();
prev->insertNext(n);
}
}
//노드 크기: 리스트의 총 노드 개수 반환
int DblLinkedList::size() {
int count = 0;
for (Node2* p = getHead(); p != NULL; p = p->getNext())
count++; //리스트의 각 노드를 따라가면서 count증가
return count;
}
//노드 출력: 리스트의 각 노드를 따라가면서 모든 노드 출력
void DblLinkedList::display() {
cout << "Double Linked List 항목 수 = " << size() << endl;
for (Node2* p = getHead(); p != NULL; p = p->getNext())
p->display();
cout << endl;
}
// 접근자 함수: pos번째 노드 반환
Node2* DblLinkedList::getEntry(int pos) {
Node2* n = &org; // 헤드 노드
for (int i = -1; i < pos; i++, n = n->getNext()) // i증가, 노드 따라가며
if (n == NULL) break; // pos위치를 찾는다.
return n;
}
// 노드 삽입: pos 위치에 노드 삽입
int DblLinkedList::insert(int pos, Node2* n) {
Node2* prev = getEntry(pos - 1); //n-1번째 노드를 찾아서
if (prev != NULL)
prev->insertNext(n); //n-1번째 노드 다음에 n추가
current = n;
pos++;
return pos;
}
// 노드 삭제: pos 위치에 있는 노드 삭제
Node2* DblLinkedList::remove(int pos) {
Node2* n = getEntry(pos); //pos번째 노드 n 찾아서
if (n==NULL) return NULL;
else {
return n->remove(); //노드 n 제거
}
}
// 노드 삭제: pos 위치에 있는 노드 삭제
int DblLinkedList::removeNode(int pos) {
if (current != NULL) {
current = getEntry(pos - 2); //현재 노드를 pos번째 노드 이전 노드로 업데이트
Node2* n = getEntry(pos - 1); //pos번째 노드 n 찾아서: index 0부터 시작
n->remove(); //pos번째 노드 삭제
pos--; //현재 노드 위치를 pos번째 노드 이전 위치로 업데이트
}
return pos;
}
// 이동 연산: 1번째 위치로 이동
int DblLinkedList::toFirst(int pos) {
if (current != NULL)
{
current = getHead();
pos = 1;
}
return pos;
}
// 이동 연산: 마지막 위치로 이동
int DblLinkedList::toLast(int pos) {
int count = 0;
if (current != NULL)
{
for (Node2* p = getHead(); p != NULL; p = p->getNext()) { //마지막 노드로 이동
current = p; //현재 노드를 마지막 노드로 업데이트
count++;
}
pos = count; //현재 노드의 위치를 마지막 노드의 위치로 업데이트
}
return pos;
}
// 이동 연산: 다음 위치로 이동
int DblLinkedList::toNext(int pos) {
if (current->getNext() != NULL)
{
current = current->getNext(); //현재 노드를 다음으로 이동
pos++; //현재 노드의 위치를 다음으로 이동
}
return pos;
}
// 이동 연산: 이전 위치로 이동
int DblLinkedList::toPrev(int pos) {
Node2* prev = current->getPrev();
if (prev != NULL && prev != &org) {
current = prev; //현재 노드를 이전으로 이동
pos--; //현재 노드의 위치를 이전으로 이동
}
return pos;
}
// 이동 연산: 다음 다음 위치로 이동
int DblLinkedList::toNextNext(int pos) {
if (current != NULL) {
if ((current->getNext()) != NULL) { //다음 노드 존재할 때
current = current->getNext(); //현재 노드를 다음으로 이동
pos++; //현재 노드의 위치를 이전으로 이동
}
if ((current->getNext()) != NULL) { //그 다음 노드 존재할 때
current = current->getNext(); //현재 노드를 다음으로 이동
pos++; //현재 노드의 위치를 이전으로 이동
}
}
return pos;
}
// 이동 연산: 이전 이전 위치로 이동
int DblLinkedList::toPrevPrev(int pos) {
if (current != NULL) {
Node2* p = current->getPrev();
if (p != NULL && p != &org ) { //이전 노드 존재할 때, 이전 노드가 헤드 노드가 아닌지도 반드시 체크!!
current = current->getPrev(); //현재 노드를 이전으로 이동
pos--; //현재 노드의 위치를 이전으로 이동
}
p = current->getPrev();
if (p != NULL && p!= &org) { //그 이전 노드 존재할 때
current = current->getPrev(); //현재 노드를 이전으로 이동
pos--; //현재 노드의 위치를 이전으로 이동
}
}
return pos;
}
int main() {
int num, cnt=1, pos=0;
char command;
DblLinkedList m;
// 입력: 명령어 갯수
cin >> num;
for (int i=0; i<num; i++)
{
// 명령어 입력
cin >> command;
// 명령어 처리
switch (command) {
case 'A': pos = m.insert(pos, new Node2(cnt++)); break;
case 'B': pos = m.removeNode(pos); break;
case 'C': pos = m.toFirst(pos); break;
case 'D': pos = m.toLast(pos); break;
case 'E': pos = m.toNext(pos); break;
case 'F': pos = m.toPrev(pos); break;
case 'G': pos = m.toNextNext(pos); break;
case 'H': pos = m.toPrevPrev(pos); break;
default: break;
}
}
// 출력: 현재 곡
m.printCurrent();
return 0;
}
study/자료구조