개요
Stack의 개념을 다시 review해보자. 스택은 "LIFO"구조를 갖는 자료 구조이다. stack은 메모리공간을 정적으로 설정할 수도 있고 동적으로 할당 받아서 사용할 수도 있다. 그렇다면 메모리 공간을 유연하게 바꾸는 것은 안될까?
예를 들어서 평소에는 사람이 거의 오지않는 식당이 있다고 치자 그런데 설날만 되면 사람들이 몇 백 배씩 늘어난다고 쳐보자 이 상황에서 테이블을 설날 기준에 맞춰서 세팅하면 평소에 적자가 매우 심할 것이고 그렇다고 평소에 맞추자니 설날에 오는 사람들이 아쉽게된다. 이때 좋은 방법은 밖에다가 텐트를 친다던지 해서 테이블 개수를 설날에만 많이 세팅하는 것이다.
우리가 이번에 알아볼 Linked Structure가 이러한 개념에서 출발한다.
Linked Structure(Stack)
정의
우리는 그동안 전체 stack을 한 개의 배열로 고려했다. 그러나 linked structure에선 각각의 item을 single object(Node)로 고려할 것이다. 이들의 관계는 어떻게 정할까?
포인터를 사용하여 다음 노드를 가리키도록 설계를 한다.
이것을 Linked Structure라 부르고 각각의 노드는 값과 다음 노드를 가리키는 포인터를 갖고있다.
struct NodeType {
ItemType value;
NodeType * next;
}NodeType의 크기는 value 크기 + 8byte(포인터 크기 64bit기준) -> int val을 가진 경우 12byte
Node들이 추가되고 사라질 때는 stack과 같이 top에서 push되고 pop된다.
또한 여기서 top을 가리키는 pointer가 추가로 필요하다. 왤까?
컴퓨터는 각 메모리 공간에 접근하기위해 변수 이름을 사용하는데 동적 배열은 이름이 없다.(동적 배열은 이름이 있는 포인터가 가리키는 것일 뿐이다.) 그래서 동적 배열 Item은 pointer로 접근해야한다. 아까 설계했던 linked structure를 보면 첫 번째 노드를 제외한 다른 모든 노드들은 다른 노드들에 의해 가리켜지고 있지만 top을 가리키는 pointer는 없다.
-> 그래서 top Node를 가리키는 pointer가 추가로 필요하다.
생성자를 보면 다음과 같다.
StackType::StackType() {
topPtr = nullptr;
}top을 가리키는 pointer를 처음에 만든 것이다.(아직 push하지 않았기 때문에 nullptr인 상태)
push()
Logical Level
linked structure에서 push가 어떻게 일어나는 지 알아보자.
5 값을 갖고있는 Node를 push하는 상황이다.
먼저 새로운 NodeType을 만든 후 값을 5로 설정해준다.
그리고 새롭게 추가한 NodeType의 next Pointer가 기존의 top에 있던 Node를 가리키도록 한다.
그리고 topPtr이 새로운 NodeType을 가리키도록 한다. 그렇게 해서 최종적으로 만들어지는 구성은 위와같다.
Implementation Level
void StackType::push(ItemType value) {
NodeType* newNode;
newNode = new NodeType;
newNode -> value = new_value;
newNode -> next = topPtr;
topPtr = newNode;
}하나씩 살펴보자.
NodeType* newNode;
newNode = new NodeType;에서 새로운 NodeType인 newNode를 만들었다.
newNode -> value = new_value;에서는 newNode의 value값을 인자로 받아온다.
->의 뜻은 newNode가 가리키는 공간에 있는 value값을 new_value로 바꾼다는 의미이다.
newNode -> next = topPtr;newNode의 next가 기존의 top에 있던 Node를 가리키도록 한다.(topPtr이 원래 기존의 top에 있던 Node를 가리키고 있어서 그걸 그대로 복사 해준것)
topPtr = newNode;topPtr이 새로운 NodeType을 가리키도록 바꾼다.
memory map
아직도 이해가 잘 가지않는다 메모리 맵을 보면서 이해해보자.
newNode는 0x3000에 있고 topNode는 0x2000에 있다. topPtr은 이 주소 0x2000을 갖고있다.
newNode의 next를 0x2000으로 만들어준다.
그 후 topPtr을 0x3000으로 만들어 준다.
isFull()
Logical Level
배열 구조의 stack은 용량이 MAX_ITEMS이기 때문에 full상태인 것을 알 수 있다.
linked structure는 꽉찬 것을 알 수 있을까?
linked structure는 item을 넣는 것이 새로운 동적 할당된 노드를 만들어내는 것이다.
HEAP영역은 무한한 공간이 아니며, Os default HEAP size를 각 프로그램 마다 갖고 있다.
그래서 HEAP이 포화된 상태가 되면 new 구문이 실패하고 exception을 throw한다.
Implementation Level
bool StackType::isFull() const {
NodeType* newNode;
try {
newNode = new NodeType;
delete newNode;
return false;
}
catch (std::bad_alloc exception) {
return true;
}
}
- 꽉 찼는지 확인해보려고 try문 안에 새로운 Node를 만든다.
- isFull = false라면 새로운 Node를 delete후 false를 return한다.
- isFull = true라면 catch문으로 넘어가고 true를 return한다.
pop()
Logical Level
pop을 하는 과정을 살펴보자.
이렇게 생긴 Linked Structure에서 pop을 하면 5가 return될 것이다.
먼저 topPtr을 top Node의 next을 향하게 하면 되는데 문제는 이렇게 하면 top에 접근할 수 있는 포인터가 사라진다는 점이다. 그래서 우리는 먼저 TempPtr을 만들고 top을 가리키도록 한다.
그 후 topPtr이 top의 next를 가리키도록 한 후 tempPtr이 가리키고 있는 Node를 delete해준다.
tempPtr은 포인터 변수이기 때문에 알아서 사라질 것이다.
Implementation Level
ItemType StackType::pop() {
NodeType *tempPtr;
tempPtr = topPtr;
topPtr = topPtr -> next;
delete(tempPtr);
}
- 먼저 topNode를 가리키는 tempPtr을 만든다.
- topPtr이 가리키고 있는 Node의 next를 topPtr에 할당한다.
- tempPtr을 없애준다.
- tempPtr은 local variable이라 알아서 사라진다.
그 외 연산자들
isEmpty()
bool StackType::isEmpty() const {
if (topPtr == nullptr) {
return true;
}
return false;
}topPtr == nullPtr 즉, topPtr이 아무것도 가리키고 있지 않을 때 true
Destructor
StackType::~StackType() {
NodeType *tempPtr = topPtr;
while (tempPtr != nullptr) {
topPtr = topPtr -> next;
delete tempPtr;
tempPtr = topPtr;
}
}
- top을 가리키는 tempPtr을 만들어줌
- topPtr이 topPtr다음 노드를 가리키도록 함
- tempPtr을 delete함
- tempPtr에 topPtr 할당
- tempPtr이 nullptr이 될 때까지 반복함
-> 2번을 3번보다 먼저하는 이유는 만약에 3번을 먼저할 시 next에 대한 정보도 날라가기 때문임
-> delete 헷갈렸었는데 우리는 포인터 변수를 없애는 것이 아니라 동적 할당된 배열을 없애는 것이기 때문에 tempPtr로 없애는 과정이 이상할게 없다.
-> tempPtr이 가리키고있는 것은 배열이 아니라 동적으로 할당된 단일 객체이기 때문에 delete[]가 아닌 delete를 사용하여 해제함
clear()
void StackType::clear() {
~StackType();
}간단하게 destructor을 호출하면 끝이다.
size()
int StackType::size() {
NodeType *tempPtr = topPtr;
int length = 0;
while(tempPtr != nullptr) {
length ++;
tempPtr = tempPtr -> next;
}
return length;
}topPtr부터 시작해서 다음 다음 이동하면서 length를 1씩 증가시켜주다가 nullptr이 되면 length를 return해준다.
사실 size()함수를 따로 변수를 만들어서 구현할 수 있지만 학습 차원에서 이렇게 정의함
시간복잡도
size()함수와 clear(), Destructor는 시간 복잡도가 O(N)이다. 이는 top부터 하나씩 이동하기 때문에 그렇다. 나머지 연산자들의 시간복잡도는 O(1)이다.
Array는 모든 시간 복잡도가 O(1)이다. 그래서 시간복잡도 측면에서는 Array를 사용하는 것이 유리하다고 한다.
Linked Structure(Queue)
정의
이번엔 queue형태의 linked structure를 알아보자.
위 그림과 같이 구현을 한다.
template <class ItemType>
struct NodeType {
ItemType value;
NodeType *next;
}
template <class ItemType>
class QueueType{
private:
NodeType<ItemType> *pFront;
NodeType<ItemType> *pRear;
public:
QueueType();
~QueueType();
void enqueue(ItemType value);
void dequeue(ItemType &value);
void clear();
int size() const;
bool isFull() const;
bool isEmpty() const;생성자
QueueType::QueueType() {
pFront = nullptr;
pRear = nullptr;
}pFront와 pRear가 노드의 처음과 끝을 가리키도록 한다. 생성자엔 nullptr을 넣어준다.
"pFront랑 pRear는 값도 없는데 왜 NodeType<ItemType>이지?" 라고 헷갈렸었는데 이 둘은 그냥 NodeType형 포인터일 뿐임
enqueue()
Logical Level
먼저 새로운 노드를 하나 만들고 노드 값을 설정해준 뒤 next를 nullptr로 설정 해준다.
원래 마지막 노드의 next가 새로운 노드를 가리키도록 한 후 pRear 포인터도 새로운 노드를 가리키도록 한다.
Implementation Level
void QueueType::enqueue(ItemType new_value) {
NodeType *newNode;
newNode = new NodeType;
newNode -> value = new_value;
newNode -> next = nullptr;
pRear -> next = newNode;
pRear = newNode;
- 먼저 새로운 노드 newNode를 만들어준다.
- newNode의 값에 new_value를 넣어주고 next에 nullptr을 넣어준다. (모두 newNode의 멤버 변수에 값을 넣어주는 것임)
- pRear가 가리키는 Node의 next를 newNode로 바꿔준다. (원래는 nullptr)
- pRear가 newNode를가리키도록 한다.
이렇게만 정의하면 끝일까?
문제가 하나 있다. 바로 queue가 비어있을 경우이다.
위와 같이 pFront와 pRear모두 nullptr인 상태에서 pRear -> next = newNode;를 해버리면 pRear가 가리키는 값이 없기 때문에 프로그램이 망가진다.
그래서 위와 같이 !isEmpty()일 때만 pRear -> next = newNode를 정의해준다.
pFront또한 queue가 empty일 때 같이 update해줘야 하므로 최종적으로 다음과 같이 정의한다.
그래서 완성된 코드는 다음과 같다.
void QueueType::enqueue(ItemType new_value) {
NodeType *newNode;
newNode = new NodeType;
newNode -> value = new_value;
newNode -> next = nullptr;
if(isEmpty()) {
pFront = newNode;
}
else {
pRear -> next = newNode;
}
pRear = newNode;isFull()
bool QueueType::isFull() const {
NodeType *newNode;
try {
newNode = new NodeType;
delete newNode;
return false;
}
catch(std::bad_alloc exception) {
return true;
}
}stack에서 했던 것과 동일하게 만들어보고 꽉차면 bad_alloc exception을 던지기 때문에 위와 같이 정의한다.
isEmpty()
bool QueueType::isEmpty() const {
return(pFront == nullptr);
}pFront가 nullptr 즉, 가리키는 값이 없으면 비어있는 상태이다.
dequeue()
Logical Level
stack에서 pop()을 구현했던 것과 마찬가지로 front node를 가리킬 tempPtr을 만들어줘야 한다.
위와 같은 구성이 된다.
그 후 위와 같이 tempPtr이 가리키는 node를 delete해준다.
tempPtr은 지역 변수이기 때문에 자동으로 사라진다.
Implementation Level
void QueueType::dequeue(ItemType &ret_value) {
NodeType *tempPtr;
tempPtr = pFront;
pFront = pFront -> next;
delete tempPtr;
}
- pFront가 가리키는 값을 가리키는 새로운 tempPtr을 만든다.
- pFront가 pFront 다음에 있는 node를 가리키도록 한다.
- tempPtr이 가리키고 있는 노드를 delete해준다.
- tempPtr은 함수가 종료되면서 자동으로 사라진다.
stack과 마찬가지로 2번이 3번보다 앞에있는 이유는 3번이 앞서면 next에 대한 정보가 사라지기 때문이다.
Edge Case
다음과 같이 노드가 하나만 있는 상태에서 dequeue를 한다고 생각해보자.
tempPtr을 만들고 pFront를 앞으로 옮기면 다음과 같아진다.
이 상태에서 tempPtr이 가리키는 값을 delete해주면 다음과 같아진다.
pFront는 nullptr이라 문제가 없지만 pRear는 이미 사라진 동적 배열을 계속 가리키고 있는 상태가 된다. 이를 댕글링 포인터(Dangling Pointer)라 부르며, 메모리 garbage의 정 반대 상황이 되버린다.
이를 해결하기위해 다음과 같이 코드를 추가로 작성해준다.
void QueueType::dequeue(ItemType &ret_value) {
NodeType *tempPtr;
tempPtr = pFront;
pFront = pFront -> next;
delete tempPtr;
if (isEmpty()) {
pRear = nullptr;
}
}그 외 연산자들
Destructor and clear()
QueueType::~QueueType() {
NodeType *tempPtr = pFront;
while (tempPtr != nullprt) {
pFront = pFront -> next;
delete tempPtr;
tempPtr = pFront;
}
pRear = nullptr;
}
void QueueType::clear() {
~QueueType();
}front부터 삭제 삭제... nullptr이 될 때까지
마지막에 pRear = nullptr;잊지 않기
size()
int QueueType::size() {
NodeType *tempPtr = pFront;
int length = 0;
while(tempPtr != nullPtr) {
length++;
tempPtr = tempPtr -> next;
}
return length;
}front부터 nullptr이 될 때까지 length++;
이도 마찬가지로 변수를 이용해서 함수 정의할 수 있는데 학습 차원에서 이렇게 함
시간 복잡도
stack과 마찬가지로 size(), clear(), Destructor만 O(N)이고 나머지는 O(1)이다.
-> 시간 복잡도 측면에선 Array를 사용하는 것이 유리함 (Array는 전부 O(1)이기 때문에)
