배열
배열 : 배열은 인접한 메모리에 저장되는 요소의 집합입니다. 인덱스를 통한 빠른 접근이 가능하며 예상 할 수 있는 순서로 데이터를 저장하고 탐색하는데 사용하기 좋은 자료구조입니다. 또한, 연속된 메모리 주소에 요소들이 존재하기 때문에 관리하기 쉽습니다.
다만, 삽입과 삭제에 시간 복잡도 O(N) 성능을 보여 다른 자료구조보다 시간적 성능이 좋지 못합니다. 또한, 메모리의 재사용이 어렵습니다. 처음 할당 받은 메로리 중 일부 데이터를 삭제하더라도 배열 자체가 삭제되지 않으면 해당 공간을 재사용 할 수 없습니다.
배열의 시간복잡도 :
탐색 - 임의 접근 방식으로 인덱스를 가지고 있기에 빠른 탐색이 가능합니다. 탐색 시 배열은 O(1) 의 시간복잡도를 가집니다.
추가 - 추가하려는 데이터가 맨 뒤가 아니면 특정 인덱스 이후의 모든 데이터들을 한 칸씩 미뤄야해서 O(N)의 시간복잡도를 가집니다.
삭제 - 데이터 삭제 시에도 삭제하려는 데이터의 위치가 맨 뒤가 아니면 O(N)의 시간복잡도를 가집니다.
따라서 배열은 사용할 메모리의 크기가 정해져 있거나, 데이터의 삽입 삭제를 적게 사용하는 경우, 순차적 검색 및 탐색을 빈번하게 사용할 경우에 사용하기 용이한 자료구조입니다.
연결리스트
연결리스트는 동적인 자료구조입니다.
연결리스트에는 노드가 존재하고 각 노드에는 저장되는 데이터 값과 다음 데이터가 있는 메모리 주소 등을 가지고 있습니다.
그래서 배열처럼 연속된 메모리 공간을 가지지 않고도 선형구조로 데이터를 저장할 수 있습니다.
주소 값을 이용하여 접근이 가능하므로 데이터의 추가 삭제에 용이한 자료구조입니다. 다만, 인덱스를 가지지 않기 때문에 임의 접근이 불가능하며, 데이터 탐색을 위해서 순차 접근 방식을 사용해야하는 단점이 있습니다. 또한, 데이터를 저장할 공간 뿐 아니라 다음 노드를 가리킬 포인터를 저장하는 공간이 추가적으로 필요합니다.
연결리스트 시간 복잡도
데이터 탐색 : 순차 접근 방식으로 탐색하기 때문에 O(N)의 시간복잡도를 가집니다.
데이터 추가/삭제 : 삽입/삭제 할 주변 노드들의 포인터 주소 값만 수정하면 된다. O(1)의 시간복잡도를 가집니다.
다만, 이것은 자신이 추가/삭제할 노드의 이전 노드를 알고 있을 때의 경우이며, 모르는 경우 다시 순차 접근을 해야하므로 O(N) 시간복잡도를 가집니다
스택 구현
// 스택
// LIFO 후입선출
// 예) 되돌리기 복원 등등에 사용
template<typename T, typename Container = vector<T>>
class Stack
{
public:
void push(const T& value)
{
_container.push_back(value);
}
void pop()
{
_container.pop_back();
}
T& top()
{
return _container.back();
}
bool empty()
{
return _container.empty();
}
int size()
{
return _container.size();
}
private:
//vector<T> _container;
//list<T> _container;
Container _container;
};
리스트 구현
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<T> temp = *this;
_node = _node->_next;
return temp;
}
// --it
Iterator& operator--()
{
_node = _node->_prev;
return *this;
}
// it--
Iterator operator--(int)
{
Iterator<T> temp = *this;
_node = _node->_prev;
return temp;
}
// *it
T& operator*()
{
return _node->_data;
}
bool operator==(const Iterator& other)
{
return _node == other._node;
}
bool operator!=(const Iterator& other)
{
return !(*this == other);
}
public:
Node<T>* _node;
private:
};
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;
};
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;
}
void push_back(const T& value)
{
// 꼬리 전에 노드를 추가 맨 뒷부분
AddNode(_tail, value);
}
void pop_back()
{
// 꼬리 더미노드의 전 노드 즉 마지막 노드
RemoveNode(_tail->_prev);
}
private:
// [head] <-> [prevNode] <-> [before] <-> [tail]
// [head] <-> [prevNode] <-> [node] <-> [before] <-> [tail]
Node<T>* AddNode(Node<T>* before, const T& value)
{
Node<T>* newNode = new Node<T>(value);
//newNode->_data = value;
Node<T>* prevNode = before->_prev;
prevNode->_next = newNode;
newNode->_prev = prevNode;
newNode->_next = before;
before->_prev = newNode;
_size++;
return newNode;
}
// [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; }
public:
using iterator = Iterator<T>;
iterator begin() { return iterator(_head->_next); }
iterator end() { return iterator(_tail); }
// 매개변수 it 의 앞에 넣는다.
iterator insert(iterator it, 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;
};
vector 구현
template<typename T>
class Vector
{
public:
Vector()
{
}
~Vector()
{
if (_data)
{
delete[] _data;
}
}
void push_back(const T& value)
{
if (_size == _capacity)
{
// 증설 작업
int newCapacity = static_cast<int>(_capacity * 1.5);
if (newCapacity == _capacity)
{
newCapacity++;
}
reserve(newCapacity);
}
// 데이터 저장
_data[_size] = value;
// 데이터 개수 증가
_size++;
}
void reserve(int capacity)
{
if (_capacity >= capacity)
return;
_capacity = capacity;
T* newData = new T[_capacity];
// 데이터 복사
for (int i = 0; i < _size; i++)
{
newData[i] = _data[i];
}
if (_data)
{
delete[] _data;
}
_data = newData;
}
T& operator[](const int pos) { return _data[pos]; }
int size() { return _size; }
int capacity() { return _capacity; }
void clear()
{
if (_data)
{
delete[] _data;
_data = new T[_capacity];
}
_size = 0;
}
private:
T* _data = nullptr;
int _size = 0;
int _capacity = 0;
};
queue 구현
#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;
// Queue (FIFO 선입선출)
// front << [1][2][3][4] << rear(back)
// 대기열
// 앞에서 꺼내야하기 때문에 노드를 이용하는 연결리스트 사용.
// deque 를 사용해도 가능
// [ ][ ][ ][a]
// [1][2][3][4]
// 데크의 삽입 기능이 위와 같아서 사용가능
// 실제 stack 과 queue stl 의 기본 컨테이너는 deque 로 되어있음
template<typename T>
class ArrayQueue
{
public:
ArrayQueue()
{
//_container.resize(100);
}
void push(const T& value)
{
// 다 찼는지 체크
if (_size == _container.size())
{
// 증설 작업
int newSize = max(1, _size * 2);
vector<T> newData;
newData.resize(newSize);
// 데이터 복사
for (int i = 0; i < _size; ++i)
{
// 복사 전 기존 컨테이너의 N 번째 위치의 인덱스
int index = (_front + i) % _container.size();
newData[i] = _container[index];
}
_container.swap(newData);
_front = 0;
_back = _size;
}
_container[_back] = value;
// 최대 사이즈에 _back 이 도달 했을 때 맨처음으로 돌리는 기본 테크닉
_back = (_back + 1) % _container.size();
// 실제 데이터 갯수 size() 는 전체 사이즈임 다른거임
_size++;
}
void pop()
{
if (empty())
return;
_front = (_front + 1) % _container.size();
_size--;
}
T& front()
{
return _container[_front];
}
bool empty()
{
return _size == 0;
}
int size()
{
return _size;
}
private:
vector<T> _container;
int _front = 0;
int _back = 0;
int _size = 0;
};
template<typename T>
class ListQueue
{
public:
void push(const T& value)
{
_container.push_back(value);
}
void pop()
{
_container.pop_front();
}
T& front()
{
return _container.front();
}
bool empty()
{
return _container.empty();
}
int size()
{
return _container.size();
}
private:
list<T> _container;
};
int main(void)
{
ArrayQueue<int> q;
//ListQueue<int> q;
for (int i = 0; i < 100; ++i)
q.push(i);
while (q.empty() == false)
{
int value = q.front();
q.pop();
cout << value << endl;
}
int size = q.size();
return 0;
}'자료구조 알고리즘' 카테고리의 다른 글
| 그래프 구현 (0) | 2024.05.29 |
|---|---|
| 그래프 기초 (0) | 2024.05.29 |
| 이진 탐색 트리와 균형 이진 트리 (0) | 2024.05.27 |
| BFS DFS 차이 (0) | 2024.05.27 |
| 트리와 그래프 (0) | 2024.05.27 |
