Simply Linked List

The simply linked list is easy to implement and useful if you want to delete an element.

list.h
1#ifndef list_h
2#define list_h
3
4struct node {
5    int data;
6    struct node *next;
7} list;
8
9#endif
addToList.h
1#ifndef addtolist_h
2#define addtolist_h
3
4void 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
23void 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
search.h
1#ifndef search_h
2#define search_h
3
4struct 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
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    //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
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 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
printList.h
1#ifndef printlist_h
2#define printlist_h
3
4void 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
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/*
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"
19using namespace std;
20
21int 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}