자료구조 - Linked List(Stack & Queue)

배열을 사용하여 구현을 할 경우 해당 배열의 크기를 미리 정해줘야 하기 때문에 만약 사전에 설정한 크기보다 큰 영역이 필요할 경우 문제가 생기고, 사전에 너무 큰 영역을 할당한다면 메모리 효율이 떨어지게 된다.

 

따라서 Linked List를 사용하면 이러한 문제를 해결할 수 있는데 Linked list는 필요에 따라 메모리를 할당하고 해제할 수 있어서, 배열과 달리 크기가 고정되어 있지 않는다.

 

그리고 Linked list에서 노드의 삽입과 삭제는 단순히 포인터를 변경하면 되기 때문에 기존 배열에서 삽입이나 삭제를 위해 요소들을 이동시켜야 하는 부분을 없앨 수 있다.

 

또한 Linked list는 필요한 데이터만큼만 메모리를 사용하여 배열과 달리 사용하지 않는 메모리 공간이 생기지 않아 메모리 사용이 효율적이다.

 

기본적인 Linked list는 다음과 같이 생겼다.

 

topPtr은 가장 앞의 노드의 주소를 가리키고 있고, info에는 해당 노드의 값을 포함한다.

 

그리고 Next는 해당 노드에 연결된 다음 노드의 주소를 가리키고 있고, 마지막 노드의 경우는 끝이기 때문에 가리키는 값이 없다.

 

이제 이러한 Linked List로 stack을 다시 구현해 보면 처음에 stack의 제일 위를 가리키는 포인터가 nullptr이었다가 원소가 삽입되면 new로 생성된 해당 원소의 위치를 가리키게 된다.

 

그리고 그다음 원소가 추가되면 stack은 위로 원소가 추가되고 포인터는 항상 가장 위의 원소를 가리켜야 하기 때문에 추가된 원소의 주소로 포인터가 이동하게 되고 추가된 원소에서 기존의 top이었던 주소를 연결하여 Linked 된 List를 구성해야 한다.

 

그리고 Pop은 현재 가장 위를 가리키고 있는 포인터를 해당 포인터에서 가리키고 있는 주소를 가리키게 바꿔주고 delete로 메모리에서 해제해 주면 된다.

 

이러한 내용을 바탕으로 Stack을 Linked List로 다시 구현해 보면 다음과 같이 짤 수 있다.

class StackType {
    NodeType* topPtr;
public:
    StackType();
    ~StackType();
    bool IsFull() const;
    bool IsEmpty() const;
    void Push(ItemType item);
    void Pop();
    ItemType Top();
};

StackType::StackType() {
    topPtr = NULL;
}

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

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

bool StackType::IsEmpty() const {
    return (topPtr == NULL);
}

void StackType::Push(ItemType newItem) {
    if (IsFull())
        throw FullStack();
    else {
        NodeType* location;
        location = new NodeType;
        location->info = newItem;
        location->next = topPtr;
        topPtr = location;
    }
}

void StackType::Pop() {
    if (IsEmpty())
        throw EmptyStack();
    else {
        NodeType* tempPtr;
        tempPtr = topPtr;
        topPtr = topPtr->next;
        delete tempPtr;
    }
}

 

그리고 Linked List로 queue을 다시 구현해 보면 스택과 다르게 처음과 끝을 가리키는 포인터 2개가 존재해야 한다.

 

이때 만약 큐에 새로운 원소를 삽입할 경우 new로 새로운 노드를 만들어 준 후에 새로 만들어진 노드에 값을 넣고 마지막이기 때문에 다음 가리키는 주소는 NULL로 설정해 준다.

 

그리고 기존에 마지막 노드였던 qRear가 가리키고 있는 노드의 다음 주소로 새로 만든 노드의 주소를 입력해 준다.

 

그 후 qRear를 새로 만들어진 노드의 위치로 옮기면 Enqueue를 구현할 수 있다.

 

이를 그림으로 표현하면 다음과 같다.

이러한 Linked List로 만들어진 큐의 Enqueue에서 가장 문제가 되는 부분은 처음 원소가 없던 상태에서 원소를 집어넣을 때인데, 이때는 qFront와 qRear가 가리키는 값이 모두 null이었으므로 예외적으로 이때만 qFront가 가리키는 값을 새로 생성된 노드로 설정해 주면 된다.

 

이제 반대로 Dequeue를 하는 과정을 살펴보면 qFront가 가리키고 있는 노드의 다음 주소를 qFront로 다시 설정해주고, 이전의 front였던 부분은 delete를 통해 메모리에서 제거해주면 된다.

Dequeue를 하면서 가장 문제되는 부분은 제일 마지막 원소를 제거해줄때이다.

 

이때는 qFront가 가리키고 있는 노드의 다음 주소가 NULL이기 때문에 모든 큐의 값이 없어야 한다.

 

따라서 qRear가 가리키고 있던 값은 없는 값이므로 이때를 한정해서 qRear이 가리키고 있는 노드도 NULL로 설정해주면 된다.

 

이러한 내용을 바탕으로 Queue를 Linked List로 다시 구현해 보면 다음과 같이 짤 수 있다.

class QueType {
    NodeType* front;
    NodeType* rear;
public:
    QueType();
    QueType(int max);
    ~QueType();
    void MakeEmpty();
    bool IsEmpty() const;
    bool IsFull() const;
    void Enqueue(ItemType newItem);
    void Dequeue(ItemType& item);
    void ReplaceItem(ItemType oldItem, ItemType newItem);
};

struct NodeType {
    ItemType info;
    NodeType* next;
};

QueType::QueType() {
    front = NULL;
    rear = NULL;
}

void QueType::MakeEmpty() {
    NodeType* tempPtr;
    while (front != NULL) {
        tempPtr = front;
        front = front->next;
        delete tempPtr;
    }
    rear = NULL;
}

QueType::~QueType() {
    MakeEmpty();
}

bool QueType::IsFull() const {
    NodeType* location;
    try {
        location = new NodeType;
        delete location;
        return false;
    }
    catch (bad_alloc exception) {
        return true;
    }
}

bool QueType::IsEmpty() const {
    return (front == NULL);
}

void QueType::Enqueue(ItemType newItem) {
    if (IsFull())
        throw FullQueue();
    else {
        NodeType* newNode;
        newNode = new NodeType;
        newNode->info = newItem;
        newNode->next = NULL;
        if (rear == NULL)
            front = newNode;
        else
            rear->next = newNode;
        rear = newNode;
    }
}

void QueType::Dequeue(ItemType& item) {
    if (IsEmpty())
        throw EmptyQueue();
    else {
        NodeType* tempPtr;
        tempPtr = front;
        item = front->info;
        front = front->next;
        if (front == NULL)
            rear = NULL;
        delete tempPtr;
    }
}

void QueType::ReplaceItem(ItemType oldItem, ItemType newItem) {
    NodeType* location = front;
    while (location != NULL) {
        if (location->info == oldItem) {
            location->info = newItem;
        }
        location = location->next;
    }
}