링크드 리스트(Linked list)

■ 설명

데이터 그리고 링크로 구성된 노드(Node)들이 이어진  형태의 자료구조를 링크드 리스트라고한다. 링크드 리스트는 링크의 구현을 포인터로 하기때문에 삽입/삭제에 대한 리스크가 없다는 특징이있으나 탐색시 최상위 노드인 헤드 노드부터 순회해야 하기 때문에 검색에 대한 리스크가  크다.

■ 구현( 설계 ) 

AddNode( data )
RemoveNode( node )
ClearList( )

GetHeadNode( )
GetLength( )

함수이름에서 직관적으로 보이듯 간단히 노드를 추가하고 삭제하고 헤드노드를 얻을수있는 더블링크드 리스트를 만들어보자. 

■ 구현( 헤더 )

[DLNode.h]

Colored By Color Scripter™

#pragma once typedef int DATA; struct DLNode {     DATA data;     DLNode* prevNode;     DLNode* nextNode; };

[DLList.h]

Colored By Color Scripter™

#pragma once #include "DLNode.h" class DLList { private:     enum DEFAULT{ DEFAULT_DATA = 0}; private:     DLNode* headNode = nullptr;     DLNode* curNode = nullptr; private:     DLNode* CreateNode(const DATA& data, DLNode* prev, DLNode* next); public:      void AddNode(const DATA& data);     DLNode* RemoveNode(DLNode* node);     void ClearList(); public:      inline DLNode* GetHeadNode() const { return this->headNode; } private:     DLList(); public:     ~DLList(); public:     static DLList* Create(); };

■ 구현( 코드 )

[DLList.cpp]

Colored By Color Scripter™

#include "DLList.h" DLList * DLList::Create() {     DLList* dlList = new DLList;     dlList->headNode = dlList->CreateNode(DEFAULT_DATA, nullptr, nullptr);     dlList->curNode = dlList->headNode;     return dlList; } DLNode * DLList::CreateNode(const DATA & data, DLNode * prev, DLNode * next) {     DLNode* dlNode = new DLNode;     dlNode->data = data;     dlNode->prevNode = prev;     dlNode->nextNode = next;     return dlNode; } void DLList::AddNode(const DATA & data) {     this->curNode->nextNode = CreateNode(data, this->curNode, nullptr);     this->curNode = this->curNode->nextNode; } DLNode* DLList::RemoveNode(DLNode * node) {     if (!node)         return nullptr;     if(node->prevNode)         node->prevNode->nextNode = node->nextNode;     if (node->nextNode)         node->nextNode->prevNode = node->prevNode;          DLNode* nextNode = node->nextNode;     delete node;     return nextNode; } void DLList::ClearList() {     DLNode* node = this->headNode;     while (node)     {         node = RemoveNode(node);     }     this->headNode = nullptr;     this->curNode = nullptr; } DLList::DLList() { } DLList::~DLList() { }

■ 실행

[Main.cpp]

Colored By Color Scripter™

#include <iostream> #include "DLList.h" using namespace std; int main() {     DLList* dlList = DLList::Create();     dlList->AddNode(10);     dlList->AddNode(20);     dlList->AddNode(30);     dlList->AddNode(40);     dlList->AddNode(50);     DLNode* node = dlList->GetHeadNode()->nextNode;     for (int nodeNum = 0; node; ++nodeNum)     {         cout << "Node(" << nodeNum << ") data : " << node->data <<" "<<endl;         node = node->nextNode;     }     dlList->ClearList();     delete dlList;     dlList = nullptr;     return 0; }

■ 소스코드
Downloding_DoubleLinkedList_vs2015_project