[C++] 나만의 DoubleLinkedList(이중연결리스트)만들기 (2) - 생성자, 데이터추가

연결리스트는 여러개의 노드로 구성되어 있기 때문에 노드 구조체를 먼저 만들어보자

	//template <typename Data>
    struct Node
	{
		Data data = NULL;
		Node* next = nullptr;
		Node* prev = nullptr;
	};

노드는 대단한건 없고, 데이터를 저장하기위한 변수와, 앞 뒤 노드를 가리키는 변수2개가 필요하다.

처음 프로그래밍을 공부할 때 이해가 어려웠던 부분이

 

Node구조체안에 왜 똑같은 노드가 2개가있지? 그리고 왜 포인터지?

노드는 노드를 가리켜야 하니까 저렇게 한건 알겠는데 논리적으로 이해를 못하니까 두루뭉술하게 이해했고,

왜 포인터로 저장하는지도 이해를 못했다.

 

노드 구조체안에 노드변수를 가져야하는것은 구현하면 알게되니 넘어가고

포인터로 저장하는 이유는 노드를 '복사'해서 가지지 않으려고 그런것이다.

call by value, call by address, call by reference라는 개념이 있는데 

여기서 이것까지 설명하면 길어지기 때문에 이 부분은 넘어가고 여기선 일단

노드구조체안의 노드변수는 앞 뒤 노드의 정보를 원본으로 가지고 있어야하기 때문이라고 이해하자

---

	MyLinkedList()
	{
		head = new Node;
		tail = new Node;

		head->next = tail;
		tail->prev = head;
	}
	~MyLinkedList()
	{
		//모든 노드 삭제
		RemoveAll();

		delete head;
		delete tail;
	}

	Node* head = nullptr;
	Node* tail = nullptr;
	size_t size = 0;

생성자에선 헤드와 테일을 미리 생성하고 서로 연결시켜 놓습니다.

소멸자에선 모든 데이터를 제거및해제 하고, 헤드와 테일도 해제합니다. 항상 포인터같은 할당된 변수는 꼭 해제를 해야합니다.

RemoveAll()은 다음 포스팅에서 나옵니다

 

내가 구현한 이중연결리스트는 헤드와 테일에 데이터가 없습니다

---

	//데이터를 추가합니다
	void AddFront(const Data& data)
	{
		Add(head->next, data);
	}
	void AddBack(const Data& data)
	{
		Add(tail, data);
	}
    
    private:
	void Add(Node* nd_next, const Data& data)
	{
		//노드를 새로생성합니다
		Node* nd = new Node;
		nd->data = data;

		//생성한 노드의 앞, 뒤 노드를 연결합니다.
		nd->next = nd_next;
		nd->prev = nd_next->prev;

		//앞, 뒤 노드도 생성한 노드에 연결합니다
		nd_next->prev->next = nd;
		nd_next->prev = nd;

		++size;
	}

AddFront(), AddBack()은 앞 혹은 뒤에 데이터를 추가하겠는 함수고 실제 로직은 Add()에 들어있다.

Add()를 보면 생성된 노드와 앞,뒤의 노드를 연결하는 부분이 헷갈릴수 있다.

하지만 하나씩 하나씩 나눠서 보면 이해가 될것이다.

그래도 이해가 안되면 직접 그려보자.

 

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer