The simply linked list is easy to implement and useful if you want to delete an element.
1 | #ifndef addtolist_h
|
2 | #define addtolist_h
|
3 |
|
4 | void append(struct node **head_ref, int new_data) {
|
5 |     struct node *new_node = new struct node;
|
6 |     struct node *last = *head_ref;
|
7 |     
|
8 |     new_node->data = new_data;
|
9 |     new_node->next = NULL;
|
10 |     
|
11 |     if(*head_ref == NULL) {
|
12 |         *head_ref = new_node;
|
13 |         return;
|
14 |     }
|
15 |     
|
16 |     while(last->next != NULL) last = last->next;
|
17 |     
|
18 |     last->next = new_node;
|
19 |     
|
20 |     return;
|
21 | }
|
22 |
|
23 | void push(struct node **head_ref, int new_data) {
|
24 |     //allocate new node
|
25 |     struct node *new_node = new struct node;
|
26 |     
|
27 |     //put in data
|
28 |     new_node->data = new_data;
|
29 |     
|
30 |     //link the old list off the new node
|
31 |     new_node->next = (*head_ref);
|
32 |     
|
33 |     //move the head to point to the new node
|
34 |     (*head_ref) = new_node;
|
35 | }
|
36 |
|
37 | #endif |
1 | #ifndef search_h
|
2 | #define search_h
|
3 |
|
4 | struct node *search(struct node **head_ref, int wanted_data) {
|
5 |     struct node *tmp_pointer = *head_ref;
|
6 |     struct node *wanted_node = NULL;
|
7 |     
|
8 |     while(tmp_pointer != NULL) {
|
9 |         if(tmp_pointer->data == wanted_data) {
|
10 |             wanted_node = tmp_pointer;
|
11 |         }
|
12 |         tmp_pointer = tmp_pointer->next;
|
13 |     }
|
14 |     return wanted_node;
|
15 | }
|
16 |
|
17 | #endif |
1 | #ifndef deletenode_h
|
2 | #define deletenode_h
|
3 | #include "search.h"
|
4 |
|
5 | struct node *deleteNode(struct node **head_ref, int wanted_data) {
|
6 |     //reference pointer to list for navigation
|
7 |     struct node *tmp_pointer = *head_ref;
|
8 |     
|
9 |     //search wanted node for delete
|
10 |     struct node *wanted_node = search(head_ref, wanted_data);
|
11 |     
|
12 |     if(tmp_pointer == wanted_node) {
|
13 |         if(tmp_pointer->next == NULL) {
|
14 |             return (*head_ref);
|
15 |         }
|
16 |         tmp_pointer->data = tmp_pointer->next->data;
|
17 |         
|
18 |         wanted_node = tmp_pointer->next;
|
19 |         
|
20 |         tmp_pointer->next = tmp_pointer->next->next;
|
21 |         
|
22 |         delete wanted_node;
|
23 |         
|
24 |         return (*head_ref);
|
25 |     }
|
26 |     
|
27 |     struct node *prev = tmp_pointer;
|
28 |     while(prev->next != NULL && prev->next != wanted_node)
|
29 |         prev = prev->next;
|
30 |     
|
31 |     //check if node really exists in linked list
|
32 |     if(prev->next == NULL) {
|
33 |         return (*head_ref);
|
34 |     }
|
35 |     //remove node from linked list
|
36 |     prev->next = prev->next->next;
|
37 |     
|
38 |     //free memory
|
39 |     delete wanted_node;
|
40 |     
|
41 |     return (*head_ref);
|
42 | }
|
43 |
|
44 | #endif |
1 | #ifndef swap_h
|
2 | #define swap_h
|
3 |
|
4 | struct node *swapNodes(struct node **head_ref, int x, int y) {
|
5 |     //nothing to do if x and y are the same
|
6 |     if(x == y)
|
7 |         return (*head_ref);
|
8 |     
|
9 |     //search x element and keep track off prev_X and curr_X
|
10 |     struct node *prev_X = NULL, *curr_X = *head_ref;
|
11 |     while(curr_X && curr_X->data != x) {
|
12 |         prev_X = curr_X;
|
13 |         curr_X = curr_X->next;
|
14 |     }
|
15 |     
|
16 |     //search y element and keep track off prev_Y and curr_Y
|
17 |     struct node *prev_Y = NULL, *curr_Y = *head_ref;
|
18 |     while(curr_Y && curr_Y->data != y) {
|
19 |         prev_Y = curr_Y;
|
20 |         curr_Y = curr_Y->next;
|
21 |     }
|
22 |     
|
23 |     //if x or y are not elements in list than do nothing
|
24 |     if(curr_X == NULL || curr_Y == NULL)
|
25 |         return (*head_ref);
|
26 |     
|
27 |     //if x is not head of linked list
|
28 |     if(prev_X != NULL)
|
29 |         prev_X->next = curr_Y;
|
30 |     else //else make y as new head
|
31 |         *head_ref = curr_Y;
|
32 |     
|
33 |     //if y is not head of linked list
|
34 |     if(prev_Y != NULL)
|
35 |         prev_Y->next = curr_X;
|
36 |     else //else make x as new head
|
37 |         *head_ref = curr_X;
|
38 |     
|
39 |     //swap next pointers
|
40 |     struct node *tmp_next = curr_Y->next;
|
41 |     curr_Y->next = curr_X->next;
|
42 |     curr_X->next = tmp_next;
|
43 |     
|
44 |     return (*head_ref);
|
45 | }
|
46 |
|
47 | #endif |
1 | #ifndef printlist_h
|
2 | #define printlist_h
|
3 |
|
4 | void printList(struct node *head_ref) {
|
5 |     //reference to list for navigation
|
6 |     struct node *tmp_pointer = head_ref;
|
7 |     
|
8 |     //begin print out with new line
|
9 |     std::cout << std::endl;
|
10 |     
|
11 |     //walk through the list until reached NULL
|
12 |     while(tmp_pointer != NULL) {
|
13 |         //print out current data
|
14 |         std::cout << tmp_pointer->data << ", ";
|
15 |         
|
16 |         //set current pointer to next pointer
|
17 |         tmp_pointer = tmp_pointer->next;
|
18 |     }
|
19 |     
|
20 |     //end print out with new line
|
21 |     std::cout << std::endl;
|
22 | }
|
23 |
|
24 | #endif |
1 | #ifndef deletelist_h
|
2 | #define deletelist_h
|
3 |
|
4 | struct node *deleteList(struct node **head_ref) {
|
5 |     //reference to list for navigation
|
6 |     struct node *tmp_pointer = *head_ref;
|
7 |     
|
8 |     //walk through the list and erase
|
9 |     while(tmp_pointer != NULL) {
|
10 |         deleteNode(head_ref,tmp_pointer->data);
|
11 |         
|
12 |         tmp_pointer = tmp_pointer->next;
|
13 |     }
|
14 |     
|
15 |     return (*head_ref);
|
16 | }
|
17 |
|
18 | #endif |
1 | /*
|
2 |     
|
3 |     main.cpp
|
4 |     
|
5 |     simply linked list
|
6 |     
|
7 |     How to compile with GCC under Linux/UNIX:
|
8 |     g++ -o list main.cpp
|
9 |     
|
10 | */
|
11 |
|
12 | #include <iostream>
|
13 | #include "list.h"
|
14 | #include "addToList.h"
|
15 | #include "deleteNode.h"
|
16 | #include "swap.h"
|
17 | #include "printList.h"
|
18 | #include "deleteList.h"
|
19 | using namespace std;
|
20 |
|
21 | int main(int argc, char **argv) {
|
22 |     //empty list
|
23 |     struct node *newList = NULL;
|
24 |     
|
25 |     //loop to add integer numbers to list
|
26 |     for(int i = 1; i < 21; i++) {
|
27 |         append(&newList, i);
|
28 |     }
|
29 |     
|
30 |     //print out list
|
31 |     printList(newList);
|
32 |     
|
33 |     //delete number 20
|
34 |     deleteNode(&newList, 20);
|
35 |     
|
36 |     //swap two nodes
|
37 |     swapNodes(&newList, 19, 18);
|
38 |     
|
39 |     //print out new list
|
40 |     printList(newList);
|
41 |     
|
42 |     //delete list
|
43 |     deleteList(&newList);
|
44 |     
|
45 |     //free memory
|
46 |     delete newList;
|
47 |     
|
48 |     return 0;
|
49 | } |