[C++] 자료구조 – SinglyLinkedList 코드

요즘 자료구조를 다시 복습하고있다. 학부때 자료구조를 한번 공부하긴 했었지만, 워낙.. 시험 위주로 코딩했더니 완전히 내것으로 만들지 못한 것 같다. 뇌를 자극하는 알고리즘이란 책을 사서 읽고있는데 설명은 꽤나 괜찮은 것 같으나 개인적으로 코드들이 맘에 안든다. 그 책은 C언어를 사용하는데 C언어 치고 naming convention도 맘에안들고 해서 그냥 내가 직접 C++ 로 책에 나오는것들을 구현하면 더 효과적으로 공부 할 수 있을 것 같다.

자료구조는 솔직히 아직까진 강좌를 쓸 정도로 자신 있지 않고, 쓰더라도 남들이 쓴것들을 인용한거 일거라서 강좌작성은 생략하고 코드 설명 위주로만, 내가 복습 할 용도로 작성해야겠다.

이 코드에는 Node 클래스와 SinglyLinkedList 클래스가 있다. Node 클래스에는 create 와 destroy 메소드가 static으로 선언되어 있는데 그 이유는 메모리를 아끼기 위함이다.

SinglyLinkedList 클래스는, 싱글링크드리스트에서 필요한 메소드들이 구현되어있다.

딱히 복잡한 코드는 없어서 설명 할 부분이 없다.

이 클래스에 구현했어야 했지만 하지 않았던 부분은 destructor.. 자유 메모리를 사용하기때문에 객체가 destruct 될 때 만들어져있는 node 들을 delete 해야 하는데, 글쓰면서 생각이 났는데 지금 구현하기 귀찮다.

다음 작성 할 DoublyLinkedList 에선 구현하도록 해야겠다.

/**
    SinglyLinkedList.cpp
    @author: velopert
*/

#include <iostream>

using namespace std;


/*
 * Node Class
 */

class Node {
    public:
        int data;
        Node* nextNode;
        static Node* create(int data);
        static void destroy(Node* node);
};

Node* Node::create(int data) {
    Node* node = new Node;
    node->data = data;
    node->nextNode = NULL;
    return node;
}

void Node::destroy(Node *node) {
   delete node;
}


/*
 * SinglyLinkedList Class
 */

class SinglyLinkedList {
    public:
        Node* head;

        static Node* createNode(int data);
        static void deleteNode(Node* node);
        void appendNode(Node* node);
        Node* getNodeAt(int loc);
        void removeNode(Node* node);
        void insertAfter(Node* current, Node* node);
        void print();
        int getLength();
        SinglyLinkedList();
};

void SinglyLinkedList::appendNode(Node* node) {
    if(this->head == NULL) {
        this->head = node;
    } else {
        Node* current = this->head;
        while(current->nextNode != NULL) {
            current = current->nextNode;
        }
        current->nextNode = node;
    }
}

Node* SinglyLinkedList::getNodeAt(int loc) {

    Node* current = this->head;

    while(loc--) {
        if(!current) {
            return NULL;
        }
        current = current->nextNode;
    }

    return current;
}

void SinglyLinkedList::removeNode(Node* node) {
    if(this->head == node) {
        this->head = node->nextNode;
    } else {
        Node* current = this->head;
        while(current && current->nextNode != node) {
            current = current->nextNode;
        }

        if(current) current->nextNode = node->nextNode;
    }

    Node::destroy(node);
}

void SinglyLinkedList::insertAfter(Node* current, Node* node) {
    node->nextNode = current->nextNode;
    current->nextNode = node;
}

void SinglyLinkedList::print() {
    if(this->head == NULL) {
        cout << "LinkedList is Empty" << endl;
        return;
    }
    Node* current = this->head;
    cout << "LinkedList: ";
    while(current != NULL) {
       cout << current->data << " -> ";
       current = current->nextNode;
    }
    cout << "END" << endl;
}

int SinglyLinkedList::getLength() {
    int length = 0;

    if(!this->head) return length;

    Node* current = this->head;
    while(current){
        length++;
        current = current->nextNode;
    }

    return length;
}

SinglyLinkedList::SinglyLinkedList() {
    this->head = NULL;
};


/*
 * testing
 */
int main() {
    Node* node = Node::create(10);
    cout << node->data << endl;
    Node::destroy(node);


    SinglyLinkedList sll;
    for(int i =0; i < 10; i++) {
        sll.appendNode(Node::create(i));
    }

    sll.print();

    Node* result = sll.getNodeAt(1);
    cout << result->data << endl;

    sll.removeNode(result);
    sll.print();

    sll.removeNode(sll.getNodeAt(0));
    sll.print();

    sll.insertAfter(sll.getNodeAt(1), Node::create(10));
    sll.print();

    cout << "Length: " << sll.getLength() << endl;
}