4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현

이중 연결 리스트란 ?

 

여기서 연결 리스트에 대한 개념을 알게 되었고 

여기서 단순 연결 리스트를 구현해보았다.

 

또, 앞선 포스팅에서 연결에 대한 방법을 말했는데 '이중 연결 리스트' 는 양방향(이중)으로 구성된 자료구조이다.

즉, 싱글 연결 리스트는 코스 여행이라면 이중 연결 리스트는 자유 여행이다.

이에 대해선 내가 생각한 예시이기 때문에 한 번 생각해보고 비슷한 예시를 찾아서 본인만의 개념으로 이해하길..

 

이번 STL 따라잡기 포스트는 standard library인 list를 만들어보겠다.

먼저, list에 어떤 기능이 있는지 한 번 알아보자.

 

우리는 STL list에 어떤 기능이 구현되어있는지 파악한 뒤에 이를 정리할 것이다.

깃허브 이슈에 구현할 내용을 작성하고 이를 바탕으로 레파지토리에 저장할 것이다.

list의 모든 기능을 구현하지는 않고 '이중 연결 리스트'의 핵심 기능과 추가하고 싶은 작업에 대해 수행할 것이다.

 

깃허브 Double Linked List 구현할 기능 목록 정리

---

이중 연결 리스트의 데이터를 가질 노드 만들기 DoubleLinkedList.h

 

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

 

우리가 가질 내용은 코드에 작성된 그대로이다.

각 노드는 데이터와 연결될 데이터를 연결할 선을 만들어야 한다.

data - 값, next - 다음 노드, prev - 이전 노드

 

해당 portotype에 대한 작성법은 생략하겠습니다.

한 번, 직접 구현해보고 모르겠으면 제 깃허브에서 정답을 보는 것을 추천합니다.

※ 알면 좋은 개념

1. const keyword

get 메서드에 대해 자세히 보자. 맨 끝에 const가 달려있다.

변수를 선언하기 전에 const 변수명 = 값; 을 취하면 해당 변수는 수정할 수 없는 '상수'가 된다.

즉, const는 정보의 무결성(변하지 않는 성질)을 지켜주는 키워드입니다.

해당 메서드는 우리가 사용하는 멤버 변수인 data와 next, prev에 대해 무결성을 보장해줍니다.

내부에서 수정되어 이상한 값이 전달되는 것을 막아주죠.

 

2. private access modifier

우리는 멤버 변수에 대해 외부에서 접근할 수 없도록 캡슐화(encapsulate)를 했습니다.

정보은닉을 통해 데이터의 무결성, 신뢰성을 보장합니다.

 

노드를 만들었으면 해당 노드로 이중 연결 리스트를 생성하기 DoublyLinkedList.h

#pragma once
#include "DoublyLinkedListNode.h"

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

	// 반복자 
    class iterator {
    public:
        iterator(Node<T>* node, bool& isReverse);

        T operator*() const;
        iterator& operator++(int);
        iterator& operator--(int);
        bool operator!=(const iterator& other) const;

    private:
        Node<T>* it;
        bool isReverse;
        
        Node<T>* getNode();
        friend class DoublyLinkedList<T>;
    };
    
    // Function
	iterator begin();
    iterator end();
	iterator rbegin();
	iterator rend();
	iterator erase(iterator it);

    void push_front(const T& value);
    void push_back(const T& value);
    void pop_front();
    void pop_back();
    void insert(iterator it, const T& value);
    void reverse();
    
    T front() const;
    T back() const;

    int getSize() const;

private:
    Node<T>* head;
    Node<T>* tail;
    int size;
    bool isReverse;
    //void insert_reverse(iterator it, const T& value);
};

 

깃 이슈에 작성한대로 먼저, 구현할 목록을 생성했습니다.

각 기능에 대해서는 몇 몇 부분만 작성하려고 합니다.

남은 부분은 각자 작성해보고 모르겠으면 제 깃허브에서 확인하시면 되겠습니다.

깃 허브 링크는 제일 하단에 공개하겠습니다.

 

※ 알면 좋은 개념

1. head와 tail

이중 연결 리스트는 시작 노드와 끝 노드로 구성되어 있으며 시작노드 부터 끝 노드까지 연결되어있다..

단일 연결 리스트에서는 단방향으로만 탐색을 진행할 수 있었지만,

이중 연결 리스트에서는 양방향으로 탐색을 진행할 수 있으므로 tail부터 head까지도 탐색을 진행할 수 있다.

 

2. iterator 내부 클래스

우리가 STL을 사용하다보면 아래와 같은 코드를 접해본 적이 있을 것이다.

list<int> lis;

lis.push_back(1);
lis.push_back(2);
lis.push_back(3);

