5. 원형 연결 리스트 (Circular Linked List)

원형 연결 리스트란?

 

단순 연결 리스트에서 끝이 처음과 연결되어 있는 형태를 원형 연결 리스트라고 합니다.

 

STL에도 구현되어있지 않고 아직 학생 수준이지만, 실제로 사용되는 경우도 본 적이 많이 없습니다.

그래서 단순하게만 만들어보도록 할 것인데, 이중 연결 리스트 형태로 만들려고 합니다.

(실제로 순환적인 요소는 큐 또는 재귀를 많이 사용하는듯)

---

원형 연결 리스트(Circular Linked List) 구현하기 

 

많은 기능을 추가하지는 않겠습니다.

노드

#pragma once

template <typename T>
class Node {
public:
    Node(T data);
    
    T getData() const;
    Node* getNext() const;
    Node* getPrev() const;

    void setNext(Node* node);
    void setPrev(Node* node);

private:
    T data;
    Node* next;
    Node* prev;
};

template <typename T>
Node<T>::Node(T data) : data(data), next(nullptr), prev(nullptr) {}

template <typename T>
T Node<T>::getData() const {
    return data;
}

template <typename T>
Node<T>* Node<T>::getNext() const {
    return next;
}

template <typename T>
Node<T>* Node<T>::getPrev() const {
    return prev;
}

template <typename T>
void Node<T>::setNext(Node* node) {
    next = node;
}

template <typename T>
void Node<T>::setPrev(Node* node) {
    prev = node;
}

 

원형 연결 리스트의 노드는 단순 연결 리스트 구조일 경우 단순 연결 리스트 포스트에서 사용된 노드를 사용하면 됩니다.

현재는 이중 연결 리스트 구조에서 원형 연결 리스트를 개발하기로 설계했습니다.

 

원형 연결 리스트 클래스

#pragma once
#include "CircularLinkedListNode.h"
#include <iostream>

// Prototype
template <typename T>
class CircularLinkedList {
public:
    CircularLinkedList();

    void push_front(const T& value);
    void push_back(const T& value);
    void pop_front();
    void pop_back();
    void travel();

private:
    Node<T>* head;
    Node<T>* tail;
};

template <typename T>
CircularLinkedList<T>::CircularLinkedList() : head(nullptr), tail(nullptr) {}

template <typename T>
void CircularLinkedList<T>::push_front(const T& value) {
	Node<T>* newNode = new Node<T>(value);
	if (head == nullptr) {
		head = newNode;
		tail = newNode;
		head -> setNext(newNode);
		head -> setPrev(newNode);
		tail -> setNext(newNode);
		tail -> setPrev(newNode);
	} else {
		head -> setPrev(newNode);
		tail -> setNext(newNode);
		newNode -> setNext(head);
		newNode -> setPrev(tail);
		head = newNode;
	}
}

template <typename T>
void CircularLinkedList<T>::push_back(const T& value) {
	if (head == nullptr) {
		push_front(value);
	} else {
		Node<T>* newNode = new Node<T>(value);
		head -> setPrev(newNode);
		tail -> setNext(newNode);
		newNode -> setNext(head);
		newNode -> setPrev(tail);
		tail = newNode;
	}
}

template <typename T>
void CircularLinkedList<T>::pop_front() {
	if(head == tail) {
		delete head;
		delete tail;
		head == nullptr;
		tail == nullptr;
	} else {
		Node<T>* newHead = head -> getNext();
		tail -> setNext(newHead);
		newHead -> setPrev(newHead);
		delete head; 
		head = newHead;
	}
}

template <typename T>
void CircularLinkedList<T>::pop_back() {
	if(head == tail) {
		delete head;
		delete tail;
		head == nullptr;
		tail == nullptr;
	} else {
		Node<T>* newTail = tail -> getPrev();
		newTail -> setNext(head);
		head -> setPrev(newTail);
		delete tail; 
		tail = newTail;
	}
}

template <typename T>
void CircularLinkedList<T>::travel() {
	Node<T>* temp = head;
	do {
		std::cout << (temp -> getData()) << ' ';
		temp = temp -> getNext();
	}
	while (temp != head);
	std::cout << '\n';
}

 

이중 연결 리스트에서 iterator를 제거하고 간단하게만 작성했습니다.

맨 앞 뒤에 추가/삭제 하는 연산과 모든 원소를 탐색하는 과정만 작성했습니다.

 

※ 추가 연산 시 주의해야 할 점.

만약, 처음으로 추가하는 경우 리스트는 비어있습니다.

이 때, 원형 연결리스트에서 첫 원소는 본인 스스로를 가르키게 되어있습니다.

원소가 뒤에 추가 되는 경우, 새로 추가되는 원소를 Now(현재 원소)라고 하겠습니다.

1. Tail(마지막 원소)의 다음 값으로 Now가 와야하고 Head(첫 원소)의 이전 값으로 Now가 와야합니다.

2. Now의 다음 원소는 Tail이 되어야하고 Now의 이전 원소는 Head가 되어야 합니다.

 

원소가 앞에 추가 되는 경우는 반대 케이스라서 설명하지 않겠습니다.

 

원소가 삭제되는 경우는, 원소가 하나만 있을 경우 head와 tail이 같은 경우 (주소 값을 기준으로 비교할 수 있음)

1. 이 때, head와 tail에 할당된 메모리를 삭제하여 메모리 누수를 방지하고 모두 null값으로 바꾸어야 합니다.

맨 뒤 데이터가 삭제가 되는 경우

1. Prev(Tail의 이전 값)가 Tail이 되어야합니다.

2. Prev의 다음 값을 Next(Tail의 다음 값)으로 설정합니다.

3. Next의 이전 값을 Prev로 설정합니다.

4. 기존의 Tail에 할당된 메모리를 해제해주고 Prev를 Tail로 정의합니다.

 

앞의 원소가 삭제되는 경우도 반대 케이스라서 설명하지 않겠습니다.

 

마지막으로 탐색하는 경우입니다.

(head == tail) != null 이므로 do에서 먼저 출력한 뒤 while문에서 조건 검사를 해야합니다.

 

실행

#include <iostream>
#include "CircularLinkedList.h"

using namespace std;

int main() {
	CircularLinkedList<int> customList;
	
	cout << "===== push_back & travel =====\n";
	for (int i = 10; i <= 50; i += 10) {
		customList.push_back(i);
	}
	customList.travel();
	
	cout << "\n===== push_front & travel =====\n";
	for (int i = 1; i <= 5; i++) {
		customList.push_front(i);
	}
	customList.travel();
	
	cout << "\npop_front & pop_back & travel \n";
	customList.pop_front();
	customList.pop_back();
	customList.travel();
	
	return 0;
}

 

결과

 

GitHub 링크 URL

https://github.com/jihwankim128/datastructure

GitHub - jihwankim128/datastructure