태그 글목록: doubly linked list

[Data Structure] 연결리스트(Linked List)의 구현 2015-06-19

상황에 맞게 최적의 성능을 내고 싶을 경우 연결리스트를 직접 구현해 사용하기도 한다. 원형 이중 연결리스트를 C++로 구현해 보았다. 노드가 어디에 추가되건 편리하게 사용할 수 있는 장점이 있다. 선형의 경우도 아래 소스를 참고하여 손쉽게 구현할 수 있다.

circulardoublylinkedlist

#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;
}

[C++ 정리] 배열(Array)과 연결리스트(Linked List) 2015-06-18

배열 : 정해진 크기만큼만 선언을 할 수 있다. 이는 연결된 메모리를 보장해준다. 하지만 이는 유연하게 프로그래밍을 하는데는 제약이 있다.

array
장점

* 구현이 간단하다.
* 연결된 메모리상에 존재하므로 중간 데이터에 빠르게 접근할 수 있다. 
  ex> array[3] 으로 'D'에 접근할 수 있다.

단점

* 크기를 고정해야 하기 때문에 사용될 것을 고려하여 할당해야 하고 이는 불필요한 메모리를 차지한다.
* 중간 데이터의 삽입 또는 삭제가 일어난다면 뒤에 데이터를 전부 변경해야만(메모리상에서 한칸씩 밀거나 당긴다) 하기 때문에 비효율적이다.

연결리스트 : 크기에 대한 제약없어 유연하게 활용할 수 있지만 연결된 메모리가 아니기 때문에 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.

linkedlist
장점

* 필요할때마다 메모리를 동적으로 할당하기 때문에 메모리 효율적이다.
* 중간에 데이터를 삽입 또는 삭제 하더라도 다른 데이터에 영향을 주지 않아 효율적이다.
  Ex> 'D'를 삭제하려면 'C'에서의 링크를 'E'로 변경만 하면 된다.

단점

* 구현이 복잡하다.
* 중간의 데이터에 접근하기 위해서는 이전 노드를 모두 거쳐야만 접근할 수 있다.
  Ex> 'D'에 접근하려면 'B', 'C'를 거쳐야만 한다.

연결리스트의 종류

> 단일 연결 리스트(Singly Linked List)

singlylinkedlist

typedef struct node
{
    struct node* next;
    void* data;
}Node;
* 노드가 다음노드를 가리킨다.
> 이중 연결 리스트(Doubly Linked List)

doublylinkedlist

typedef struct node
{
    struct node* prev;
    struct node* next;
    void* data;
}Node;
* 각 노드들이 이전과 다음노드를 가리킨다.
> 다중 연결 리스트(Multiply Linked List)

multiplylinkedlist

typedef struct node
{
    vector<struct node *> pointers;
    void* data;
}Node;
* 각 노드가 2개이상의 노드를 가리킨다.
> 원형 연결 리스트(Circular Linked List)

circularlinkedlist

* 리스트의 마지막 노드가 멀리있는 다른 노드(보통 첫번째 노드)를 가리키고 있는 형태이다.
* 원형 이중 연결 리스트(circular doubly linked list)의 경우는 첫번째 노드의 prev는 마지막 노드를, 마지막 노드의 next는 첫번째 노드를 가리킨다.

<링크 : 위키문서(Linked list)> 참조