상황에 맞게 최적의 성능을 내고 싶을 경우 연결리스트를 직접 구현해 사용하기도 한다. 원형 이중 연결리스트를 C++로 구현해 보았다. 노드가 어디에 추가되건 편리하게 사용할 수 있는 장점이 있다. 선형의 경우도 아래 소스를 참고하여 손쉽게 구현할 수 있다.
#include "stdafx.h" #include <iostream> using namespace std; struct User { char name[20]; char email[40]; }; template<typename T> class Node { template<typename T> friend class MyContainer; private: Node* prev; Node* next; T* data; public: Node() { this->prev = NULL; this->next = NULL; this->data = NULL; } Node(T* data) { this->prev = NULL; this->next = NULL; this->data = data; } Node(T* data, Node* prev, Node* next) { this->prev = prev; this->next = next; this->data = data; } }; template<typename T> class MyContainer { private: Node<T>* head = new Node<T>(); public: // 자신을 가리키도 데이터가 NULL인 헤더를 만든다. MyContainer() { this->head->prev = this->head; this->head->next = this->head; this->head->data = NULL; } ~MyContainer() { this->deleteContainer(); delete this->head; } // 생성 Node<T>* createNode(T* data) { // data를 저장할 동적메모리 할당 T* newData = new T(*data); // node를 저장할 동적메모리 할당 // - newNode->prev = lastNode (prev는 마지막 노드를 가리킨다.) // - newNode->next = firstNode (next는 첫번째 노드(head)를 가리킨다.) Node<T>* newNode = new Node<T>(newData, this->head->prev, this->head); // 노드가 삽입될 양옆의 노드 정보를 변경한다. if (this->head == this->head->next) { // 최초 생성일 경우 this->head->next = newNode; } else { // 최초 생성이 아닐 경우 this->head->prev->next = newNode; } // firstNode->prev (첫번째 노드의 prev는 새로운 노드를 가리킨다.) // lastNode->next (마지막 노드의 next는 새로운 노드를 가리킨다.) this->head->prev = newNode; return newNode; } // 삭제 void deleteNode(Node<T>* node) { // 이전노드와 다음노드를 연결한다. node->prev->next = node->next; node->next->prev = node->prev; // 자신을 메모리에서 삭제 delete node->data; delete node; } // 컨테이너 삭제 void deleteContainer() { if (this->head->next != this->head) { // head 만 남지 않았으면 다음노드 삭제하고 재귀호출 this->deleteNode(this->head->next); this->printAll(); this->deleteContainer(); } } // 전체 출력 : 적용시 삭제 void printAll() { if (this->head != NULL) { cout << "\n### head Node ###\n"; cout << "HEAD : " << this->head << "\n"; cout << "PREV : " << this->head->prev << "\n"; cout << "NEXT : " << this->head->next << "\n"; cout << "DATA : " << this->head->data << "\n"; cout << "\n"; cout << "### Node List ###\n"; if (this->head->next != NULL) { for (Node<T>* currentNode = this->head->next; currentNode != this->head; currentNode = currentNode->next) { User* tmpUser = (User*)currentNode->data; cout << "[<-" << currentNode->prev << "]"; cout << "[" << currentNode << "]"; cout << "[" << currentNode->next << "->]"; cout << " NAME : " << tmpUser->name << "\n"; } } } } }; int _tmain(int argc, _TCHAR* argv[]) { const int INSERT_SIZE = 5; MyContainer<User> myContainer; Node<User>* newNode[INSERT_SIZE]; // Sample1. CreateNode : INSERT_SIZE 만큼 데이터를 입력 for (int i = 0; i < INSERT_SIZE; i++) { User user; cout << "insert name : "; cin.getline(user.name, 20); cout << "insert email : "; cin.getline(user.email, 40); newNode[i] = myContainer.createNode(&user); } myContainer.printAll(); // Sample2. deleteNode : 2번째 노드를 삭제 myContainer.deleteNode(newNode[1]); myContainer.printAll(); // Sample3. deleteContainer : 전체 노드를 삭제 / 삭제해주지 않아도 소멸시 자동삭제되도록 구현한다. myContainer.deleteContainer(); return 0; }