Link List In C++

1: #include <stdio.h>
2: #include <iostream>
3: 
4: using namespace std;
5: 
6: class linkList
7: {
8:   typedef struct node
9:   {
10:     struct node *next;
11:     int data;
12:     node():next(NULL),data(-1){}
13:   }listNode;
14:   listNode *head;
15:   listNode *end;
16:   int m_nSize;
17: public:
18:   linkList(int size = 0);
19:   int insert(int data);
20:   //how many times find is in the list
21:   int count(int find);
22:   int getNth(int index);//index starting from 0
23:   //removes all the nodes, frees and set head null
24:   void deleteList();
25:   //pop the head, changes the head
26:   int pop();
27:   //inser data at nth index
28:   int insertAtNth(int index,int data);
29:   int sortedInsert(int data);
30:   void display();
31: };
32: 


33: linkList::linkList(int size):head(NULL),end(NULL),m_nSize(0)
34: {
35:   for(int i = 0;i < size ;i++)
36:     insert(i);
37:   for(int i = 0;i < size ;i++)
38:     insert(i);
39: }
40: 
41: void linkList::display()
42: {
43:   listNode *temp = head;
44:   while(temp)
45:   {
46:     cout<<temp->data<<"->";
47:     temp = temp->next;
48:   }
49:   cout<<endl;
50: }
51: 
52: //will not insert duplicates
53: int linkList::sortedInsert(int data)
54: {
55:   listNode *newNode = new listNode;
56:   newNode->data = data;
57:   
58:   //find the positon based on the data
59:   listNode *temp = head;
60:   int index = 0;
61:   while(temp)
62:   {
63:     if(data < temp->data)
64:       break;
65:     
66:     temp = temp->next;
67:     index++;
68:   }
69:   insertAtNth(index,data);
70: }
71: 
72: //end will move, inserting at the end
73: int linkList::insert(int data)
74: {
75:   listNode *newNode = new listNode;
76:   //newNode->next = NULL;
77:   newNode->data = data;
78:   
79:   if(head == NULL)
80:   {
81:     end = head = newNode;
82:     m_nSize++;
83:   }
84:   else
85:   {
86:     //insert at end
87:     end->next = newNode;
88:     end = newNode;
89:     m_nSize++;
90:   }
91: }
92: 
93: int linkList::count(int find)
94: {
95:   //find the int in the list, traverse the complete list
96:   int times = 0;
97:   listNode *temp = head;
98:   while(temp != NULL)
99:   {
100:     if(temp->data == find)
101:       times++;
102:     
103:     temp = temp->next;
104:   }
105:   
106:   return times;
107: }
108: 
109: //return the value at the valid index
110: //-1 means failure
111: int linkList::getNth(int index)
112: {
113:   listNode *temp = head;
114:   if(index < 0)
115:     return -1;
116:     
117:   int counted = 0;
118:   int data = -1;
119:   do
120:   {
121:     if(!temp)//reached the end, out of bounds
122:     {
123:       data = -1;
124:       break;
125:     }
126:     data = temp->data;
127:     temp = temp->next;
128:     counted++;
129:     
130:   }while(index >= counted);
131:   
132:   return data;
133: }
134: 
135: void linkList::deleteList()
136: {
137:   listNode *temp = head;
138:   while(head != NULL)
139:   {
140:     head = head->next;
141:     delete(temp);
142:     temp = head;
143:     m_nSize--;
144:   }
145:   cout<<"size "<<m_nSize<<endl;
146: }
147: 
148: int linkList::pop()
149: {
150:   int data = -1;
151:   if(head != NULL)
152:   {
153:     listNode *temp = head;
154:     head = head->next;
155:     data = temp->data;
156:     m_nSize--;
157:     delete(temp);
158:     temp = NULL;
159:   }
160:   return data;
161: }
162: 
163: int linkList::insertAtNth(int index,int data)
164: {
165:   if(index < 0 || index > m_nSize-1)
166:     return -1;
167:   
168:   listNode *newNode = new listNode;
169:   newNode->data = data;
170:   
171:   listNode *temp = NULL;
172:   //find the position to insert
173:   if(index == 0)//insert at head
174:   {
175:     newNode->next = head;
176:     head = newNode;
177:     m_nSize++;
178:     return 1;
179:   }
180:   else
181:   {
182:     temp = head;
183:     while((--index))
184:       temp = temp->next;
185:       
186:     newNode->next = temp->next;
187:     temp->next = newNode;
188:     m_nSize++;
189:     return 1;  
190:   }
191: }
192: 
193: int main(int argc, char **argv)
194: {
195:   linkList myList(10);
196:   cout<<"1 is found "<<myList.count(1)<<" times"<<endl;
197:   cout<<"11 is found "<<myList.count(11)<<" times"<<endl;
198:   cout<<"element at -1 index is "<<myList.getNth(-1)<<endl;
199:   cout<<"element at 19 index is "<<myList.getNth(19)<<endl;
200:   cout<<"pop the top "<<myList.pop()<<endl;
201:   cout<<"pop the top "<<myList.pop()<<endl;
202:   
203:   myList.display();
204:   myList.deleteList();
205:   
206:   myList.insert(5);
207:   myList.insert(9);
208:   myList.display();
209:   myList.insertAtNth(0,4);
210:   myList.display();
211:   myList.insertAtNth(1,6);
212:   myList.display();
213:   myList.insertAtNth(3,10);
214:   myList.display();
215:   myList.sortedInsert(6);
216:   myList.display();
217:   myList.sortedInsert(4);
218:   myList.display();
219:   myList.sortedInsert(9);
220:   myList.display();
221: 
222:   
223:   myList.deleteList();
224:   cout<<"after deleting list "<<endl;
225:   
226:   printf("hello world\n");
227:   getchar();
228:   return 0;
229: }
230: