linked list in c++

list.cpp

/**
 * Copyright (c) 2012, Yohei Yamaguchi.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the Software
 * is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include <iostream>
#include <cstdlib>
using namespace std;

typedef int type_t;

struct Listelem {
    type_t data;
    Listelem* next;
};

Listelem* init();
Listelem* create(type_t data);
Listelem* add(Listelem* list, type_t data);
Listelem* remove(Listelem* list, size_t pos);
void clear(Listelem* list);
void print(Listelem* list);


/**
 * generate an initialized list
 * this list has a dummy node at the top of the list for managing a
 * @return an initialized list
 */
Listelem* init()
{
    return create(type_t(NULL));
}

/**
 * create a list with a single node
 * @param data data the list has
 * @return a list with a single node
 */
Listelem* create(type_t data)
{
    Listelem* elem = new Listelem;
    if (!elem) {
        cerr << "Unable to allocate a memory region" << endl;
        exit(1);
    }
    elem->data = data;
    elem->next = NULL;
    return elem;
}

/**
 * add a new node in the list keeping an ascending order
 * @param list the pointer of the top node in the list
 * @param data data to add to the list
 * @return the pointer of the top node in the list
 */
Listelem* add(Listelem* list, type_t data)
{
    Listelem *head, *cur, *curPrev;
    cur = new Listelem;
    curPrev = new Listelem;
    if (!cur || !curPrev) {
        cerr << "Unable to allocate a memory regin" << endl;
        exit(1);
    }

    cur = list->next;
    head = curPrev = list;
    while (cur != NULL) {
        if (cur->data > data) {
            break;
        }
        curPrev = cur;
        cur = cur->next;
    }

    // prepare a new node
    Listelem* newNode = create(data);
    newNode->next = cur;
    curPrev->next = newNode;

    return head;
}

/**
 * remove a node located in the specified position
 * @param list the pointer of the top node in the list
 * @param pos a position to remove a node
 * @return the pointer of the top node in the list
 */
Listelem* remove(Listelem* list, size_t pos)
{
    if (list == NULL) { return list; }

    Listelem *head, *cur, *curPrev;
    cur = list->next;
    head = curPrev = list;

    while (cur != NULL && pos--) {
        curPrev = cur;
        cur = cur->next;
    }
    if (cur != NULL) {
        curPrev->next = cur->next;
        delete [] cur;
    } else {
        cerr << "the value of the pos is too large!" << endl;
    }

    return head;
}

/**
 * release memory regions of all nodes in the list
 * @param list the pointer of the top node in the list
 */
void clear(Listelem* list)
{
    if (list != NULL) {
        Listelem* tmp = list->next;
        clear(list->next);
        delete [] list;
    }
}

/**
 * show nodes in the list
 * @param list the pointer of the top node in the list
 */
void print(Listelem* list)
{
    list = list->next; // skip the dummy node
    while (list != NULL) {
        const char* s = (list->next == NULL) ? "\n" : " -> ";
        cout << list->data << s;
        list = list->next;
    }
}

int main()
{
    Listelem* list = init();

    add(list, 10);
    add(list, 5);
    add(list, 7);
    add(list, 0);
    add(list, 15);
    print(list);     // 0 -> 5 -> 7 -> 10 -> 15

    remove(list, 1); // 5 will be deleted
    print(list);     // 0 ->  7 -> 10 -> 15
    remove(list, 1); // 7 will be deleted
    print(list);     // 0 -> 10 -> 15

    clear(list);

    return 0;
}

added comments in the Javadoc style