1-5. 이중 배열 리스트(List) - 구현 복습

0. 필요성

vector가 list에 비해 얻는 편의성이 높기 때문에 대부분 vector를 사용하지만, 앞으로 공부할 자료 구조가

list가 기초가 되기 때문에 연습이 필요하다.

 

1. vector와 다른점?

(1) push_front가 존재

vector는 데이터 수정을 위해서 각 요소를 한칸씩 미는 것이 복사 - 이동의 순서를 거치기 때문에(비효율적) 제공하지 않는 기능이다.

 

(2) 중간 삽입 삭제가 효율적

(3) 이전 / 다음 노드를 가리키는 포인터를 저장

(4) list는 임의 접근이 불가능하기 때문에, 각 노드들을 타고 가서 찾는다

(5) insert가 존재

중간에 삽입하는 insert가 존재한다.

insert('삽입 위치의 바로 다음','삽입할 값')
// return 값은 반복자이다.

 

2. Node 구현

각 Node는 서로를 가리킨다. 그리고 Node는 생성자 오버로딩을 통해서 값을 매개변수로 받으면 _data에 저장한다.

template<typename T>
class Node // 양방향 리스트로 만든다.
{
public:
	Node() : _prev(nullptr), _next(nullptr), _data(T())
	{

	}

	Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value) // 생성자 오버로딩
	{

	}


public:
	T		_data; 
	Node*	_prev; // 자기 자신의 포인터 값(주소)을 타입으로 받는 멤버변수
	Node*	_next; // 주소를 타고 가면 Node가 있다는 뜻
};

 

 

3. List 구현

Node의 개수인 _size, 더미노드인 _head, _tail 매개변수를 저장한다.

이때 더미노드들은 자기 자신의 타입의 포인터 형을 받는데, 이것은

_head(혹은 _tail) 멤버 변수를 (주소를)타고 가면 Node 형의 데이터가 있다고 알려주는 것이므로 문제가 없다.

 

(1) 생성자 초기화

생성자를 호출하면 _size를 0으로 초기화한다.

 _head와 _tail은 초기에 서로를 가리키게 만든다.

이를 통해서 노드의 Null Check를 하는 작업을 생략할 수 있다.

또한 중간에 노드를 연결하는 작업을 수월하게 진행할 수 있다.

template<typename T>
class List	// 시작 데이터, 끝 데이터,
{
private:
	Node<T>*	_head; // 더미 노드를 만들어 준다
	Node<T>*	_tail;
	int             _size;
    
public:
	List() : _size(0)
	{
		_head = new Node<T>();
		_tail = new Node<T>(); // _head <-> _tail
		_head->_next = _tail;
		_tail->_prev = _head; // NULL Check를 하지 않아도 된다.
	}

 

(2) 소멸자

list의 모든 요소를 pop_back을 사용해 추출하고 더미노드 _head와 _tail을 삭제한다.

	~List()
	{
		while (_size > 0)
		{
			pop_back();
		}
		delete _head;
		delete _tail;
	}

(3) push_back

tail의 이전 위치에 데이터를 삽입하는 함수이다.

insert 함수와 비슷한 기능을 공유하므로 노드를 추가하는 함수를 따로 만들어 관리한다.

	void push_back(const T& value) // tail 이전에 데이터를 삽입
	{
		AddNode(_tail, value);
	}

(4) pop_back

tail 이전 위치의 데이터를 추출하는 함수이다.

마찬가지로 remove 함수와 비슷한 기능을 공유하기 때문에 노드를 제거하는 함수를 따로 만들어 관리한다.

	void pop_back() // tail 이전의 데이터를 추출
	{
		RemoveNode(_tail->_prev);
	}

(5) AddNode('위치', '값')

노드를 입력된 노드의 위치의 이전에 추가한다.

// 추가 이전 : [head] <-> [1] <-> [prevNode] <-> [before] <-> [tail]
// 추가 이후 : [head] <-> [1] <-> [prevNode] <-> [newNode] <-> [before] <-> [tail]

위의 관계도를 보고 구현한다.

	Node<T>* AddNode(Node<T>* before, const T& value)
	{
		Node<T>* newNode = new Node<T>(value); // 새로운 노드를 value값을 가진 노드로 동적할당
		Node<T>* prevNode = before->_prev; // prevNode는 before 노드의 이전을 가리킴

		prevNode->_next = newNode; // 추가 이후 prevNode의 다음이 새로운 노드임
		newNode->_prev = prevNode; // 추가 이후 새로운 노드의 이전이 prevNode(이전 노드)임

		newNode->_next = before; // 새로운 노드의 다음이 before임
		before->_prev = newNode; // before의 이전이 새로운 노드를 가리킴

		_size++;

		return newNode; // 새로운 노드를 리턴함
	}

newNode의 위치(포인터)를 반환한다.

 

(6) RemoveNode('제거할 노드')

// 제거 이전 : [head] <-> [prevNode] <-> [node] <-> [nextNode] <-> [tail]
// 제거 이후 :[head] <-> [prevNode] <-> [nextNode] <-> [tail]

위의 관계도를 보고 구현한다.

