[자료구조] Chapter 5. Linked Structures

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

 

Why we need topPtr?

• 모든 변수는 자신의 이름과 memory space를 가짐
• computer는 이런 변수의 이름을 이용해 각 memory space에 접근
• 동적 할당된 memory spaces는 고정된 이름이 존재하지 않음 -> ptr로 가리켜야함
• 메모리 해제 없이 ptr 삭제 -> Garbage (memory leakage) 발생

 

1. LStack 자료구조의 ADT & Implementation

void push(ItemType value)
- new Node 생성
- new Node의 value를 설정
- new Node의 next는 old topPtr 가리킴
- topPtr은 new Node를 가리킴
- edge case: isFull
    ItemType pop();

ItemType pop();
- tempPtr이 old top을 가리키게 함
- topPtr을 old top의 next로 이동
- tempPtr 가리키는 공간 해제
- edge case: isEmpty

void clear();
- destructor 호출

int size() const;
- tempPtr이 nullPtr이 될 때까지 length++
- 최종 length 반환

bool isFull() const;
- newNode를 생성해보고, 실패할 시에 stack이 Full 상태인 것으로 간주 -> true 반환

bool isEmpty() const;
- topPtr이 nullPtr을 가리키면 true 반환

~StackType()
- tempPtr이 nullPtr이 될 때까지 pop 연산

 

2. LStack Implementation in codes

#include "LStack.hpp"
#include <iostream>

void StackType::push(ItemType value) {
    if (isFull()) {
        return;
    }
    
    NodeType * newNode;
    newNode = new NodeType;
    
    newNode -> value = value;
    newNode -> Next = topPtr;
    
    topPtr = newNode;
}

bool StackType::isFull() const {
    NodeType * newNode;
    try {
        newNode = new NodeType;
        delete newNode;
        return false;
    }
    catch (std::bad_alloc exception) {
        return true;
    }
}

ItemType StackType::pop() {
    if (isEmpty()) {
        return 0;
    }
    NodeType * tempPtr;
    tempPtr = topPtr;
    ItemType rtn = tempPtr -> value;
    
    topPtr = topPtr -> Next;
    delete(tempPtr);
    
    return rtn;
}

bool StackType::isEmpty() const {
    return topPtr == nullptr;
}

StackType::~StackType() {
    NodeType * tempPtr = topPtr;
    
    while (tempPtr != nullptr) {
        topPtr = topPtr -> Next;
        delete tempPtr;
        tempPtr = topPtr;
    }
}

void StackType::clear() {
    NodeType * tempPtr = topPtr;
    
    while (tempPtr != nullptr) {
        topPtr = topPtr->Next;
        delete tempPtr;
        tempPtr = topPtr;
    }
}

int StackType::size() const {
    NodeType * tempPtr = topPtr;
    int length = 0;
    
    while (tempPtr != nullptr) {
        length++;
        tempPtr = tempPtr -> Next;
    }
    return length;
}

 

3. Big-O Comparison of Stack Operations

 

4. LQueue 자료구조의 ADT & Implementation

void enqueue(ItemType value);
- make newNode
- set newNode's value as something & next as nullptr
- old qRear's next point to the newNode
- qRear point to the newNode
- edge case: isFull()
- edge case: isEmpty() -> pFront도 newNode를 가리키게 설정

void dequeue(ItemType &value);
- tempPtr 생성 후 qFront point
- old qFront의 next로 qFront 변경
- tempPtr이 가리키는 Node 메모리 공간 해제 (local variable인 tempPtr은 함수 종료와 함께 자동 삭제)
- Edge case: isEmpty() -> qRear도 nullptr를 가리키도록 

void clear();
- tempPtr이 nullPtr이 될 때까지 pop 연산

int size() const;
- qFront에서 시작해서, tempPtr이 nullptr을 가리킬 때까지 이동

bool isFull() const;
- newNode를 생성해보고, 실패할 시에 stack이 Full 상태인 것으로 간주 -> true 반환

bool isEmpty() const;
- qFront가 nullptr를 가리키면 true

 

5. LQueue Implementation in codes

#include "LQueue.hpp"
#include <iostream>

QueueType::QueueType() {
    qFront = nullptr;
    qRear = nullptr;
}

void QueueType::enqueue(ItemType value) {
    if(isFull()) {
        return;
    }
    
    NodeType * newNode;
    newNode = new NodeType;
    
    newNode -> value = value;
    newNode -> next = nullptr;
    
    if(isEmpty()) {
        qFront = newNode;
    } else {
        qRear -> next = newNode;
    }
    qRear = newNode;
}

void QueueType::dequeue(ItemType & ret) {
    NodeType * tempPtr;
    tempPtr = qFront;
    
    qFront = qFront -> next;
    ret = tempPtr -> value;
    delete tempPtr;
    
    if(isEmpty()) {
        qRear = nullptr;
    }
}

bool QueueType::isFull() const {
    NodeType * newNode;
    try {
        newNode = new NodeType;
        delete newNode;
        return false;
    }
    catch (std::bad_alloc exception) {
        return true;
    }
}

bool QueueType::isEmpty() const {
    return (qFront == nullptr);
}

QueueType::~QueueType() {
    NodeType * tempPtr = qFront;
    
    while(tempPtr != nullptr) {
        qFront = qFront -> next;
        delete tempPtr;
        tempPtr = qFront;
    }
    qRear = nullptr;
}

void QueueType::clear() {
    NodeType * tempPtr = qFront;
    
    while(tempPtr != nullptr) {
        qFront = qFront -> next;
        delete tempPtr;
        tempPtr = qFront;
    }
    qRear = nullptr;
}

int QueueType::size() const {
    NodeType * tempPtr = qFront;
    int length = 0;
    
    while (tempPtr != nullptr) {
        length++;
        tempPtr = tempPtr -> next;
    }
    
    return length;
}

 

6. Big-O Comparison of Queue Operations