강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)

list도 저번에 우리가 선영자료구조를 할 때 알아보았기 때문에 어렵지는 않을 것이다.

list

list도 vector와 마찬가지로 이러한 것들이 있을 것이다

• size(resize)
• capacity(reserve)
• 삽입/삭제
  • 시작 O(1)
  • 중간 O(1) << 조건
  • 끝 O(1)
• front O(1)
• back O(1)
• push_front O(1)
• push_back O(1)
• 임의 접근 li[2] O(1)
• remove(value)

list에서는 size랑 capacity를 어떻게 분석을 할 수 있을까?
size는 node기반으로 list를 구현하기때문에 데이터의 개수를 이야기하는 것이고
capacity는 없다!
애초에 list는 capacity라는 개념이 없기 때문이다.

list는 실시간으로 만들때마다 노드가 늘어나서 이어붙이는 방식이여서 capacity라는 개념은 없다.
뭐 그래도 resize(10)을 하면 데이터가 10개 할당되는 것은 변함이 없다.

그리고 vector의 초기화방식도 동일하게 동작을 한다.

또 list는 vector와 다르게 push_back말고도 push_front도 지원을 한다.
그럼 이때 시간복잡도는 시작, 중간, 끝 모두 O(1)이다.
하지만 중간은 위치를 정확하게 알아야지 O(1)이다.
우리는 iterator를 배웠기 때문에 list기반으로 작업을 할 때에는 iterator를 기억했다가 그것을 활용한다.

front와 back도 O(1)이다.

그리고 데이터를 삭제할 때 erase를 사용한다면 iterator를 이용해서 삭제할 수 있다. 하지만 push_back,front에서는 iterator를 지원하지 않는다.

그래서 우리는 insert라는 것을 사용하여서 iterator를 활용하여 값을 넣어줄 수 있다.

list<int> li;

// 위치를 iterator로 반환해줌
li.insert(li.end(), 1);
li.insert(li.end(), 2);
list<int>::iterator it = li.insert(li.end(), 3);
li.insert(li.end(), 4);

// 위치를 기억하고 넣어줄 수 있다.
//li.insert(it, 100);

// 반환받은 위치로 값을 삭제할 수 있다.
li.erase(it)

그리고 list에서는 임의접근을 지원하지 않는다.

