ForestBird

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

벡터(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

구글링으로 원형큐 구현을 보면 이상하게 원형큐의 사이즈가 정해져있고, 꽉차면 원형큐의 크기가 커지지않고 채울수 없는 구현만 봤다. 내가 못본걸수도 있지만,,,

이건 너무 이상해서 언제든 크기조절이 가능한 큐를 구현해보았다.

기존 원형큐의 단점은 위에 설명했듯이 큐에 데이터가 꽉차면 더이상 값을 넣을 수 없고, 그렇다고 큐의 사이즈를 키울 수도 없고, 빈공간을 효율적으로 관리하지만, 큐의 사이즈를 초기값설정후 다시 늘릴 수 없는 것이다.

분명 개발중 큐의 크기를 추정하기 애매할 때가 있을 거라 생각하고 원형큐의 장점인 빈 공간활용을 살리되, 언제든 벡터(vector)처럼 큐의 크기를 늘릴수 있는 기능을 추가하고 싶었다.

	void Reserve(size_t capacity) override
	{
		//기존 캐퍼시티가 더 크다면 재할당을 하지 않습니다
		if (this->my_capacity >= capacity)
			return;

		Data* temp = new Data[capacity];

		//Debug
		for (size_t i = 0; i < capacity; ++i)
		{
			temp[i] = NULL;
		}

		//0번째 인덱스부터 rear까지 새로 할당한 배열에 복사합니다
		for (size_t i = 0; i < _rear; ++i)
		{
			temp[i] = this->my_base[i];
		}

		//컨테이너에 원소가 있다면 새로 할당한 주소로 옮겨줍니다
		if (this->my_capacity > 0 &&
			this->my_size > 0 &&
			_rear <= _front)
		{
			//front부터 마지막인덱스까지 새로 할당한 배열에 복사합니다
			for (size_t i = 0; i < this->my_capacity - _front; ++i)
			{
				temp[capacity - i - 1] = this->my_base[this->my_capacity - i - 1];
			}
			_front += capacity - this->my_capacity;

			delete[] this->my_base;
		}

		
		this->my_capacity = capacity;
		this->my_base = temp;
	}

	//마지막 위치에 원소를 추가합니다
	//Enqueue()
	void PushBack(const Data& data)
	{
		//rear의 위치가 배열의 최대 크기를 넘었는지 확인
		if (_rear >= this->my_capacity)
		{
			_rear = 0;
		}

		//컨테이너에 비어있는 자리가 있는지 확인
		//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
		if (_rear == _front)
		{
			//큐가 꽉찼으면 재할당합니다
			if (this->my_size > 0)
			{
				this->Reserve(this->my_capacity + this->additive_capacity);
			}
		}

		//추가합니다
		this->my_base[_rear++] = data;
		++this->my_size;
	}

	//가장 처음으로 들어온 원소를 반환합니다
	//디버깅을 위해 bool로 반환의 실패여부를 체크합니다
	//Dequeue
	const bool PopFront(Data& out_data)
	{
		//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
		if (_rear == _front)
		{
			//큐가 비어있으면 Pop을 하지 않습니다
			if (this->my_size <= 0)
			{
				return false;
			}
		}

		if (_front >= this->my_capacity)
		{
			_front = 0;
		}

		--this->my_size;

		//return this->my_base[_front++];

		//Debug
		Data& data = this->my_base[_front++];
		Data data_new = data;
		out_data = data_new;
		data = NULL;

		return true;
	}

PushBack()을 보면 데이터가 꽉 찰때Reserve()함수를 사용하는데 이것말고는 기존 원형큐과 똑같고 PopFront()도 변경점은 없다.

자세히 봐야할것은 Reserve()함수인데 이 함수는 이전에 벡터(vector)구현할 때 소개했던것과 동일하지만, 기존 데이터를 재할당한 배열에 추가하는 방법이 조금 달라졌다.

데이터가 앞쪽에 그대로 있다면 이런식으로 재할당한 배열에 추가된다

벡터와 동일하게 데이터가 추가되지만

만약 뒷 공간이 꽉차서 앞 공간까지 넘어오게 되었을때는 이런식으로 동작한다

이건 벡터와 동일하다.

rear가 뒷공간을 넘어서 앞으로 넘어오게된 상황에서 어떻게 재할당이 이뤄지는것이 핵심이다

rear와 front사이의 공간을 확보한다.

이말은 추가데이터의 위치를 가리키는 rear의 뒷부분을 확보한다고 봐도 된다

그러기 위해 front를 기준으로 뒷부분의 데이터를 옮긴다.

데이터가 꽉차서 자동으로 재할당이 될 경우는 이렇게 된다.

rear와 front가 겹치고, 데이터가 있다는 뜻은 꽉찼다는 뜻이므로 rear와 front가 겹쳐있을 때 재할당이 이루어진다.

front위치 이후의 3개의 데이터가 계속 뒤로 밀리고 있으며 rear위치뒤에 빈공간을 계속 생성하는게 보일것이다.

벡터와 마찬가지로 크기재할당은 가급적 피하는것이 좋다. 

https://github.com/ForestBird1/MyContainer

원형큐의 구현은 어렵지 않다.

Enqueue하는데 뒷 공간이 없다면 앞으로 오면되고,,,

Dequeue또한 마찬가지이고...

그래서 딱 하나만 추가하면 된다

큐가 꽉찼거나 비어있음을 판단

이것만 구현한다면 원형큐도 이젠 쉽다!

	MyQueue_FixedCircle(size_t i_init_size)
	{
		//my_base가 nullptr지만
		//사이즈및 캐퍼시티가 0이므로 원소를 추가할때 Reserve()함수에서 할당이 이뤄집니다
		this->my_size = 0;
		this->my_capacity = i_init_size;

		Data* temp = new Data[this->my_capacity];

		this->my_base = temp;

		//Debug
		for (size_t i = 0; i < this->my_capacity; ++i)
			this->my_base[i] = NULL;
	}
    //마지막 위치에 원소를 추가합니다
	//Enqueue()
	const bool PushBack(const Data& data)
	{
		//rear의 위치가 배열의 최대 크기를 넘었는지 확인
		if (_rear >= this->my_capacity)
		{
			_rear = 0;
		}

		//컨테이너에 비어있는 자리가 있는지 확인
		//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
		if (_rear == _front)
		{
			//큐가 꽉찼으면 데이터를 채울 수 없습니다
			if (this->my_size > 0)
			{
				return false;
			}
		}

		//추가합니다
		this->my_base[_rear++] = data;
		++this->my_size;
		return true;
	}

	//가장 처음으로 들어온 원소를 반환합니다
	//디버깅을 위해 bool로 반환의 실패여부를 체크합니다
	//Dequeue
	const bool PopFront(Data& out_data)
	{
		//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
		if (_rear == _front)
		{
			//큐가 비어있으면 Pop을 하지 않습니다
			if (this->my_size <= 0)
			{
				return false;
			}
		}

		if (_front >= this->my_capacity)
		{
			_front = 0;
		}

		--this->my_size;

		//return this->my_base[_front++];

		//Debug
		Data& data = this->my_base[_front++];
		Data data_new = data;
		out_data = data_new;
		data = NULL;

		return true;
	}

다른 원형큐 구현을 보면 %연산자를 쓰고, isEmpty() isFull()등의 함수를 추가로 구현하던데 나는 그렇게 하지않고 최대한 직관적으로 구현했다.

EnQ나 DeQ를 하면 rear, front를 ++해주고 최대 사이즈를 넘어가면 0으로 돌아가게 하고,

내 원형큐는 데이터의 개수를 카운팅하고 있어서 rear==front라면 데이터개수를 판단해 큐가 비었는지 꽉찼는지 알 수 있다.

생성자를 보면 원형큐의 크기를 '무조건' 설정해줘야한다. 중간에 늘리거나 줄일 수 없다.

다른 원형큐 구현을 보면 const size_t QUEUE_SIZE = 1000; 뭐 이런식으로 하드코딩 해놓기도 하는데 똑같으면 재미없으니까 사용자가 원하는대로 크기를 조절할 수 있게 해놓았다

생성자 코드의 자세한 내용은 여기서 Reserve()구현부를 보면 확인할 수 있다.

https://forestbird0.tistory.com/38

다음 포스팅은 여기서 더 발전된 '동적 원형 큐'인데 대단한건 아니고 사이즈를 언제든 늘릴 수 있게 구현한 원형큐다.

https://github.com/ForestBird1/MyContainer