연결리스트 구현 연습

🔗 연결 리스트란?

연결 리스트(Linked List)는 데이터를 메모리 상에 연속적으로 저장하지 않고,
각 노드가 다음 노드(또는 이전 노드)를 가리키는 포인터를 가진 구조입니다.

✔ 특징 요약

항목	설명
메모리	비연속적
삽입/삭제	빠름 (위치를 알고 있을 때)
탐색	느림 (랜덤 접근 불가)
응용	큐, 스택, 트리, 해시 등 다양한 구조의 기초

---

🛠 연결 리스트 직접 구현

1. Node 클래스: 하나의 데이터를 담는 단위

template<typename T>
class Node
{
public:
	Node* _prev; // 이전 노드
	Node* _next; // 다음 노드
	T _data;     // 실제 데이터

	Node() : _prev(nullptr), _next(nullptr), _data(T()) {}
	Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value) {}
};

2. Iterator 클래스: 순회와 접근을 위한 도우미

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

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

	Iterator& operator++() { _node = _node->_next; return *this; }
	Iterator operator++(int) { Iterator temp = *this; _node = _node->_next; return temp; }

	Iterator& operator--() { _node = _node->_prev; return *this; }
	Iterator operator--(int) { Iterator temp = *this; _node = _node->_prev; return temp; }

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

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

✅ STL 스타일로 ++, --, *, ==, != 등을 오버로딩하여
마치 std::list처럼 사용할 수 있게 설계되어 있습니다.

---

3. List 클래스: 양방향 연결 리스트 전체 구현

template<typename T>
class List
{
public:
	using iterator = Iterator<T>;

	List() : _size(0)
	{
		_head = new Node<T>();
		_tail = new Node<T>();
		_head->_next = _tail;
		_tail->_prev = _head;
	}

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

	void push_back(const T& value) { AddNode(_tail, value); }
	void pop_back() { RemoveNode(_tail->_prev); }

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

	iterator insert(iterator it, const T& value)
	{
		Node<T>* node = AddNode(it._node, value);
		return iterator(node);
	}

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

private:
	Node<T>* _head;
	Node<T>* _tail;
	int _size;

	Node<T>* AddNode(Node<T>* before, const T& value)
	{
		Node<T>* newNode = new Node<T>(value);
		Node<T>* prevNode = before->_prev;

		prevNode->_next = newNode;
		newNode->_prev = prevNode;

		newNode->_next = before;
		before->_prev = newNode;

		_size++;
		return newNode;
	}

	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;
	}
};

💡 핵심 포인트

• head와 tail은 더미 노드로 사용되어 삽입/삭제 시 조건문 없이 처리 가능
• AddNode: 특정 노드 앞에 새 노드를 삽입
• RemoveNode: 특정 노드를 제거

---

🧪 실습: 연결 리스트 테스트

int main()
{
	List<int> li;
	List<int>::iterator eraseli;

	for (int i = 0; i < 10; i++)
	{
		if (i == 5)
			eraseli = li.insert(li.end(), i); // 5는 erase용으로 저장
		else
			li.push_back(i);
	}

	li.pop_back();          // 마지막 노드 제거
	li.erase(eraseli);      // i==5였던 노드 제거

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

🔍 실행 결과

• 0부터 9까지의 수 중 5와 9는 제거
• 출력: 0 1 2 3 4 6 7 8

---