인사글
안녕하세요 Aron입니다.
이전 C++에서 구현한 가변배열에서 이어서 이번시간에서도
링크드 리스트를 왜 알아야하고 어떻게 구현하는지를 글로 작성해보려합니다
인사글인 만큼 솔직하게 글을 써보자면 C++에서 저는 리스트를 쓰기 싫습니다.
데이터 중간 삽입이 가능하다는점 이전글에 설명 드렸던것처럼 요소값이 많으면 벡터는 비효율적인면을
이해하고있으면서도 C++ List 이터레이터는 데이터 컨테이닝 기능이 C#의 List에 비하면 너무 불편하게만 느껴집니다. 하지만, 이터레이터의 기능을 한번쯤은 이해하는편이 좋습니다.
다른 언어 모두 이터레이터를 사용하고 부르는 방식이나 이름이 달라졌을뿐 반복자는 어디에서는 존재하기에 이번 글에서 간단하게 리스트와 반복기도 같이 구현해볼생각입니다.
개요
링크드 리스트(linked list)는 데이터를 순서대로 저장하는 자료구조 중 하나로, 각 데이터 요소가 이전과 다음 요소와의 링크로 연결돼 있습니다. 배열과는 달리 링크드 리스트는 각 요소가 메모리 상에서 연속적으로 위치하지 않고, 각각이 독립적인 노드로 구성됩니다.
링크드 리스트의 주요 특징은 데이터의 삽입, 삭제가 배열보다 효율적으로 이루어질 수 있다는 것입니다. 또한, 크기가 동적으로 조절될 수 있어 메모리를 효율적으로 활용할 수 있습니다. 그러나 인덱스를 통한 직접 접근이 어려워 탐색 시간이 배열보다 더 많이 소요될 수 있습니다.
링크드 리스트는 단일 연결 리스트와 이중 연결 리스트로 나눌 수 있으며, 각각의 구조에 따라 활용하는 상황이 달라집니다. 데이터의 동적 관리와 삽입, 삭제 연산이 빈번한 상황에서 링크드 리스트는 유용한 자료구조로 활용됩니다.
이터레이터가 필요한 이유는 무엇일까?
백터의 경우vec[3] = 10 이러한 쉬운 요소의 접근이 가능한데 왜 링크드 리스트는 접근이 불가능한걸까요?
위 그림은 1,2,5,3 정수 데이터를 담은 링크드 리스트의 랜덤한 메모리 주소 상태를 표현한것입니다.
vec[3] 이란 접근의 의미가 벡터의 3번째 메모리 주소의 접근을 허용하는것이기 때문입니다.
벡터는 요소값이 순차적 메모리 주소에 데이터를 선언받기에 인덱스로인한 접근이 가능한것입니다.
반대로 그림처럼 메모리주소가 일정하지않는 리스트는 numbers[3] = 10 이러한 허용이 불가능한것 이고
서로를 이어주는 연결이 필요하고 이터레이터 반복탐색하여 원하는값을 찾게 도와주는 역할을 하는것이 됩니다.
노드 클래스
개요에서 설명 드린 내용과 같이 링크드 리스트는 독립적인 노드들의 링크로 연결되어있습니다.
이를 우리는 직접 구현하고 이해해보려합니다.
template<typename T>
class Node
{
public:
Node() : _prev(nullptr), _next(nullptr), _data(T())
{
}
Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value)
{
}
public:
//이전값 노드 주소
Node* _prev;
//다음값 노드 주소
Node* _next;
//데이터
T _data;
};
제가 상상하는 노드의 추상적인 느낌입니다.
노드는 데이터,링크를 위한 이전값 노드 주소, 다음값 노드 주소로 구성되어있습니다.
서로 다른 메모리에 할당되어 알수없는 데이터들을 앞뒤로 링크 시켜 데이터 접근이
가능하게끔 만들어줍니다. 결국 노드들의 집한체가 링크드 리스트를 만들게됩니다
위와 같이 앞뒤로 주소값을 2개 가지면 양방향 링크드 리스트 입니다.
이전값 주소가 없고 다음값 주소만을 가진다면 단방향 링크드 리스트 입니다.
실습은 양방향 링크드 리스트로 해보겠습니다.
리스트 클래스
위 그림은 완성된 링크드 리스트의 모습입니다.
_prev와 _next는 서로이 이웃한 노드를 가리키며 결합합니다.
서로 연결된 링크만으로는 원하는 데이터를 찾기 어렵습니다.
이터레이터가 리스트의 처음노드부터 끝노드까지 순차적으로 탐색할수있게끔
head와 tail의 정보가 반드시 필요합니다.
이때 주의해야할점은 head와 tail은 리스트의 생성시 바로 만들어지며
값이 존재하지않습니다.
이유는 추가되는 값이 head가 되거나 tail이 될수도 있는 유동적인 list란 stl에
데이터가 없는 head와 tail이 더 구현하기 원활해서 입니다.
template<typename T>
class List
{
public:
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;
}
};
리스트 클래스 ::Push_back 함수
public:
void push_back(const T& value)
{
AddNode(_tail, value);
}
private:
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->_next = before;
before->_prev = newNode;
newNode->_prev = prevNode;
_size++;
return newNode;
}
코드 설명
새로운 요소값을 Node 클래스로 동적할당 합니다.
새로운 요소값을 추가하면 tail로 재정의가 필요합니다.
위에서 가리키는 before는 tail을 뜻하고
prevNode는 리스트의 마지막 노드를 뜻합니다.
1. 이전 마지막 노드의 _next를 새노드로 재정의합니다.
2. 새노드의 next는 tail을 가리킵니다.
3. 새노드의 next는 데이터가 빈 tail을 가리킵니다.
4. 사이즈를 증가합니다.
5. 새노드를 반환합니다.
결국 꼬리와 리스트의 마지막 노드 사이에 데이터를 삽입한것과 결과가 같습니다.
AddNode함수는 매개변수에 따라서 Insert 구현으로 바로 응용이 가능합니다.
리스트 클래스 ::pop_back함수
public:
void pop_back()
{
RemoveNode(_tail->_prev);
}
private:
Node<T>* RemoveNode(Node<T>* node)
{
Node<T>* next = node->_next;
Node<T>* prev = node->_prev;
next->_prev = prev;
prev->_next = next;
delete node;
_size--;
return next;
}tail의 이전 노드는 리스트의 마지막 노드를 뜻합니다.
해당 노드를 삭제하기위해 이전 AddNode와 반대로 결합된 삭제 대상 노드의 _prev, _next삭제합니다
그리고 삭제한 노드를 가르켰던 _prev,_next를 재정의합니다.
next(tail)을 반환합니다.
Iterator 클래스
template<typename T>
class Iterator
{
public:
Iterator() : _node(nullptr)
{
}
Iterator(Node<T>* node) : _node(node)
{
}
Iterator& operator++()
{
_node = _node->_next;
return *this;
}
Iterator operator++(int)
{
Iterator<T> temp = *this;
_node = _node->_next;
return temp;
}
Iterator& operator--()
{
_node = _node->_prev;
return *this;
}
Iterator operator--(int)
{
Iterator<T> 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;
}
public:
Node<T>* _node;
private:
};
- 멤버변수:
- _node는 반복중인 현 current의 노드를 가리킵니다.
- _node는 반복중인 현 current의 노드를 가리킵니다.
- 생성자:
- Iterator() : _node(nullptr): 기본 생성자로, _node를 nullptr로 초기화합니다.
- Iterator(Node<T>* node) : _node(node): 노드 포인터를 받아서 초기화하는 생성자로, 주어진 노드로 _node를 초기화합니다.
- 전위 증가 연산자 (operator++):
- _node를 다음 노드로 이동시키고 자기 자신을 반환합니다.
- 후위 증가 연산자 (operator++(int)):
- 현재 상태를 저장한 임시 객체를 생성한 후, _node를 다음 노드로 이동시킵니다. 저장한 임시 객체를 반환합니다.
- 전위 감소 연산자 (operator--):
- _node를 이전 노드로 이동시키고 자기 자신을 반환합니다.
- 후위 감소 연산자 (operator--(int)):
- 현재 상태를 저장한 임시 객체를 생성한 후, _node를 이전 노드로 이동시킵니다. 저장한 임시 객체를 반환합니다.
- 역참조 연산자 (operator*):
- 현재 노드의 데이터에 대한 참조를 반환합니다.
- 등호 연산자 (operator==):
- 현재 노드가 다른 반복자의 현재 노드와 같은지 여부를 확인하여 참 또는 거짓을 반환합니다.
- 부등호 연산자 (operator!=):
- 현재 노드가 다른 반복자의 현재 노드와 다른지 여부를 확인하여 참 또는 거짓을 반환합니다.
리스트 클래스 추가 기능
//List 이터레이터
public:
using my_iterator = Iterator<T>;
my_iterator begin() { return my_iterator(_head->_next); }
my_iterator end() { return my_iterator(_tail); }
my_iterator insert(my_iterator it, const T& value)
{
Node<T>* node = AddNode(it._node, value);
return my_iterator(node);
}
my_iterator erase(my_iterator it)
{
Node<T>* node = RemoveNode(it._node);
return my_iterator(node);
}
이터레이터 클래스 구현으로 노드를 탐색하는 함수를 구현할수있게 되었습니다.
- using my_iterator = Iterator<T>;
- 앞서 구현한 Iterator클래스를 리스트에서 사용하기 위해 my_iterator라는 별칭으로 사용하겠다는 선언부 입니다.
- begin()
- 리스트의 첫번째 노드를 의미합니다.
- end()
- 리스트의 마지막 노드를 의미합니다.
- 리스트의 마지막 노드를 의미합니다.
- insert
- insert 내부코드 AddNode의 호출 첫번째 인자값은 이전 노드를 의미하며
it._node의 이전 노드에서 삽입이 이루어집니다.
- insert 내부코드 AddNode의 호출 첫번째 인자값은 이전 노드를 의미하며
- erase
- it._node를 리스트에서 제거하고 삭제한 다음 대상의 노드로 _node 재정의합니다
상황에 따라 _node는 nullptr입니다.
- it._node를 리스트에서 제거하고 삭제한 다음 대상의 노드로 _node 재정의합니다
마무리말
여기까지가 오늘 해보게된 리스트, 이터레이터 구현이었습니다.
리스트 클래스 자체의 구현은 어려울게 없습니다.
데이터 탐색 부분도 for문을 이용하거나 while문을 이용해서 index의 접근이 가능하게끔 구현하는것도 물론
가능합니다 이번 글에서 중요한것은 이터레이터보다는 리스트의 랜덤한 heap메모리에 할당된 데이터를 어떻게 접근할수있는지를 알아보기위한 글이었습니다 오늘도 긴글을 읽어주셔서 감사합니다
다음에는 그래프 알고리즘에대해 구현해보는 시간을 가져보겠습니다.
'알고리즘' 카테고리의 다른 글
| 그래프 알고리즘이란 (2) | 2024.03.18 |
|---|---|
| 동적배열 왜 반드시 알아야하는가 (0) | 2024.01.16 |
| 게임 개발 알고리즘 공부 왜 필수인가 (0) | 2024.01.16 |
