::public/자료구조

LinkedList 구현.

해맑은욱 2019. 8. 21. 22:57
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
using namespace std;
 
class MyNode
{
private:
    MyNode* link;
    int data;
public:
    MyNode(int n) : data(n), link(NULL)    {}
    ~MyNode() {}
    MyNode* getLink()
    {
        return link;
    }
    void setLink(MyNode* node)
    {
        if (node != NULL)
        {
            link = node;
        }
    }
    
    void insertNext(MyNode* next)
    {
        if (next != NULL)
        {
            next->setLink(link);
            link = next;
        }
    }
    MyNode* removeNext()
    {
        MyNode* next = link;
        if(next != NULL)
            link = next->getLink();
        return next;
    }
    bool hasData(int n)
    {
        return data == n;
    }
    void display()
    {
        cout << data << " ";
    }
};
 
#include "MyNode.h"
 
class MyLinkedList
{
private:
    MyNode head;
public:
    MyLinkedList() : head(0) {}
    ~MyLinkedList() { clear(); }
    void insert(int pos, MyNode* node)
    {
        MyNode* prev = getElement(pos - 1);
        if (prev != NULL)
        {
            node->setLink(prev->getLink());
            prev->setLink(node);
        }
    }
    MyNode* remove(int pos)
    {
        MyNode* prev = getElement(pos - 1);
        if (prev != NULL)
        {
            prev->removeNext();
        }
    }
    MyNode* getElement(int pos)
    {
        MyNode* node = &head;
        for (int i = -1; i < pos; i++, node = node->getLink())
        {
            if (node != NULL)
                return node;
            else
                break;
        }            
    }
    bool isEmpty()
    {
        return head.getLink() == NULL;
    }
    MyNode* find(int n)
    {
        for (MyNode* p = head.getLink(); p != NULL; p = p->getLink())
        {
            if (p->hasData(n))
                return p;
            else
                return NULL;
        }
    }
    void replace(int pos, MyNode* node)
    {
        MyNode* prev = getElement(pos - 1);
        if (prev != NULL)
        {
            delete prev->removeNext();
            prev->insertNext(node);
        }
    }
    int size()
    {
        int count = 0;
        for (MyNode* p = head.getLink(); p != NULL; p = p->getLink())
        {
            count++;
        }
        return count;
    }
    void clear()
    {
        while (!isEmpty())
        {
            remove(0);
        }
    }
    void display()
    {
        cout << "전체 리스트 : ";
        for (MyNode* p = head.getLink(); p != NULL; p = p->getLink())
        {
            p->display();
        }
        cout << "\n";
    }
};
cs