Doubly Linked List

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.

list.h
1#ifndef list_h
2#define list_h
3
4//structure for doubly linked list
5struct node {
6    int data;
7    struct node *prev;
8    struct node *next;
9} list;
10
11#endif
addToList.h
1#ifndef addtolist_h
2#define addtolist_h
3
4void 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
38void 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
search.h
1#ifndef search_h
2#define search_h
3
4struct 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
26void 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
deleteNode.h
1#ifndef deletenode_h
2#define deletenode_h
3#include "search.h"
4
5struct node *deleteNode(struct node **head_ref, int wanted_data) {
6    struct node *wanted_node = search(head_ref, wanted_data);
7    
8    if(*head_ref == NULL || wanted_node == NULL)
9        return (*head_ref);
10    
11    if(*head_ref == wanted_node)
12       *head_ref = wanted_node->next;
13    
14    if(wanted_node->next != NULL)
15        wanted_node->next->prev = wanted_node->prev;
16    
17    if(wanted_node->prev != NULL)
18        wanted_node->prev->next = wanted_node->next;
19    
20    delete wanted_node;
21    
22    return (*head_ref);
23}
24
25#endif
swap.h
1#ifndef swap_h
2#define swap_h
3
4struct 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
printList.h
1#ifndef printlist_h
2#define printlist_h
3
4void print_rightway(struct node *node) {
5    //output description
6    std::cout << "List: " << std::endl;
7    
8    //loop until NULL
9    while(node != NULL) {
10        //print out current node
11        std::cout << node->data << ", ";
12        
13        //set current pointer to next pointer
14        node = node->next;
15    }
16    
17    //output a new line
18    std::cout << std::endl;
19}
20
21void print_reversed(struct node *node) {
22    //output description
23    std::cout << "Reserved list:" << std::endl;
24    
25    //loop to navigate to tail
26    while(node->next != NULL)
27        node = node->next; //set current pointer to next pointer
28    
29    //loop until NULL
30    while(node != NULL) {
31        //print out current node
32        std::cout << node->data << ", ";
33        
34        //set current pointer to prev pointer
35        node = node->prev;
36    }
37    
38    //output a new line
39    std::cout << std::endl;
40}
41
42#endif
deleteList.h
1#ifndef deletelist_h
2#define deletelist_h
3
4struct 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
main.cpp
1#include <iostream>
2#include "list.h"
3#include "addToList.h"
4#include "swap.h"
5#include "deleteNode.h"
6#include "printList.h"
7#include "deleteList.h"
8using namespace std;
9
10int main(int argc, char **argv) {
11    //allocate empty list
12    struct node *newList = NULL;
13    
14    //loop to fill list
15    for(int i = 0; i < 20; i++) {
16        //append to list
17        append(&newList, i);
18    }
19    
20    //print out created list in rightway
21    print_rightway(newList);
22    
23    //search number 10 in list
24    search(newList, 10);
25    
26    //delete 7 in list
27    deleteNode(&newList, 7);
28    
29    //swap head with tail
30    swapNodes(&newList,0,19);
31    
32    //swap two neighbors
33    swapNodes(&newList,11,12);
34    
35    //swap new head with not neighbor
36    swapNodes(&newList,19,5);
37    
38    //print out rightway
39    print_rightway(newList);
40    
41    //print out reversed
42    print_reversed(newList);
43    
44    //delete list
45    deleteList(&newList);
46    
47    delete newList;
48    
49    return 0;
50}