1
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.