Singly linked list 2.0

Question

Version 1.0: Singly linked list

The struct and the prototypes of the functions were given in the question. I am unfortunately aware that this is more C code and less C++ code.

#include <iostream>
using namespace std;

struct node_ll
{
    int payload;
    node_ll* next;//Pointer to the next node
};

void print_ll (node_ll** list)
{
  node_ll* temp = *list;
    while(temp)
    {
        cout << temp->payload << endl;
        temp = temp->next;
    }
}

void head_insert(node_ll** list, int pload)
{
    node_ll *node = new node_ll;
    node->payload = pload;
    node->next = *list;
    *list = node;
};

void tail_insert(node_ll** list, int pload)
{
    if (!*list)
    {
        head_insert(list, pload);
    }
    else
    {
        node_ll* temp = *list;
        while(temp->next)
        {
            temp = temp->next;
        }
        head_insert(&temp->next, pload);
    }
}

int head_return (node_ll** list)
{
    if (!*list)
    {
        return -1;//Error: List is empty.
    }
    node_ll* trash = *list;
    int i = trash->payload;
    *list = trash->next;
    delete trash;
    return i;
}

int tail_return (node_ll** list)
{
    if (!*list)
    {
        return -1;//Error: List is empty.
    }
    if (!(*list)->next)
    {
        return head_return(list);
    }
    else
    {
        node_ll* temp = *list;
        while(temp->next->next)
        {
            temp = temp->next;
        }
        return head_return(&temp->next);
    }
}

bool ordered_list(node_ll** list)
{
    if (!*list || !(*list)->next)
    {
        return true;
    }
    if ((*list)->payload < (*list)->next->payload)
    {
        return ordered_list(&(*list)->next);
    }
    else
    {
        return false;
    }
}

void ordered_insert(node_ll** list, int pload)
{
    if (!ordered_list(list))
    {
        return;//Error: List is not ordered;
    }
    if (!*list || (*list)->payload > pload)//If list is null or first payload is greater than new payload.
    {
        head_insert(list, pload);
    }
    else
    {
        node_ll* temp = *list;
        while(temp->next)
        {
            if (temp->next->payload > pload)
            {
                head_insert(&temp->next, pload);
                return;
            }
            temp = temp->next;
        }
        head_insert(&temp->next, pload);//If all payloads are less than or equal to new payload.
    }
}

void find_remove (node_ll** list, int pload)
{
    if (!*list)
    {
        return;//List is empty.
    }
    while (*list && (*list)->payload == pload)//While loop required as node will become node->next on head_return(node).
    {
        head_return(list);
    }
    if (*list && (*list)->next)
    {
        find_remove(&(*list)->next, pload);
    }
}

int main()
{
    node_ll* alist = NULL;
    cout << "Empty list a to start." << endl;
    head_insert(&alist, 2);
    head_insert(&alist, 4);
    head_insert(&alist, 6);
    cout << "List a after head insertion of 2,4,6 is: " << endl;
    print_ll(&alist);
    cout << "Tail return: " << tail_return(&alist) << endl;
    cout << "Tail return: " << tail_return(&alist) << endl;
    cout << "Tail return: " << tail_return(&alist) << endl;
    cout << "Tail return: " << tail_return(&alist) << endl;
    cout << endl;

    node_ll* blist = NULL;
    cout << "Empty list b to start." << endl;
    tail_insert(&blist, 2);
    tail_insert(&blist, 4);
    tail_insert(&blist, 6);
    cout << "List b after tail insertion of 2,4,6 is: " << endl;
    print_ll(&blist);
    cout << "Head return: " << head_return(&blist) << endl;
  cout << "Head return: " << head_return(&blist) << endl;
  cout << "Head return: " << head_return(&blist) << endl;
  cout << "Head return: " << head_return(&blist) << endl;
    cout << endl;

    node_ll*clist = NULL;
    cout << "Empty list c to start." << endl;
    tail_insert(&clist, 2);
    tail_insert(&clist, 4);
    tail_insert(&clist, 6);
    cout << "List c after tail insertion of 2,4,6 is: " << endl;
    print_ll(&clist);
    if (ordered_list(&clist))
    {
        cout << "List c is ordered." << endl;
    }
    else
    {
        cout << "List c is not ordered." << endl;
    }
    ordered_insert(&clist, 1);
    ordered_insert(&clist, 3);
    ordered_insert(&clist, 7);
    cout << "List c after ordered insertion of 1,3,7 is: " << endl;
    print_ll(&clist);
    cout << endl;

    node_ll* dlist = NULL;
    cout << "Empty list d to start." << endl;
    tail_insert(&dlist, 2);
    tail_insert(&dlist, 2);
    tail_insert(&dlist, 3);
    tail_insert(&dlist, 4);
    tail_insert(&dlist, 4);
    tail_insert(&dlist, 9);
    tail_insert(&dlist, 6);
    tail_insert(&dlist, 6);
    cout << "List d after tail insertion of 2,2,3,4,4,5,6,6 is: " << endl;
    print_ll(&dlist);
    if (ordered_list(&dlist))
    {
        cout << "List d is ordered." << endl;
    }
    else
    {
        cout << "List d is not ordered." << endl;
    }
    find_remove(&dlist, 2);
    find_remove(&dlist, 4);
    find_remove(&dlist, 6);
    cout << "List c after find and remove of 2,4,6 is: " << endl;
    print_ll(&dlist);
    cout << endl;

    system("PAUSE");
    return 0;
}

Answer 1

Considering the following code

head_insert(&alist, -1);
int result = tail_return(&alist);
if (result == -1)
  std::cout << "error" << std::endl;

Is this the correct result?

No, you can't have an allowed payload that is also the error code.

bool ordered_list(node_ll** list) {
    if (!*list || !(*list)->next) {
        return true;
    }
    if ((*list)->payload < (*list)->next->payload) {
        return ordered_list(&(*list)->next); // extremely inefficient recursive call
    } else {
        return false;
    }
}

Use a while loop instead.

bool ordered_list(node_ll** list) {
    if (!*list || !(*list)->next) {
        return true;
    }

    node_ll *test = *list; // no reason to run around with the double deref.
    while (test->next && (test->payload < test->next->payload) {
        test = test->next;
    } 

    // if there is a next its not ordered
    if (test->next) {
        return false;
    }
    return true;
}

Not having a separate tail pointer makes all operations involving tail cost O(N) instead of O(1). Not having a separate tail pointer makes the code easier as it doesn't need to be maintained to insure consistency.