그래서 vector보다 list가 더 좋아보이지만 노드를 타고가는 연산이 조금씩 더 잡아먹기 때문에 vector보다 조금 느리다고 할 수 있다.
(참고로 C#의 list는 vector이다)

그래서 list는 자체적으로 활용도는 높지 않지만 list를 활용하여서 다른 것들을 만들때에는 유용하게 사용된다.

list로 순회를 도는 코드를 짜는 것은 vector와 비슷하다.

list<int> li = {1, 2, 3, 4, 5}

for(list<int>::iterator it = li.begin(); it != li.end(); it++)
{
	int value = *it;
    cout << value << endl;
}

이런식으로 iterator를 사용하여서 찾을 수 있다.

만약 특정 데이터를 찾는 것을 만든다고 하면(다음에 알고리즘을 배우면 std::find로도 만들 수 있다)

list<int> li = {1, 2, 3, 4, 5}

// 소멸되지 않도록
list<int>::iterator it;

for(it = li.begin(); it != li.end(); it++)
{
	int value = *it;
    if(value == 3)
    {
    	break;
    }
}

if(it != li.end())
{
	//있다
}

이런식으로 vector와 똑같이 구현할 수 있다.

그리고 list에서도 vector와 동일하게 조심해야 하는 부분이 있다.
바로 erase를 사용할 때이다.

list<int> li = {1, 2, 3, 4, 5}

for(list<int>::iterator it = li.begin(); it != li.end();)
{
	int value = *it;
    if(value % 2 == 0)
    {
    	// 값을 받아준다.
    	it = li.erase(it);
    }
    else
    {
    	// 받은 값이 확인을 안하고 넘어갈 수 있으니 여기서 it++을 해준다.
    	it++;
    }
    
}

이런식으로 erase를 사용할 떄는 바로 break를 해주거나 값을 받아주고 다른 곳에서 it++처리를 해줘야 한다.

이것도 vector와 구현하는 방식이 똑같다고 볼 수 있다.

즉, iterator라는 인터페이스 방식으로 똑같이 작업을 하고 있기에 list든 vector든 코드를 유사하게 구현할 수 있다.

list의 iterator

저번에 구현했던 list코드이다.

#pragma once
#include <iostream>
using namespace std;

template<typename T>
class Node
{
public:
	Node(int data) : data(data), prev(nullptr), next(nullptr) { }

public:
	T		data;
	Node*	prev;
	Node*	next;
};

template<typename T>
class List
{
public:
	List()
	{
		_head = new Node<T>(0);
		_tail = new Node<T>(0);
		_head->next = _tail;
		_tail->prev = _head;
	}

	~List()
	{
		Node<T>* node = _head;
		while (node)
		{
			Node<T>* deleteNode = node;
			node = node->next;
			delete deleteNode;
		}
	}

	// [dummy]<->[1]<->[2]<->[3]<->[dummy]
	// [head]						[tail]
	Node<T>* GetNode(int index)
	{
		Node<T>* node = _head->next;
		if (node == _tail)
			return nullptr;

		for (int i = 0; i < index; i++)
		{
			if (node == _tail->prev)
				return nullptr;
			
			node = node->next;
		}

		return node;
	}

	void Print()
	{
		Node<T>* node = _head->next;
		while (node != _tail)
		{
			cout << node->data << " ";
			node = node->next;
		}
		cout << endl;
	}

	Node<T>* AddAtHead(int data)
	{
		Node<T>* node = new Node<T>(data);
		Node<T>* nextNode = _head->next;

		node->next = nextNode;
		nextNode->prev = node;
		_head->next = node;
		node->prev = _head;

		return node;
	}

	Node<T>* AddAtTail(int data)
	{
		Node<T>* node = new Node<T>(data);
		Node<T>* prevNode = _tail->prev;

		prevNode->next = node;
		node->prev = prevNode;
		node->next = _tail;
		_tail->prev = node;

		return node;
	}
	
	void Insert(Node<T>* posNode, int data)
	{
		Node<T>* node = new Node<T>(data);
		Node<T>* prevNode = posNode->prev;

		prevNode->next = node;
		node->prev = prevNode;
		node->next = posNode;
		posNode->prev = node;
	}
				
	Node<T>* Remove(Node<T>* node)
	{
		Node<T>* prevNode = node->prev;
		Node<T>* nextNode = node->next;
		prevNode->next = nextNode;
		nextNode->prev = prevNode;

		delete node;

		return nextNode;
	}

private:
	Node<T>* _head = nullptr;
	Node<T>* _tail = nullptr;
};

list는 vector보다 조금 더 다양한 방식으로 iterator를 만들 수 있다.
(list를 구현하는 다양한 방식이 있다)
우리는 dummy 2개를 사용하는 방식이다.

그럼 구현을 해보자

template<typename T>
class Iterator
{
public:

public:
	Node* _node;
}

일단 list에서는 Node가 데이터와 데이터의 다음과 이전을 가지고 있기 때문에 Node를 들고 있게 해준다.

그 다음에는 vector의 iterator에서 했던 것처럼 다양한 시리즈들을 구현을 해주면 된다.

template<typename T>
class Iterator
{
public:
	Iterator() : _node(nullptr) {}
	// 노드 지정시 저장
	Iterator(Node<T> node) : _node(node) {}

	// ++it
	Iterator& operator++()
	{
		// 현재 노드에 다음노드 저장
		_node = _node->next;
		return *this;
	}

	// it++
	Iterator operator++(int)
	{
		Iterator temp = *this;
		// 현재 노드에 다음노드 저장
		_node = _node->next;
		return temp;
	}

	T& operator*()
	{
		return _node->data;
	}

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

	bool operator!=(const Iterator& other)
	{
		return _node != otehr._node;
	}
public:
	Node<T> _node;
};

이런식으로 vector와 유사하게 구현을 해주면 된다.

그리고 list에서는

using iterator = Iterator<T>;

// dummy 노드 다음 노드가 첫 번쨰 노드
iterator begin() { return iterator(_head->next); }
// dummy 노드가 마지막 다음이기에 _tail
iterator end() { return iterator(_tail); }

이런식으로 iterator를 들고 있게 만들어주고 begin과 end를 만들어준다.

그러면 list를 이런식으로 사용할 수 있게 된다.

List<int> li;
li.AddAtTail(10);
li.AddAtTail(20);
li.AddAtTail(30);

for(List<int>::iterator it = li.begin(); it != li.end();)
{
	int value = *it;
    cout << value << endl;
}

결국 list의 iterator도 엄청 신기한 개념은 아니고 그냥 인터페이스를 만들어서 우리가 원하는 자료구조에 맞춰서 구현만 해주면 만들 수 있다.
즉, iterator는 helper class(wrapper class)라고 볼 수 있다.

이제 list는 여기서 마무리를 하겠다.

마무리

다음 포스트(알고리즘 파트)에는 이미 만들어진 함수를 사용하여서 작업하는 것을 연습해 볼 것이다.

비하인드로..이 글을 적다가 적던글이 다 날라가 버리는 대참사가 일어나버려서..멘탈이 불안정한 상태로 작성을 하여서 글이 좀 난잡할 수 있습니다. 죄송합니다..