	Node<T>* RemoveNode(Node<T>* node)
	{
		Node<T>* prevNode = node->_prev;
		Node<T>* nextNode = node->_next;

		prevNode->_next = nextNode;
		nextNode->_prev = prevNode;

		delete node;

		_size--;

		return nextNode;
	}
    
    	int size() { return _size; }

제거된 위치인 nextNode의 위치(포인터)를 반환한다.

 

(6) 반복자(Iterator)를 사용한 begin(), end(), insert(), erase()의 구현

4번의 반복자 구현 이후에 작성한다.

 

 

4. 반복자(Iterator) 구현

begin(), end(), insert(), erase()의 함수들을 구현하기 위해서 반복자를 구현하는 실습을 한다.

단, List 클래스 내에서 반복자를 사용하므로 반드시 반복자 클래스가 List 클래스 코드보다 먼저 와야(위에 있어야) 된다.

 

(1) 생성자 초기화

반복자가 생성될 때에는 어떤 노드도 가리키지 않도록 작성한다.

template<typename T>
class Iterator
{
public:
	Node<T>* _node;
    
public:
	Iterator() : _node(nullptr)
	{

	}

 

(2) 생성자 오버로딩

반복자가 어떤 노드를 가리키도록 생성되면 해당 노드를 가리키도록 작성한다.

	Iterator(Node<T>* node) : _node(node)
	{

	}

 

(3) 연산자 오버로딩

반복자는 증감이(전위형, 후위형 모두) 가능해야 하고 역참조 연산자(*It)를 사용해서 값을 반환할 수 있어야 한다.

(3-1) 증가 연산자 ; ++It, It++

	//++It ; 전위 증가 연산자
	Iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//It++ ; 후위 증가 연산자
	Iterator operator++(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_next;
		return temp;
	}

후위형에서 int가 삽입된 것은 단순히 후위형임을 나타내기 위함이며 실제로 사용되지는 않는다.

 

(3-2) 감소 연산자 ; --It, It--

	//It-- ; 전위 감소 연산자
	Iterator& operator--()
	{
		_node = _node->prev;
		return *this;
	}
    
        //--It ; 후위 감소 연산자
	Iterator operator--(int)
	{
		Iterator<T> temp = *this;
		_node = _node->_prev;
		return temp;
	}

 

(3-3) 역참조 연산자 ; *It

	//*it
	T& operator*()
	{
		return _node->_data;
	}

' * ' 다음에 오는 포인터의 값을 리턴하는 연산자이다.

 

(3-4)  동등비교 연산자 ; ==, !=

	bool operator==(const Iterator& other)
	{
		return _node == other._node;
	}

	bool operator!=(const Iterator& other)
	{
		return _node != other._node;
	}
};

다른 노드(other)가 왼값과 같은지 다른지 판단하는 연산자이다.

true or false를 반환하기 때문에 boolean 타입이다.

 

5. List 클래스에서 반복자(Iterator)를 사용한 begin(), end(), insert(), erase()의 구현

위의 4번에서 반복자를 구현하였으니 이제 이를 사용한 4개의 함수를 구현한다.

아래의 코드들은 List 클래스 내에서 public으로 작성한다.

 

(1) begin, end

begin은 노드들의 처음을 가리키고, end는 노드들의 마지막을 가리킨다.

즉 begin은 _head 노드의 다음 노드, end 노드는 _tail노드이다.

 

(1-1) end 함수가 _tail->prev가 아닌 _tail 노드를 가리키는 이유는?

연결 리스트의 마지막 원소 다음에는 유효한 데이터가 없다.

따라서 실제 데이터가 존재하는 마지막 노드의 다음을 가리키는 반복자를 반환하는 것은 메모리를 오염(엉뚱한 메모리를 수정)시킬 위험이 있다.

따라서 단순히 리스트의 끝을 나타내는 _tail 노드를 가리키게 한다.

 

(1-2)

public:
	using iterator = Iterator<T>;

	iterator begin() { return iterator(_head->_next); }
	iterator end() { return iterator(_tail); }

 

(2) insert, erase

위에서 push_back과 pop_back과의 연관성이 있다고 하였으므로, AddNode와 RemoveNode를 사용해서 구현한다.

	iterator insert(iterator it, const T& value) // it 이전 노드에 추가하는 것임!!!
	{
		Node<T>* node = AddNode(it._node, value);
		return iterator(node);
	}

	iterator erase(iterator it)
	{
		Node<T>* node = RemoveNode(it._node);
		return iterator(node);
	}

여기서 insert는 반복자가 가리키는 위치에 새로운 값을 삽입하고 반복자를 반환한다.

이 때 반복자는 새로운 값을 가리킨다.

여기서 AddNode 함수는 입력된 위치의 이전(node->prev) 위치에 새로운 노드를 만든다는 것을 유의하여야 한다.