ForestBird

	//가장 앞, 뒤의 데이터를 삭제합니다
	const bool RemoveFront()
	{
		return Remove(head->next);
	}
	const bool RemoveBack()
	{
		return Remove(tail->prev);
	}

    private:
	//데이터를 찾아서 삭제합니다
	const bool Remove(Node* nd_remove)
	{
		if (size <= 0) return false;

		nd_remove->prev->next = nd_remove->next;
		nd_remove->next->prev = nd_remove->prev;
		delete nd_remove;
		--size;
		return true;
	}

이전 포스팅에서 소개한 AddFront(),AddBack(),Add()와 동일한 구조의 함수다

Remove()는 성공과 실패를 리턴하고, 노드를 삭제하며 삭제된 노드 앞뒤의 노드끼리 연결시킨다

	//원하는 데이터를 찾아서 삭제합니다
	const bool RemoveData(const Data& data)
	{
		if (size <= 0) return false;

		for (Node* nd = head->next; nd != tail; nd = nd->next)
		{
			if (nd->data == data)
			{
				//삭제할 데이터를 찾았습니다. 삭제합니다
				return Remove(nd);
			}
		}

		//삭제할 데이터를 찾지 못했습니다
		return false;
	}

	//모든 데이터를 삭제합니다
	void RemoveAll()
	{
		while (RemoveFront()) {}
	}

RemoveData(): 동일한 데이터를 찾아 삭제.

RemoveAll(): 모든 데이터를 삭제.

RemoveData()에서 노드의 순회을 볼 수 있다.

head->next노드부터 시작해서 tail이 아닌 노드면 계속 순회한다.

역순회도 다르지 않다.

for (Node* nd = tail->prev; nd != head; nd = nd->prev)

논리적으로 거꾸로 돌아가게 하면된다.

프로그래밍 처음 공부했을때 꽤 어려웠던 연결리스트였는데 지금 다시 보니까 구현자체는 어렵지 않았다.

데이터의 삽입,삭제시 노드연결만 신경써주면된다.

https://github.com/ForestBird1/MyContainer

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

	//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

연결리스트는 데이터끼리 순서대로 연결된 형식이다.

벡터(vector)의 경우 메모리의 인접한 순서대로 데이터가 존재하지만,

연결리스트는 각 데이터가 메모리에서 인접하지 않더라도 데이터는 다음 데이터의 위치를 저장하고 있다.

벡터는 데이터를 중간위치에서 삽입,삭제시 데이터가 밀리거나, 땡겨지게 되는 이슈가 있는데,

연결리스트는 메모리가 인접하지 않아도 되기 때문에 삽입,삭제에서 자유롭다.

단점은 벡터는 인덱스로 데이터에 빠르게 접근할 수 있지만, 연결리스트는 꼭! 순차적으로 검색후 데이터에 접근하게 된다. 그래서 검색의 최후방에 있는 데이터는 가장늦게 찾게 된다.

벡터는 중간위치에 삽입,삭제 하려면 인덱스를 알아야 하지만,

연결리스트는 앞 혹은 뒤의 노드를 알아야한다.

여기선 어떻게 데이터끼리 위치를 저장하고있는지 알아봐야한다

1. 단일연결리스트

데이터는 다음데이터의 위치를 저장한다

각 네모아이콘은 데이터를 입력할 수 있는 노드(Node)를 의미하고, 그중 가장 앞에있는 노드를 Head 또는 Header라고 한다.

나는 헤드(Head)에 데이터를 넣지않고 빈 공간으로 표현했지만, 구현에 따라서 헤드에도 데이터를 넣어도 된다. 어차피 헤드도 노드의 종류여서 문제없다.

화살표를 보면 각 노드는 다음 노드를 가리키고 있고, 마지막 노드는 다음 노드가 없기 때문에 아무것도 가리키지 않는다.

단일연결리스트의 이름에서 볼 수 있듯이 한쪽방향으로만 데이터가 연결되어 있다 

3번 노드의 데이터를 가져오려면 헤드 혹은 1번 노드부터 순차적으로 검색한다.

1번 노드야 너 3번이니? 아니

2번 노드야 너 3번이니? 아니

3번 노드야 너 3번이니? 응 

...

마지막 위치에 데이터를 추가하려면 마지막 노드를 찾아야하는 긴 여정이 필요하다.

그렇기 때문에 맨 앞에 데이터를 추가하는것이 여러모로 이롭다.

이미지가 선형적으로 되어 있어 마치 메모리에서도 인접해 보이고 정렬된 느낌이지만 이렇게 표현할 수도 있다

노드의 위치는 신경쓰지 않아도 된다.

그저 노드와 노드끼리의 연결만 신경쓰자.

2번 노드를 삭제해보자

벡터와 다르게 중간의 데이터를 삭제해도 각 데이터(노드)의 위치는 변하지 않는다

다만 2번 노드를 가리킨 1번 노드는 이제 2번이 아니라 2번의 다음 노드인 3번 노드를 가리키게 된다.

어렵지 않다. 그냥 가리키는것만 신경쓰자!!

2. 원형연결리스트

마지막 노드는 다시 첫 데이터(노드)를 가리킨다

단일연결리스트는 빈 헤드가 없는것이 기본적이다.

단일연결리스트에서 딱 하나 추가된 기능이 있는데

마지막노드가 빈 공간을 가리키지않고 첫 데이터를 가리킨다.

나는 원형연결리스트를 써본적이 없어서 그런지... 단일연결리스트보다 좋은 점을 잘 모르겠다.

굳이 따지면 마지막 노드가 nullptr을 가리키지않아 크래쉬가 날 확률이 적어지지만,

무한루프에 빠질수도 있는 단점도 가지고 있다

3. 이중연결리스트

모든 노드가 앞뒤로 연결되어 있어 역순환을 할 수 있다.

헤드와 동일한 개념의 테일(Tail)노드가 새로 생긴다.

단일, 원형연결리스트의 단점인 마지막노드검색이 훨씬 수월해진다.

단점은 이전 노드를 기억해야하는 변수를 만들고, 테일노드까지 생성해야해서 메모리를 좀 더 쓰게되지만, 

단점에 비해 장점이 크다.

나는 이중연결리스트만 구현했고 단일,원형연결리스트는 따로 구현하지 않았기 때문에

이중연결리스트만 소개하겠다.

https://github.com/ForestBird1/MyContainer