1. 개요
이번에 정리할 내용은 바로 Circular Doubled Linked List(원형 이중 연결 리스트) 이다. 드디어 객체지향 언어를 사용할 수 있게 되었다 ㅠㅠ 사실 OOP(객체 지향저) 적인 코드를 작성하는 회사에서는 이 OOP를 디자인하는 시간이 몇달이 걸린다고도 한다. 저번 글과 현재 작성하고 있는 글에 차이가 있다면 일주일동안 들은 객체지향 특강에서 배운 지식을 활용했다는 것이다. LinkedList를 C++로 작성하려고 해도 시도하지 못했지만, 이제는 C로 작성된 원형 이중 연결 리스트의 이론과 코드를 참고하여 C++로 구현하였다. 나름 뿌듯함을 느끼는 중이다.
2. 이론
사실 원형이중연결 리스트의 기능은 연결리스트와는 다르지 않다. 다만, 차이가 있다면 마지막을 찾는 연산을 하지 않아도 된다는 것이다. 사실, 연결 리스트 → 원형연결리스트 → 이중연결리스트 →원형이중연결리스트 순으로 공부하는 것이 이해에 편하지만 이 블로그에는 이중연결리스트와 원형연결리스트에 대한 설명이 없으니 다른 자료를 찾아보고 오는 것도 좋을 것 같다(아주 간단한 설명만하고 구현은 하지 않는다 ㅠㅠ).
원형이중연결리스트를 글로 먼저 이해하는 것보다는 그림으로 보는것이 훨씬 좋다고 생각한다. 다음은 원형 이중 연결 리스트의 그림이다.
그림을 보면 앞에서 설명한 "마지막을 찾는 연산을 하지 않아도 된다." 라는 말을 어느정도 이해할 수 있을 것 같다. 왜냐하면 첫 노드의 왼쪽 링크가 바로 마지막 노드이기 때문이다. 때문에 일방적인 방향으로만 연결된 링크리스트보다는 이중연결리스트가 앞 노드를 찾는 연산이나, 마지막 노드를 찾는 연산을 수행할 때, 계산자원을 훨씬 아낄수도 있을 것 같다. 원형 이중 연결 리스트의 기능은 다음과 같다.
- 노드추가
- 노드탐색
- 노드삭제
이제 하나씩 다음의 기능들을 구현할 것이다. 구조체와 클래스 헤더는 다음과 같이 구현하였다.
- 구조체와 Class헤더
#pragma once
#include <cstdio>
typedef struct Node {
int data;
Node *lLink;
Node * rLink;
} Node, *NodePtr;
class DoubledLinkedList
{
private:
NodePtr head;
NodePtr tail;
public:
DoubledLinkedList();
~DoubledLinkedList();
NodePtr getHead() { return head; }
NodePtr getTaile() { return tail; }
NodePtr searchNode(int n);
bool insertNode(int n);
bool deleteNode(int n);
void printList();
void resetList();
};
구조체를 Class안에서 선언하고 싶었지만, 매소드 중에 해당 구조체 포인터를 반환하는 메소드를 정의할 때 에러가 발생하여 Class 밖에서 정의하였다. 이는 따로 자세히 조사하여 다른 글로 설명할 것이다.
- 노드 추가
원형 이중 연결 리스트는 연결리스트보다는 링크를 조작할 때, 신경을 조금 더 써야한다. 일단 링크가 두개이니 말이다. 내가 구현한 기능은 가장 마지막부분에 노드를 추가하는 기능이다. 다음은 마지막에 노드를 추가하는 그림이다.
그림을 보면 알겠지만, head노드의 rLink와 tail의 조작이 중요하다는 것을 알 수 있다. 다음은 코드이다.
bool DoubledLinkedList::insertNode(int n) {
NodePtr pNew = new Node;
if (pNew) {
pNew->data = n;
if (head || tail) {
tail->rLink = pNew;
pNew->lLink = tail;
pNew->rLink = head;
head->lLink = tail = pNew;
}
else {
pNew->rLink = pNew->lLink = pNew;
head = tail = pNew;
}
return true;
}
return false;
}
- 노드 탐색
다음은 노드 탐색이다. 노드 탐색과 같은 경우, 정수를 입력받으면 그 정수를 가지고있는 가장 앞쪽의 노드를 반환하는 방식으로 작성하였다. while문을 사용하면 다음과 같이 간단하게 구현할 수 있다.
NodePtr DoubledLinkedList::searchNode(int n) {
if (head || tail) {
NodePtr search = head->rLink;
while (search->data != n && search != head)
search = search->rLink;
if (head->data == n || search->data == n)
return search;
else
return nullptr;
}
else
return nullptr;
}
-노드 삭제
노드를 삭제할 때는 생각해야 하는 부분이 많다. 일단 리스트에 노드가 하나만 있을 경우와, 아무것도 없을 경우를 생각해야한다. 그 다음은 링크를 조작해야하는데, 나같은 경우는 편리함을 위해 head포인터와 tail포인터를 미리 조작하고, 나머지 링크를 조작하는 방식을 사용하였다.(이것이 정답은 아닙니다.) 다음은 노드 삭제에 대한 그림이다.
그림을 보면 lNode라는 포인터와 rNode라는 포인터를 미리 지정하여 그 포인터들을 가지고 링크를 조작하는 것을 알 수 있다. 이렇게 안하는 사람도 있고 하는 사람도 많지만, 정답은 없다고 생각한다. 자신이 편한 방법을 선택하면 될 것이다. 다음은 코드이다.
bool DoubledLinkedList::deleteNode(int n) {
NodePtr pDel = searchNode(n);
if (pDel) {
if (pDel == head && pDel == tail)
head = tail = nullptr;
else {
if (pDel == head)
head = pDel->rLink;
else if (pDel == tail)
tail = pDel->lLink;
NodePtr rNode = pDel->rLink;
NodePtr lNode = pDel->lLink;
rNode->lLink = lNode;
lNode->rLink = rNode;
}
delete pDel;
}
else
return false;
}
다음은 클래스에 대한 헤더와 메소드 정의 코드이며, 마지막 코드는 이 메소드들을 테스트하기위한 main() 함수이다.
- 헤더파일
#pragma once
#include <cstdio>
typedef struct Node {
int data;
Node *lLink;
Node * rLink;
} Node, *NodePtr;
class DoubledLinkedList
{
private:
NodePtr head;
NodePtr tail;
public:
DoubledLinkedList();
~DoubledLinkedList();
NodePtr getHead() { return head; }
NodePtr getTaile() { return tail; }
NodePtr searchNode(int n);
bool insertNode(int n);
bool deleteNode(int n);
void printList();
void resetList();
};
- 메소드 정의 파일
#include "DoubledLinkedList.h"
DoubledLinkedList::DoubledLinkedList()
{
head = tail = nullptr;
}
DoubledLinkedList::~DoubledLinkedList()
{
resetList();
printf("\n리스트가 최기화 되었습니다.\n");
}
bool DoubledLinkedList::insertNode(int n) {
NodePtr pNew = new Node;
if (pNew) {
pNew->data = n;
if (head || tail) {
tail->rLink = pNew;
pNew->lLink = tail;
pNew->rLink = head;
head->lLink = tail = pNew;
}
else {
pNew->rLink = pNew->lLink = pNew;
head = tail = pNew;
}
return true;
}
return false;
}
NodePtr DoubledLinkedList::searchNode(int n) {
if (head || tail) {
NodePtr search = head->rLink;
while (search->data != n && search != head)
search = search->rLink;
if (head->data == n || search->data == n)
return search;
else
return nullptr;
}
else
return nullptr;
}
bool DoubledLinkedList::deleteNode(int n) {
NodePtr pDel = searchNode(n);
if (pDel) {
if (pDel == head && pDel == tail)
head = tail = nullptr;
else {
if (pDel == head)
head = pDel->rLink;
else if (pDel == tail)
tail = pDel->lLink;
NodePtr rNode = pDel->rLink;
NodePtr lNode = pDel->lLink;
rNode->lLink = lNode;
lNode->rLink = rNode;
}
delete pDel;
}
else
return false;
}
void DoubledLinkedList::printList() {
if (head) {
for (NodePtr buff = head; buff != tail; buff = buff->rLink)
printf("%d <--> ", buff->data);
printf("%d", tail->data);
}
else
printf("empty list");
}
void DoubledLinkedList::resetList() {
while (head != nullptr)
deleteNode(tail->data);
}
- main() 함수
#include "DoubledLinkedList.h"
int main(void) {
DoubledLinkedList list;
list.insertNode(20);
list.insertNode(30);
list.insertNode(40);
list.insertNode(50);
list.insertNode(60);
list.printList();
printf("\n");
list.deleteNode(60);
list.deleteNode(20);
list.printList();
return 0;
}
3. 결어
그동안 블로에 글을 작성하는 것이 너무 느려졌다는 생각이 든다 ㅠㅠ. 심지어 백준 알고리즘도 꾸준히 풀고있지 않는다. 지금 부터라도 다시 예전의 나로 돌아갔으면 한다. 다음은 새로운 자료구조를 정리하는 글을 작성할 것이다.
'programming > 자료구조' 카테고리의 다른 글
| [자료구조] - C언어를 활용한 그래프의 구현 (0) | 2021.03.04 |
|---|---|
| [자료구조] - LCRS_TREE 구현 (C++) (0) | 2021.01.11 |
| [자료구조] - LinkedQueue 구현 (C++) (0) | 2020.07.18 |
| [자료구조] - LinkedList의 구현 (C언어) (0) | 2020.06.27 |
| [자료구조] - Stack의 구현( C, C++ ) (0) | 2020.06.05 |
