[자료구조]Singly Linked List - 단순연결리스트 사용

Node 클래스

#pragma once
#include <iostream>
 
//단순연결리스트에 사용되는 노드. 헤드포인터가 아니라 헤드 노드로 사용함.
class Node
{
private:
    Node* link;
    int data;
public:
    Node(int val = 0) :data(val) { link = NULL; }
    Node* getlink() { return link; }
    void setlink(Node* next) { link = next; }
    void display() { printf(" <%2d>", data); }
    bool hasdata(int val) { return data == val; }//find()를 위함.
 
    //노드를 다음 위치에 삽입
    void insertnext(Node* n) {
        if (n != NULL) {
            n->link = this->link;
            this->link = n;
        }
    }
 
    //다음 노드를 삭제
    Node* deletenext() {
        Node* removed = this->link;
        if (removed != NULL) {
            this->link = removed->link;
        }
        return removed;
    }
};

SinglyLinkedList 클래스

#pragma once
#include "Node.h"
 
class SinglyLinkedList
{
private:
    Node org;
public:
    SinglyLinkedList() :org(0) {} //헤드노드를 사용함. 헤드노드는 값이 0임.
    ~SinglyLinkedList() { clear(); }
    void clear() { while (!isEmpty()) remove(0); }
    bool isEmpty() { return getHead() == NULL; }
    Node* getHead() { return org.getlink(); } //헤드노드의 링크를 가져옴.
 
    //리스트안의 노드의 개수를 세는 함수.
    int size() {
        int sizeofList = 0;
        for (Node* p = getHead(); p != NULL; p = p->getlink()) {
            sizeofList++;
        }
        return sizeofList;
    }
 
    //연결리스트로 구현한 리스트에서 가장 중요한 함수. 단순연결리스트에서는 앞의 상황은 알수 없고 뒤의 노드만 조작할 수 있기때문에
    //getEntry(pos-1)를 통해 조작하고자 하는 노드 하나 앞의 노드에 접근한 후 노드클래스에서 정의한 함수를 사용해서 삽입, 삭제등을 함.
    Node* getEntry(int pos) {
        Node* n = &org;
        for (int i = -1; i < pos; n = n->getlink(), i++) //헤드노드의 인덱스 == -1
            if (n == NULL) break;
        return n;
    }
 
    void insert(int pos, Node* n) {
        Node* prev = getEntry(pos - 1);
        if (prev != NULL)
            prev->insertnext(n);
    }
 
    Node* remove(int pos) {
        Node* prev = getEntry(pos - 1);
        if (prev != NULL) {
            return prev->deletenext();
        }
        return prev;
    }
 
    void display() {
        printf("[전체 항목 수 =%2d", size());
        for (Node* p = getHead(); p != NULL; p = p->getlink())
            p->display();
        printf("\n");
    }
 
    bool find(int item) {
        for (Node* p = getHead(); p != NULL; p = p->getlink())
            if (p->hasdata(item))
                return true;
        return false;
    }
 
    void replace(int pos, Node* p) {
        Node* prev = getEntry(pos - 1);
        prev->insertnext(p);
        p = getEntry(pos+1);
        
    }
};