algorithms/linkedlist.cpp at master · ngochaibui/algorithms · GitHub

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// ho ten :Bui Ngoc Hai


#include<iostream>
#include<assert.h>
using namespace std;

template<class item>
class node{
    private:
        item data;
        node* next;
    public:
        node();
        void setData(item x);
        item getData();
        void setNext(node* p);
        node* getNext();
        int length();
        node* getMax();
        node* element(int index);       // access an element
        void insert(int index,item x);
        void append(item x);
        void del(int index);            // delete an element
        void show();                    // list all elements
};


template<class item>
node<item>::node()
{
    next=NULL;
};
//setData
template<class item>
void node<item>::setData(item x)
{
    this->data = x;
};
//getData
template<class item>
item node<item>::getData()
{
    return this->data;
};
//setNext
template<class item>
void node<item>::setNext(node* p)
{
    this->next = p;
};
//getNext
template<class item>
node<item>* node<item>::getNext()
{
    return this->next;
};

//getMax
template<class item>
node<item>* node<item>::getMax()
{
    node* p = this;
    node* q=p;
    while(p!=NULL){
          if(q->data < p->data)q=p;
          p = p->next;
    }
    return q;
};
//element
template<class item>
node<item>* node<item>::element(int index)
{
    node* p = this;
    assert(index<this->length() && index>=0);
    for(int i=0;i<index;i++){
        p=p->next;
    }
    return p;
};
//insert
template<class item>
void node<item>::insert(int index,item x)
{
    assert(index<=this->length() && index>=0);
    node* q = new node;
    q->data =x;
    if(index>0){
        node* p = this->element(index-1);
        q->next = p->next;
        p->next = q;
    }else if(index==0){
                q->next = this->next;
                this->next = q;
                item t = this->data;
                this->data = q->data;
                q->data = t;
          }
};
//append
template<class item>
void node<item>::append(item x)
{
    this->insert(this->length(),x);
};
//del
template<class item>
void node<item>::del(int index)
{
    node* p = this->element(index-1);
    node* q = this->element(index);
    p->next = q->next;
    delete q;
};
//show
template<class item>
void node<item>::show()
{
    cout<<" All the elements are : ";
    node* p = this;
    while(p!=NULL){
        cout<<" "<<p->data;
        p=p->next;
    }
    cout<<endl;
};


//length
template<class item>
int node<item>::length()
{
    int x=0;
    node* p=this;
    while(p!=NULL){
         x++;
         p=p->next;
    }
    return x;
};
int main()
{

    node<int> *head = new node<int>;
    head->setData(1);
    head->append(2);
    head->append(3);
    head->getNext()->append(4);
    head->show();
    cout<<" Length : "<<head->length()<<endl;
    cout<<" Max : "<<head->getMax()->getData()<<endl;
    cout<<" Second element : "<<head->element(1)->getData()<<endl;
    head->insert(0,9);
    cout<<" After insert "<<endl;
    head->show();
    head->del(3);
    cout<<" After delete"<<endl;
    head->show();

    return 0;
}