// 요기 요기 잘보세연
for(auto it = lis.begin(); it != lis.end(); it++) {  
	cout << *it << ' ';
}

it이라고 하면 무언가를 지칭하는 it이 아니다.

iterator의 약자이며 auto로 자동 캐스팅되는 저 부분은 사실 'list<int>::iterator' 가 들어가는 것이 옳다.

여기서 '::' 는 namespace에 접근하는 개념으로 list 내부에 iterator라는 내부 클래스가 존재하는 것이다.

그럼 우리는 이 iterator를 구현하기 위해서 내부 클래스를 생성해야 한다.

 

최종적으로 DoublyLinkedList<int>::iterator 로 데이터에 대한 '반복자'를 얻을 수 있다.

 

3. operator keyword

operator 키워드는 우리가 사용하는 +=, ++, * 와 같은 연산기호를 의미한다.

우리는 클래스에서 연산기호에 대해서도 직접 수정할 수 있다.

그 중 operator++(int) 에 대해 알아야한다. 딱 보면 후위 연산을 사용하는 것 같은데 int가 작성되어있다.

 

실제로 operator++(int)는 후위연산을 작성하는게 맞고, 전위 연산은 ++operator가 아니라

operator++() 이기 때문에 이를 구분하기 위해 int를 작성했습니다.

 

operator 키워드로 연산기호를 재조정하겠다는 뜻이 되어야하는데 ++이라는 키워드가 먼저 나오면 연산을 하려고 하겠죠? 연산을 수행한 뒤 operator 키워드에 접근해봤자 심볼에러가 발생할 것 입니다.

 

4. isReverse 변수

SLT list를 사용해보신 분들 공감하실 것 같은데 iterator를 가져오고 reverse를 하면 어떻게 되지?

	list<int> l;
	l.push_back(1); // null <- 1 -> null
	l.push_back(2); // null <- 1 <-> 2 -> null
	l.push_back(3); // null <- 1 <-> 2 <-> 3 -> null
	
	auto it = l.begin(); // null <- 1(it) <-> 2 <-> 3 -> null
    l.reverse(); // null <- 3 <-> 2 <-> 1(it) -> null

1. 맨 앞에서 가져온 정보를 reverse 하게 된다면 해당 iterator는 맨 마지막을 가르키는지?

2. 여전히 맨 앞에 녀석을 가르키는지?

3. 맨 마지막을 가르킨다고 하더라도 ++ 연산을 하면 null로 이동하는지? 2로 이동하는지?

궁금한 내용 아닌가요??

 

저는 reverse()를 하기전의 iterator는 내부 클래스 이름을 iterator로 사용하고

reverse에 관한건 iterator2나 reverseIterator 처럼 reverse 전, 후의 iterator들을 관리하는 클래스가 따로 있을 것이라고 생각했습니다. 그래서 list에서 직접 테스트 해봤습니다.

list<int> l = {1, 2, 3};

list<int>::iterator it = l.begin(); // 1을 가르킴
it++; // 문제 없음 2를 가르킴

l.reverse();
cout << *it; // 여전히 2를 가르킴
// 여기서 it은 데이터 그 자체에 대한 정보를 계속 가지고 있음을 앎

cout << *(++it); // 1을 가르킴 !!!
// reverse 전에 뽑은 iter임.
// 하지만 ++ 연산을 하니 reverse 결과가 적용 됨
// reverse를 하지 않았다면 원래 3을 가르켜야 함!!!

// 여기서 it도 reverse가 되는구나를 알게 됨.
// 의문, 그럼 reverse 전, 후의 내부 클래스 iterator가 같은가?

list<int>::iterator reverseIt = it.begin(); // 3을 가르킴
// reverse 되었음에도 같은 iterator를 반환함.

다음과 같은 정보로 같은 iterator를 통해서 reverse 되었는지 내부적으로 통신하고 있다고 생각했습니다.

그래서 생성자에 대한 매개변수로 주소값을 전달해주고 isReverse 값에 따라 reverse된 결과를 줘야겠다! 라는 접근~

 

6. friend access modifier

private으로 설정한 멤버 변수 및 메서드는 외부에서 접근할 수 없습니다.

freind 접근제한자를 사용하면 친구로 인정하고 내부 정보에 접근할 수 있도록 해줍니다.

상속 개념에서 사용되는 protected와는 다릅니다.

 

해당 API에는 erase 메서드를 구현하기 위해서라면 friend 접근제한자가 필요하다고 생각해서 추가했습니다.

(사실 만들다보니 friend 없이는 안될 것 같아서 추가함..)

---

 

iterator 구현

template <typename T>
DoublyLinkedList<T>::iterator::iterator(Node<T>* node, bool& isReverse) : it(node), isReverse(isReverse) {}

