The doubly linked list is similarly easy to implement as the simply linked list but the advantage is an additional pointer to the previous node and with this pointer you can navigate to root without to reverse the whole list.
1 | #ifndef addtolist_h
|
2 | #define addtolist_h
|
3 |
|
4 | void append(struct node **head_ref, int new_data) {
|
5 |     /* 1. allocate node */
|
6 |     struct node* new_node = new struct node;
|
7 |     struct node *last = *head_ref; /* used in step 5*/
|
8 |     
|
9 |     /* 2. put in the data */
|
10 |     new_node->data = new_data;
|
11 |     /*
|
12 |      3. This new node is going to be the last node, s
|
13 |      make next
|
14 |      of it as NULL
|
15 |     */
|
16 |     new_node->next = NULL;
|
17 |     
|
18 |     /*
|
19 |      4. If the Linked List is empty, then make the new node as head
|
20 |     */
|
21 |     if(*head_ref == NULL) {
|
22 |         new_node->prev = NULL;
|
23 |         *head_ref = new_node;
|
24 |         return;
|
25 |     }
|
26 |     
|
27 |     /* 5. Else traverse till the last node */
|
28 |     while(last->next != NULL)
|
29 |         last = last->next;
|
30 |     
|
31 |     /* 6. Change the next of last node */
|
32 |     last->next = new_node;
|
33 |     new_node->prev = last;
|
34 |     
|
35 |     return;
|
36 | }
|
37 |
|
38 | void push(struct node **head_ref, int new_data) {
|
39 |     //allocate store for new node
|
40 |     struct node *new_node = new struct node;
|
41 |     
|
42 |     //put in data
|
43 |     new_node->data = new_data;
|
44 |     
|
45 |     //by first adding previous pointer is always NULL
|
46 |     new_node->prev = NULL;
|
47 |     
|
48 |     //link the old list off the new node
|
49 |     new_node->next = (*head_ref);
|
50 |     
|
51 |     //change pevious of head node to the new node
|
52 |     if((*head_ref) != NULL)
|
53 |         (*head_ref)->prev = new_node;
|
54 |     
|
55 |     //move the head to point to the new node
|
56 |     (*head_ref) = new_node;
|
57 | }
|
58 |
|
59 | #endif |
1 | #ifndef search_h
|
2 | #define search_h
|
3 |
|
4 | struct node *search(struct node **head_ref, int wanted_data) {
|
5 |     //reference to list
|
6 |     struct node *tmp_pointer = *head_ref;
|
7 |     
|
8 |     //store for wanted pointer
|
9 |     struct node *wanted_node = NULL;
|
10 |     
|
11 |     //loop until NULL
|
12 |     while(tmp_pointer != NULL) {
|
13 |         //if wanted node found than store pointer
|
14 |         if(tmp_pointer->data == wanted_data) {
|
15 |             wanted_node = tmp_pointer;
|
16 |         }
|
17 |         
|
18 |         //set current pointer to next pointer
|
19 |         tmp_pointer = tmp_pointer->next;
|
20 |     }
|
21 |     
|
22 |     //return wanted pointer
|
23 |     return wanted_node;
|
24 | }
|
25 |
|
26 | void search(struct node *node, int wanted_data) {
|
27 |     //print out description
|
28 |     std::cout << "Search " << wanted_data << ":" << std::endl;
|
29 |     
|
30 |     //loop until NULL
|
31 |     while(node != NULL) {
|
32 |         //if wanted data found than print out data
|
33 |         if(node->data == wanted_data) {
|
34 |             //print out
|
35 |             std::cout << node->data << " found!" << std::endl << std::endl;
|
36 |             
|
37 |             //return to main
|
38 |             return;
|
39 |         }
|
40 |         
|
41 |         //set current pointer to next pointer
|
42 |         node = node->next;
|
43 |     }
|
44 |     
|
45 |     //print out if wanted data is not in list
|
46 |     std::cout << wanted_data << " not found" << std::endl << std::endl;
|
47 | }
|
48 |
|
49 | #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 same
|
6 |     if(x == y)
|
7 |         return (*head_ref);
|
8 |     
|
9 |     //store position of x in list
|
10 |     int pos_X = 0;
|
11 |     //search for x (keep track of prevX and currX
|
12 |     struct node *prev_X = NULL, *curr_X = *head_ref;
|
13 |     while(curr_X && curr_X->data != x) {
|
14 |         prev_X = curr_X;
|
15 |         //count position of x in list
|
16 |         ++pos_X;
|
17 |         curr_X = curr_X->next;
|
18 |     }
|
19 |     
|
20 |     //store position of y in list
|
21 |     int pos_Y = 0;
|
22 |     //Search for y (keep track of prevY and currX}
|
23 |     struct node *prev_Y = NULL, *curr_Y = *head_ref;
|
24 |     while(curr_Y && curr_Y->data != y) {
|
25 |         prev_Y = curr_Y;
|
26 |         //count position of y in list
|
27 |         ++pos_Y;
|
28 |         curr_Y = curr_Y->next;
|
29 |     }
|
30 |     
|
31 |     //swap y x to x y
|
32 |     if(pos_X > pos_Y) {
|
33 |         struct node *temp_curr = curr_Y;
|
34 |         struct node *temp_prev = prev_Y;
|
35 |         
|
36 |         curr_Y = curr_X;
|
37 |         curr_X = temp_curr;
|
38 |         
|
39 |         prev_Y = prev_X;
|
40 |         prev_X = temp_prev;
|
41 |     }
|
42 |     
|
43 |     //If either x or y is not present, nothing to do
|
44 |     if(curr_X == NULL || curr_Y == NULL)
|
45 |         return (*head_ref);
|
46 |     
|
47 |     //swap all next pointer
|
48 |     //If x is not head of linked list
|
49 |     if(prev_X != NULL) {
|
50 |         prev_X->next = curr_Y;
|
51 |     }
|
52 |     else {
|
53 |         //else make y as new head
|
54 |         *head_ref = curr_Y;
|
55 |     }
|
56 |     
|
57 |     //If y is not head of linked list
|
58 |     if(prev_Y != NULL) {
|
59 |         prev_Y->next = curr_X;
|
60 |     }
|
61 |     else {
|
62 |         //else make x as new head
|
63 |         *head_ref = curr_X;
|
64 |     }
|
65 |     
|
66 |     //swap all previous pointer
|
67 |     //swap with right neighbor
|
68 |     if(curr_Y->prev->data == curr_X->data) {
|
69 |         //if second node tail
|
70 |         if(curr_Y->next == NULL) {
|
71 |             //store tail of list
|
72 |             struct node *new_tail = new node;
|
73 |             new_tail->prev = curr_Y;
|
74 |             new_tail->data = curr_X->data;
|
75 |             new_tail->next = NULL;
|
76 |             
|
77 |             //swap prev pointers
|
78 |             curr_Y->prev = curr_X->prev;
|
79 |             
|
80 |             //swap prev next pointer
|
81 |             new_tail->prev->next = curr_Y->next;
|
82 |             
|
83 |             //set tail pointers to current X
|
84 |             curr_X = new_tail;
|
85 |             
|
86 |             //set next of current Y to current X
|
87 |             curr_Y->next = curr_X;
|
88 |             
|
89 |             //delete temporary allocated pointer
|
90 |             delete new_tail;
|
91 |         }
|
92 |         else {
|
93 |             //swap with none tail
|
94 |             
|
95 |             //store pointers for swap
|
96 |             struct node *temp_next = curr_Y->next;
|
97 |             struct node *temp_prev = curr_Y->prev;
|
98 |             
|
99 |             //swap next prev pointers
|
100 |             curr_Y->next->prev = temp_prev;
|
101 |             
|
102 |             //swap prev pointers
|
103 |             curr_Y->prev = curr_X->prev;
|
104 |             curr_X->prev = curr_Y;
|
105 |             
|
106 |             //swap next pointers
|
107 |             curr_Y->next = curr_X->next;
|
108 |             curr_X->next = temp_next;
|
109 |         }
|
110 |     }
|
111 |     else {
|
112 |         //swap with not right neighbor
|
113 |         
|
114 |         //if second node tail
|
115 |         if(curr_Y->next == NULL) {
|
116 |             //store tail of list
|
117 |             struct node *new_tail = new node;
|
118 |             new_tail->prev = curr_Y->prev;
|
119 |             new_tail->data = curr_X->data;
|
120 |             new_tail->next = NULL;
|
121 |             
|
122 |             //store pointers to swap
|
123 |             struct node *temp_prev = curr_Y->prev;
|
124 |             
|
125 |             //swap next prev pointers
|
126 |             curr_X->next->prev = curr_Y;
|
127 |             
|
128 |             //swap prev pointers
|
129 |             curr_Y->prev = curr_X->prev;
|
130 |             curr_X->prev = temp_prev;
|
131 |             
|
132 |             //swap next pointers
|
133 |             curr_Y->next = curr_X->next;
|
134 |             curr_X->next = new_tail->next;
|
135 |             
|
136 |             //set tail to current X pointer
|
137 |             curr_X = new_tail;
|
138 |             
|
139 |             //delete temporary pointer
|
140 |             delete new_tail;
|
141 |         }
|
142 |         else {
|
143 |             //swap with not right neighbor without tail
|
144 |             
|
145 |             //store pointers for swap
|
146 |             struct node *temp_next = curr_Y->next;
|
147 |             struct node *temp_prev = curr_Y->prev;
|
148 |             struct node *temp_next_prev = curr_Y->next->prev;
|
149 |             
|
150 |             //swap next prev pointers
|
151 |             curr_Y->next->prev = curr_X->next->prev;
|
152 |             curr_X->next->prev = temp_next_prev;
|
153 |             curr_Y->next->prev = curr_X;
|
154 |             
|
155 |             //swap prev pointers
|
156 |             curr_Y->prev = curr_X->prev;
|
157 |             curr_X->prev = temp_prev;
|
158 |             
|
159 |             //swap next pointers
|
160 |             curr_Y->next = curr_X->next;
|
161 |             curr_X->next = temp_next;
|
162 |         }
|
163 |     }
|
164 |     return (*head_ref);
|
165 | }
|
166 |
|
167 | #endif |