선형 자료구조는 자료를 순차적으로 나열한 형태이고, 많이 사용된다.
- 배열
- 연결 리스트
- 스택/큐
이와 반대로 비선형 자료구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태이다.
예를 들어 파일 탐색, 길 찾기 등은 일대일관계가 아니므로 비선형 자료구조를 활용해야 한다.
- 트리
- 그래프
이 포스트에서는 연결 리스트, 동적 배열, 스택&큐 에 대해서 살펴본다.
연결 리스트 🔗
-
연속되지 않은 메모리를 사용한다.
-
head,tail을dummy노드로 만들어주면 구현이 쉬운 편이다. 그림을 그리며 이해하면 좋다. -
장점 ⭐️
- 중간 삽입 / 삭제가 빠르다. (위치를 기억할때에만! 양옆을 연결해주거나 삭제해주면 되기 때문이다)
- 그래서
Insert,Remove함수가 중요하다.
-
단점 ⭐️
- 위치를 기억하지 않고는 느리게 동작한다
- 임의 접근이 (Random Access) 불가하다
양방향 연결리스트를 구현한 아래의 코드를 보며 자세히 살펴보자!
#pragma once
#include <iostream>
using namespace std;
class Node
{
// typedef int T; // 옛 문법
using T = int; // 요즘 문법! 추후에 템플릿을 적용해보자
public: // 생성자
Node(int data) : data(data), prev(nullptr), next(nullptr) { }
public:
T data;
Node* prev; // 포인터는 하나의 주솟값에 불과하다
Node* next;
};
class List // 노드(방)들로 이루어진 리스트
{
public:
// [dummy]<->[dummy]
// [head] [tail]
List()
{
_head = new Node(0); // dummy
_tail = new Node(0); // dummy
_head->next = _tail;
_tail->prev = _head;
}
// 리스트의 모든 노드를 삭제하는 역할을 한다.
// 이를 통해 동적으로 할당된 모든 노드가 적절하게 해제되고 메모리 누수를 방지한다.
~List()
{
Node* node = _head; //_head 에서부터 시작하여 리스트의 첫 번째 노드를 가리키는 포인터 node 를 생성
while (node) // node 가 nullptr 가 될 때까지 반복하겠다. 즉, 리스트의 끝까지 탐색하겠다.
{
// 삭제를 바로 하진 못하고 두 단계에 걸쳐서 삭제해준다
Node* deleteNode = node; // 현재 노드를 삭제할 노드로 지정
node = node->next; // (커서 역할) node 포인터가 다음 노드를 가리키도록 포인터를 업데이트한다
delete deleteNode; // delete 연산자를 사용하여, deleteNode 포인터가 가리키는 노드를 삭제한다. 이는 메모리에서 해당 노드를 해제하는 역할이다.
}
}
// 원하는 임의의 (index의) 노드를 get 하는 함수
// [dummy]<->[1]<->[2]<->[3]<->[dummy]
// [head] [tail]
// 특정 노드 위치가 저장이 되어 있을 때 라는 조건이 있다는 가정하에 O(1) 에 가능해진다
Node* 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;
}
// [dummy]<->[1]<->[2]<->[3]<->[dummy]
// [head] [tail]
void Print()
{
Node* node = _head->next; // 커서 역할을 하는 노드
while (node != _tail) // 더미는 출력하지 않는다
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
// [node]
// [dummy]<->[nextNode]<->[2]<->[3]<->[dummy]
// [head] [tail]
Node* AddAtHead(int data)
{
Node* node = new Node(data);
Node* nextNode = _head->next;
node->next = nextNode;
nextNode->prev = node;
_head->next = node;
node->prev = _head;
return node;
}
// [node]
// [dummy]<->[1]<->[2]<->[prevNode]<->[dummy]
// [head] [tail]
Node* AddAtTail(int data)
{
Node* node = new Node(data);
Node* prevNode = _tail->prev;
prevNode->next = node;
node->prev = prevNode;
node->next = _tail;
_tail->prev = node;
return node;
}
// [node]
// [dummy]<->[prevNode]<->[posNode]<->[dummy]
// [head] [tail]
// 중간 삽입,삭제가 항상 빠르다는 것이 아니라 posNode 이렇게 특정 위치를 기억하고 있을 때에만 뾰롱- 빠르게 처리할 수 있다는 것이다.
void Insert(Node* posNode, int data) ⭐️
{
Node* node = new Node(data);
Node* prevNode = posNode->prev;
preNode->next = node;
node->prev=prevNode;
node->next=posNode;
posNode->prev = node;
}
// [node]
// [dummy]<->[prevNode]<-><->[nextNode]<->[dummy]
// [head] [tail]
Node* Remove(Node* node) ⭐️ //삭제하고 싶은 노드를 node로 넘겨주기
{
Node* prevNode = node->prev;
Node* nextNode = node->next; // 한단계 거쳐서~
prevNode->next = nextNode;
nextNode->prev = prevNode;
delete node;
return nextNode;
}
private:
Node* _head = nullptr;
Node* _tail = nullptr;
};
동적 배열 🏢
배열
동적 배열을 살펴보기 전에 보통의 배열을 구현하는 방법을 먼저 살펴보자!
#pragma once
#include <assert.h>
class Array
{
using T = int; // 추후에 템플릿으로 변경해주자!
public:
explicit Array(int capacity = 100) : _capacity(capacity)
{
_buffer = new T[capacity]; // 용을 정해주기
}
~Array()
{
delete[] _buffer;
}
void push_back(const T& data)
{
if (_size == _capacity)
return;
_buffer[_size] = data;
_size++;
}
/* 임의접근 */
T& operator[](int index)
{
assert(index >= 0 && index < _size); // 조건에 해당하지 않으면 바로 크래시
return _buffer[index];
}
int size() { return _size; }
int capacity() { return _capacity; }
private:
T* _buffer = nullptr; // 실제로 정보를 담는 공간
int _size = 0; // 실제 요소들로 채워진 공간. push_back 으로 채워진 공간
int _capacity = 0; // 용량. 처음에 할당한 공간의 크기
};동적 배열
앞에서 살펴본 보통의 배열에 이전 기능 이 추가된 배열이다.
capacity란? 용량!
동적 배열 할당 정책
-
실제로 사용할 공간보다 많이, 여유분을 두고
capacity를 (대략 1.5 ~ 2배) 늘린다. -
증설 작업을 커지는 쪽으로는 허용해주나, 작아지는 쪽으로는 불가능하다.
-
장점
- 유동적인 배열, 추가 이사 횟수를 최소화
#pragma once
#include <assert.h>
class Vector
{
using T = int;
public:
explicit Vector() { } // 표준 vector 는 작게 시작해서 빠르게 증설되도록 설계되어있다
~Vector()
{
if (_buffer)
delete[] _buffer;
}
// 데이터를 모두 날려주기
// 이 때, 이미 늘어난 capacity 는 줄어들지 않고, size 만 줄어든다 ⭐️
void clear()
{
// 가라 코드
if (_buffer)
{
delete[] _buffer;
_buffer = new T[_capacity];
}
_size = 0;
}
// 데이터를 뒤에 밀어넣기
void push_back(const T& data)
{
// 이 부분이 제일 핵심 ⭐️
if (_size == _capacity)
{
// 증설 작업
int newCapacity = static_cast<int>(_capacity * 1.5);
if (newCapacity == _capacity)
newCapacity++;
reserve(newCapacity);
}
// 데이터 저장
_buffer[_size] = data;
// 데이터 개수 증가
_size++;
}
// 맨 뒤부터 데이터를 꺼내기
void pop_back()
{
// TODO: 소멸
_size--;
}
// 마지막 데이터를 살펴보기
T& back()
{
return _buffer[_size - 1];
}
void resize(int size) //정확하게 특정 사이즈가 되도록 우리가 정해주는 것
{
//TODO
reserve(size);
_size = size;
}
/* 증설, 이전 */
void reserve(int capacity)
{
if (_capacity >= capacity) // 현재 capacity 가 요청된 capacity 이상이면
return;
_capacity = capacity; // 증설 작업
T* newData = new T[_capacity];
for (int i = 0; i < _size; i++) // 데이터 복사
newData[i] = _buffer[i];
if (_buffer)
delete[] _buffer; // 원래 사용하던 공간을 삭제
_buffer = newData; // 교체
}
T& operator[](int index)
{
assert(index >= 0 && index < _size); // 조건에 해당하지 않으면 크래시
return _buffet[index];
}
int size() { return _size; }
int capacity() { return _capacity; }
private:
T* _buffer = nullptr; // 데이터가 위치해있는 공간
int _size = 0; // 몇개의 데이터를 들고있는지
int _capacity = 0; // 총 할당된 공간이 얼마나 되는지
};언제 어디서 쓸 수 있을까? 💡
비교해보기
배열 🆚 동적 배열
-
사이즈가 고정되어서 변경될 일이 없다면 : 그냥 배열을 활용하면 된다.
-
그러나 배열만 생각해야 하는 경우는 사실 많이 없을 것이다.
-
커스터마이징 (로비에서 캐릭터를 만들 때)
-
인벤토리 칸이 변경될 일이 없을 때
-
동적 배열 🆚 연결 리스트
-
동적 배열은 뭉쳐있어서 캐시로 작업이 가능해서 빠르다.
-
반면, 연결 리스트는 타고타고 가다보니 더 느린 편이다. 그래서 동적 배열이 더 많이 사용된다.
-
단, 중간 삽입 / 삭제 는 연결 리스트로 구현하는 것이 나은 경우가 많다.
-
그 예로 대기열에서 중간에 누군가 바로 빠져야 할 때,
-
또는 대기열에서 중간에 바로 넣어야 할 때이다.
-
-
참고로 C# 에서는 동적 배열이
list, 연결 리스트가linked list이다.
시간 복잡도
Big-O 표기법 2단계 (O 는 Order Of 라고 읽는다)
-
대장만 남긴다.
-
영향력이 가장 큰 대표 항목만 남기고 삭제한다.
-
상수를 무시한다.
-
STL Vector
-
삽입 / 삭제
-
시작
O(N)// 뒤로 밀려나는 아이들 -
중간
O(N/2)->O(N)// 뒤로 밀려나는 아이들 -
끝
O(1)// 상수 시간에 가능
-
-
임의의 index 접근
O(1)// 상수 시간에 가능
STL List
-
삽입 / 삭제
-
시작
O(1)// 상수 시간에 가능 -
중간
O(1)// 반드시 우리가 이 위치를 기억하고 있을 때만 빠르다. 그것도 양방향일때! 단방향 연결 리스트라면 나뿐만 아니라 앞,뒤 두 개를 더 알고 있어야 하겠지 -
끝
O(1)// 상수 시간에 가능
-
-
임의의 index 접근
O(N)// 타고 타고 들어간다
스택 🪣, 큐 💉
큐의 예시
- 대기열
스택의 예시
- UI팝업
- 취소 기능 (뒤로 돌아가기)
스택
스택의 특성상 vector로 만드는 것이 편할 것이다
pop 을 두 단계로 만든 이유,
pop을 함과 동시에 return을 하면 안되는 이유:
- cpp 컨셉상 하는 중간에 에러가 나는 경우에는 메모리 해제가 안될 수도 있어서였다.
또한 push 에서 const & 을 사용하는 이유:
-
매개변수를 상수로 선언함으로써 함수 내에서의 의도치 않은 값 변경을 방지합니다.
-
참조를 사용함으로써 값의 복사를 피하고 성능을 개선합니다.
-
따라서, push 함수의 매개변수가 const & value로 선언되어 있으므로, 해당 함수는 인자로 전달된 값을 변경하지 않고 읽기만 하는 용도로 사용될 것을 의도하고 있습니다.
# pragma once
# include "Vector.h"
template<typename T>
class Stack
{
public:
void push(const & value)
{
_container.push_back(value);
}
void pop()
{
_container.pop_back();
}
T& top()
{
return _container.back();
}
bool empty() { return size() > 0; }
int size() { return _container.size(); }
private:
Vector<T> _container;
};
큐
-
FIFO
-
큐는 어떤 템플릿으로 만드는 것이 효율적일까?
-
배열로 큐를 구현할 때, 요소를 저장할 때마다 배열의 끝에 추가하고, 제거할 때마다 배열의 앞쪽을 비워나가는 방식을 사용할 수 있다.
-
다음 코드의 의미? _front = (_front + 1) % _container.size();
-
push, pop 함수에서 위의 문장처럼 순환적인 인덱스 갱신을 하는 이유는, 큐가 배열로 구현되었을 때, 배열의 처음과 끝을 연결하여 원형 형태로 사용하기 위함이다.
# pragma once
# include "Vector.h"
// [front/back][][][][][][][][][]
// [front][1][2][back][][][][][][][]
template<typename T>
class Queue
{
public:
Queue()
{
_container.resize(100);// 큐의 기본 사이즈를 100 으로 설정
}
void push(const T& value) // 큐에 요소를 추가하는 함수
{
// TODO : 다 찼는지 체크
if (_size == _container.size())
{
// 크기를 늘리거나 오버플로우 처리 등을 수행할 수 있음
}
_container[_back] = value; // 큐의 뒤쪽에 값을 추가
_back = (_bak + 1) % _container.size(); // 뒤쪽 인덱스를 갱신하여 순환적으로 요소를 저장
_size++;
}
void pop() // 큐의 첫 번째 요소를 제거하는 함수
{
_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; // 큐의 현재 크기
};