template <typename T>
T DoublyLinkedList<T>::iterator::operator*() const {
    return it->getData();
}

template <typename T>
typename DoublyLinkedList<T>::iterator& DoublyLinkedList<T>::iterator::operator++(int) {
    if(isReverse) {
		it = it -> getPrev();
	} else {
		it = it->getNext();	
	}
    return *this;
}

template <typename T>
bool DoublyLinkedList<T>::iterator::operator!=(const iterator& other) const {
    return it != other.it;
}

 

 

생성자, 포인터, 후위연산, 비교연산에 대한 코드이다.

기능 단위로 너무 예쁘게 잘 작성한 것 같아서 ㅎㅎ.. 설명은 생략

 

DoublyLinkedList Method

template <typename T>
DoublyLinkedList<T>::DoublyLinkedList() : head(nullptr), tail(nullptr), size(0), isReverse(false) {}

template <typename T>
typename DoublyLinkedList<T>::iterator DoublyLinkedList<T>::begin() {
	return iterator(head, this -> isReverse);
}

template <typename T>
typename DoublyLinkedList<T>::iterator DoublyLinkedList<T>::end() {
	return iterator(nullptr, this -> isReverse);
}

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

가장 기본적인 기능인 push_back과 탐색을 위한, begin(), end()를 추가해보았다.

 

활용하기

/*
	authored by dot
    https://dev-dot.tistory.com
*/
#include <list>
#include <iostream> 
#include "DoublyLinkedList.h"

using namespace std;

int main() {
	DoublyLinkedList<int> customList;
	
	printf("push_back : 40, 50, 60\n");
	customList.push_back(40);
	customList.push_back(50);
	customList.push_back(60);
	
	printf("push_front : 30, 20, 10\n");
	customList.push_front(30);
	customList.push_front(20);
	customList.push_front(10);
	
	printf("pop_front\n");
	customList.pop_front();

	printf("pop_back\n\n");
	customList.pop_back();
	
	printf("begin() and rbegin() before reverse\n");
	printf("begin val : %d, rbegin val : %d\n", *(customList.begin()), *(customList.rbegin()));
	printf("front() and back() before reverse\n");
	printf("front : %d, back : %d\n", customList.front(), customList.back());
	
	printf("Forward Travel\n");
	for(auto it = customList.begin(); it != customList.end(); it++) {
		cout << *it << ' ';
	}
	cout << "\n\n";
	
	customList.reverse();
	
	printf("begin() and rbegin() after reverse\n");
	printf("begin val : %d, rbegin val : %d\n", *(customList.begin()), *(customList.rbegin()));
	printf("front() and back() before reverse\n");
	printf("front : %d, back : %d\n", customList.front(), customList.back());
	
	printf("Reversed Travel\n");
	for(auto it = customList.begin(); it != customList.end(); it++) {
		cout << *it << ' ';
	}
	cout << "\n\n";

	DoublyLinkedList<int>::iterator it = customList.begin();
	it++;
	printf("value of it : %d\n", *it);
	
	it = customList.erase(it);
	printf("value of it after erase : %d\n", *it);
	
	it = customList.erase(customList.begin());
	printf("value of it after erase front : %d\n", *it);
	
	it++;
	it = customList.erase(it);
	printf("value of it after erase back : %d\n", *it);
	
	printf("Travel after erase\n");
	for(auto it = customList.begin(); it != customList.end(); it++) {
		cout << *it << ' ';
	}
	cout << "\n\n";
	
	customList.insert(it, 20);
	printf("Travel after insert\n");
	for(auto it = customList.begin(); it != customList.end(); it++) {
		cout << *it << ' ';
	}
	cout << "\n\n";
	
	return 0;
}

실행 결과

모든 기능이 작성된 코드는 Github 레파지토리에 push 할 예정입니다.

다른 기능들은 한 번 직접 구현해보시는걸 추천드립니다.

 

아! 그리고 혹시 이글을 보시는 분들 중 Readme.md를 꾸며주시거나...

부족한 메서드를 채워서 PR 해주시면 정말 감사하겠습니다!!!

 

작성해보면 도움이 되는 Method

 

reverse, erase, push_front 는 필수로 해보시면 좋겠습니다.

erase의 경우 주의해야 할 점이 많습니다!

 

깃허브 이슈 및 레파지토리, 레퍼런스

 

깃허브 이슈 : https://github.com/jihwankim128/datastructure/issues/4

이중 연결 리스트 (Doubly Linked List) · Issue #4 · jihwankim128/datastructure

 

깃허브 레파지토리 : https://github.com/jihwankim128/datastructure

GitHub - jihwankim128/datastructure

 

레퍼런스 : https://cplusplus.com/reference/list/list/insert/

https://cplusplus.com/reference/list/list/insert/