DoubleLinkedList

예전 자료구조 시간에 했던 과제들을 복기하며 다시 자료구조와 알고리즘에 대한 이해를 남겨보기로 했다. 

 

그 중 자료구조에서는 Double Linked List라는 구조가 존재한다. 

 

Double Linked List란 양방향으로 연결 되어 있는 리스트로써 각 노드들이 양 방향으로 이어지는 구조를 가진다. 

그러면 우리는 이 구조에서 몇 가지의 데이터를 신경써야할까

내가 프로그래밍을 하면서 느낀 점은 프로그래밍은 결국 데이터의 관리, 엔터티의 속성의 관리를 하는 일이다. 

노드들이 양방향으로 연결되어 있으니 우리는 우선 노드라는 타입을 만들어야한다. 

#ifndef DLINKEDLIST_H
#define DLINKEDLiST_H
#include <iostream>

using namespace std; // 12171800 심정호
typedef string Elem; // string 클래스를 Elem으로 부르겠다.
class DNode {//list의 노드가 될 클래스를 설정한다. 
private:
	Elem elem;//string elem;
	DNode* prev; //이전노드
	DNode* next; // 다음 노드
	friend class DLinkedList; // DNode 클래스를 DLinkedList의 friend 클래스로 설정하여 DNode클래스의 private 변수를 DLinkedlist 클래스에서 사용할 수 있게 한다. 
};

각 노드는 무슨 정보를 담고 있어야하는가?

우리는 양방향 연결 리스트를 만들고 있기 때문에 각 노드는 나의 이전 노드, 나의 이 후 노드에 대한 정보를 가지고 있어야한다. 위에서 보면 이 정보를 prev next 포인터로 관리하고 있음을 알 수 있다. 

class DLinkedList { //doublelinked list를 구현한다.
public:
	DLinkedList();//생성자
	~DLinkedList();//소멸자
	bool empty() const;//list가 비어있는 지 판별
	const Elem& front() const;// 리스트의 가장 앞
	const Elem& back() const; // 리스트의 가장 뒤
	void addFront(const Elem& e); // 앞에다가 원소를 추가
	void addBack(const Elem& e); // 뒤에다가 원소를 추가
	void removeFront(); // 앞에 있는 원소를 제거
	void removeBack(); // 뒤에 있는 원소를 제거
private:
	DNode* header; //가장 앞에 위치하는 header
	DNode* trailer; // 가장 뒤에 위치하는 trailer
protected:
	void add(DNode* v, const Elem& e); 
	void remove(DNode* v);

};

DLinkedList의 class이다. 

리스트를 구성하는 기능은 다음과 같다. 

1. 리스트가 비어있는가? 를 판단하는 기능

2. 리스트의 가장 앞인가? 를 판단하는 기능

3. 리스트의 가장 뒤인가?를 판단하는 기능

4. 어떤 노드의 앞이나 뒤에 노드를 추가하는 기능

5. 어떤 노드의 앞이나 뒤에 위치하는 노드를 지우는 기능 

 

1. DLINKEDLIST의 생성자가 처음에 불리면 생성자는 처음에 header와 trailer라는 리스트의 처음과 끝을 담당하는 노드들을 만든다. 그 후 둘을 연결해준다. 연결을 해주면 순서가 생기는 것이다. 

 

DLinkedList::DLinkedList() // DLinkedList의 생성자
{
	header = new DNode; // 리스트를 만들기 위해 header를 만든다.
	trailer = new DNode; // 리스트를 만들기 위해 trailer를 만든다.
	header->next = trailer; // 초기 리스트에서 header와 trailer를 각각 연결한다.
	trailer->prev = header; 
	cout << "DLinkedList 생성자" << endl;
}

 

2. DlinkedList가 비어있는지를 판단하는 기능은 간단하다. 처음 생성자에서 생성했듯이 header의 next가 trailer이거나 trailer의 prev가 header이면 이 리스트는 비어있는 것이다. 

bool DLinkedList::empty() const // 리스트가 비어있는 지를 확인하는 함수 12171800 심정호
{ 
	return (header->next == trailer); // 생성자에서 설정한 그대로 header와 trailer가 연결 되어 있으면 empty이다.
}

3. DlinkedList의 가장 앞이나 뒤를 판단하는 것 또한 생성자에서 생성한 header와 trailer를 이용한다. 

header의 next는 가장 앞 trailer의 prev는 가장 뒤의 노드를 의미한다. 

const Elem& DLinkedList::front() const // 가장 앞에 있는 노드를 리턴한다.
{
	return header->next->elem;
}
const Elem& DLinkedList::back() const // 가장 뒤에 있는 노드를 리턴한다.
{
	return trailer->prev->elem;
}

4. 노드를 추가하는 기능이다. add함수는 새로운 노드의 위치를 받아 정보를 저장한다. 앞서 Elem은 string을 다르게 부르기로 한 말이었다. 

void DLinkedList::add(DNode* v, const Elem& e) // DLinkedList에 새로운 노드를 추가한다. 심정호
{
	DNode* u = new DNode; u->elem = e;
	u->next = v; //추가되는 노드의 다음노드를 기존노드에 연결한다.
	u->prev = v->prev; // 추가되는 노드의 이 전 노드를 기존 노드의 이 전 노드로 연결한다.
	v->prev->next = u; // 기존 노드의 이전노드의 다음노드를 새로운 노드에 연결한다.
	v->prev = u; // 기존 노드의 이전 노드를 새로운 노드로 연결한다. 
}

void DLinkedList::addFront(const Elem& e) // 리스트의 앞에 새로운 노드를 연결한다. 
{
	add(header->next, e);  //header->next노드 앞에 새로운 노드를 추가한다.
}
void DLinkedList::addBack(const Elem& e) // 리스트의 뒤에 새로운 노드를 연결한다.
{
	add(trailer, e); // trailer 앞에 새로운 노드를 추가한다.
}
DLinkedList::~DLinkedList() { // DLinkedList의 소멸자
	while (!empty()) // 리스트가 빌 때까지 
		removeFront(); // 앞에서부터 원소를 지운다.
	delete header; // header와 trailer를 지운다.
	delete trailer;
	cout << "DLinkedList 소멸자" << endl;
}

5. 노드를 삭제하는 기능이다. 연결을 끊어주고  delete를 통해 메모리 또한 없애주어야한다. 

void DLinkedList::remove(DNode* v) // 노드를 지우기
{
	DNode* u = v->prev; // 기존 노드의 이전 노드를 u로 설정한다.
	DNode* w = v->next; // 기존 노드의 다음 노드를 w로 설정한다.
 	u->next = w; // 기존 노드의 이전 노드를 기존 노드의 다음 노드와 연결한다.
	w->prev = u; // 기존 노드의 다음 노드를 기존 노드의 이전 노드와 연결한다.
	delete v; // 기존 노드를 지운다.
}
void DLinkedList::removeFront() // 앞에 있는 노드를 지운다.
{
	remove(header->next); // 가장 앞에 있는 노드를 지운다.
}
void DLinkedList::removeBack() // 가장 뒤에 있는 노드를 지운다.
{
	remove(trailer->prev); // trailer앞에 있는 노드를 지운다.
}