선형 자료 구조

Clear·2023년 12월 2일

선형 자료 구조

자료 사이의 전후 관계가 1:1 인 자료구조

Array

연속적인 메모리 공간 사용

동일한 타입의 데이터

배열 전체에 대한 잦은 할당/해제 메모리 단편화

인덱스 접근이 가능

종류

일반 배열

STL array<_Ty, _Size> 정적 배열

STL vector<_Ty, _Alloc> 동적 배열

List

연속적이지 않은 메모리 공간 사용

포인터를 통한 불연속적인 연결 행태

노드데이터 저장 단위 단위 메모리 할당/해제

데이터들 사이에 삽입/해제가 비교적 편리한 구조

방향에 따른 단·양방향 리스트로 나뉜다.
종류
STL list<_Ty,_Allloc> 양방향
구현
template <class T>
class List
{
public :
	struct Node
	{
		T Data;
		Node* Next;
		// Node * prev; 양방향
	};
private :
	Node* Head;
	// Node* Tail; 양방향
//...
};

Stack

LIFO

종류

STL stack<_Ty, _Container>

구현

#include <vector>
template<class T>
class StackByArray
{
private :
	std::vector<T> Data;
	int Top = -1;
};
template<typename T>
class StackByArray
{
public :
	struct Node
	{
		T Data;
		Node* Next;
	};
private :
	Node* Top;
};

Queue

FIFO

종류

STL queue<_Ty,_Container>

구현

#include <vector>
template<class T>
class QueueByArray
{
private:
	std::vector<T> Data;
	int Front;
	int Rear;
};
template<class T>
class QueueByList
{
public :
	struct Node
	{
		T Data;
		Node* Next;
	};
private :
	Node* Front;
	Node* Rear;
};