5
\$\begingroup\$

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.

I am looking to compact my functions (specifically ordered_insert and find_remove) without removing functionality. For example, at the moment my find_remove function works if there exists two matching nodes at the start, two matching nodes in the middle or two matching nodes at the end.

For example, could I make more use of head_insert and tail_insert in my ordered insert function?

#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;//Let temp be the address of the node that is the head of the list.
    while(temp)// != NULL
    {
        cout << temp->payload << endl;//Print out payload of the struct whose address is temp.
        temp = temp->next;//Set the address of temp equal to the address stored in next of the struct whose address is temp.
    }
}

void head_insert(node_ll** list, int pload)
{
    node_ll* temp = new node_ll;//Create a new node, and let temp be the address of that node.
    temp->payload = pload;//Set the payload of the struct whose address is temp to pload.
    temp->next = *list;//Set the next of the struct whose address is temp to the address of the old head of the list.
    *list = temp;//The address of the old head of the list is changed to the address of the struct temp.
};

void tail_insert(node_ll** list, int pload)
{
    if (*list == NULL)
    {
        head_insert(list, pload);
    }
    else
    {
        node_ll* temp = new node_ll;
        for (temp = *list; temp->next; temp = temp->next);
        temp->next = new node_ll;
        temp->next->payload = pload;
        temp->next->next = NULL;
    }
}

int head_return (node_ll** list)
{
    if (*list != NULL)
    {
    int temp = (*list)->payload;
      node_ll* trash = *list;
      *list = (*list)->next;
      delete trash;
      return temp;
    }
    else
    {
        return 0;
    }
}

int tail_return (node_ll** list)
{
    if (*list != NULL)
    {
      if ((*list)->next == NULL)
        {
            return head_return(list);
        }
        else
        {
      node_ll* trash;
            for (trash = *list; trash->next->next; trash = trash->next);
            int temp = trash->next->payload;
            delete trash->next;
            trash->next = NULL;
            return temp;
        }
    }
    else
    {
        return 0;
    }
}

bool ordered_list(node_ll** list)
{
    if (*list != NULL && (*list)->next != NULL)
    {
      node_ll* temp;
      for (temp = *list; temp->next; temp = temp->next)
      {
          if (temp->payload > temp->next->payload)
          {
              return false;
          }
      }
    }
  return true;
}

void ordered_insert(node_ll** list, int pload)
{
    if (ordered_list(list))
    {
      if (*list == NULL || (*list)->payload > pload)
      {
        head_insert(list, pload);
      }
      else
    {
            bool inserted = false;
            node_ll* temp;
            for (temp = *list; temp->next; temp = temp->next)
            {
                if (temp->next->payload > pload && !inserted)
                {
                    node_ll* next = temp->next;
                    temp->next = new node_ll;
                    temp->next->payload = pload;
                    temp->next->next = next;
                    inserted = true;
                }
            }
            if (!inserted)
            {
                tail_insert(list, pload);
            }
        }
    }
}

void find_remove (node_ll** list, int pload)
{
    if (*list != NULL)
    {
        while (*list && (*list)->payload == pload)
        {
            head_return(list);
        }
        if (*list != NULL)
        {
            node_ll* temp;
            for (temp = *list; temp->next; temp = temp->next)
            {
                while (temp->next->next != NULL && temp->next->payload == pload)
                {
                    node_ll* trash = temp->next;
                    temp->next = temp->next->next;
                    head_return(&trash);
                }
            }
            if (temp->next == NULL && temp->payload == pload)
            {
                tail_return(list);
            }
        }
    }
}

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 << 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 << 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\$
6
\$\begingroup\$

The tail_insert() function could be improved a bit:

node_ll* tmp = new node_ll;
...
while(*list)
    list = &(*list)->next;
*list = tmp;

In any case, you should separate the code for setting up the new node and inserting it a bit, then you would notice that you allocate two(!) nodes there.

Then, tail_return() and head_return(), are these really supposed to erase the front element? Also, both should check first thing that *list is not zero, I'd even prefer using assert() for that, but that depends on the intended semantics.

In ordered_list(), I'd also put the check for an empty list at the beginning and not use an else clause afterwards. Then, the check if there is a next element is redundant, the loop does that correctly. I'd also declare and init the loop variable in the loop header, not separately to that. Lastly, your call (3,2,1) ordered, but I would rather say that (1,2,3) is ordered! Again, it depends on the intended semantics that must be documented.

Then, ordered_insert(), what exactly is it doing when the list is not sorted? What is it supposed to do in that case even? I wouldn't bother doing anything, so just add assert(ordered_list(list)) at the beginning and declare it a fault in the calling code if it tries to do an ordered insert on an unordered list. In the loop, you could just return after inserting an element, saving the inserted flag.

In find_remove(), your nesting levels are too deep. Simply returning after finding out that the list is already empty would decrease this and at the same time split the function in two parts, allowing the reader to understand each of them separately. I for one don't understand what all those loops are doing there, but that might be caused by the lack of comments concerning what they are supposed to do.

Lastly, you could rewrite some functions to use recursion. For example, a list is sorted if

  1. it is empty (*list == 0)
  2. it has only a single element ((*list)->next == 0)
  3. its first two elements are sorted ((*list)->payload < (*list)->next->payload)) and the list starting with the second element is sorted (ordered_list(&(*list)->next)).

Doing that would make code a bit more readable in my eyes, although the iterative solution is fine, too. Note that the recursion only requires steps 2 and 3, the first one would be redundant.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ with regard to your third point, the question states: int head_return(node_ll **list);//Returns the first integer from the head of the list, and deletes it from the list. int tail_return(node_ll **list);//Returns the last integer from the tail of the list, and deletes it from the list. With regard to your fourth point, the question states: bool ordered_list(node_ll **list);//Returns true if the list is in ascending order, and false otherwise. \$\endgroup\$ – Danny Rancher Apr 15 '13 at 10:24
5
\$\begingroup\$

Here's a few comments to add to those of @uli (+1)

Would one ever use a linked list in c++ when there are nice STL containers available for such things? Seems unlikely, but I'm not strong on c++. But in a c++ exercise on the subject of linked lists, I'd expect to see some use of c++ facilities.

For example you could usefully use exceptions to avoid the ambiguity in your head_return and tail_return functions. These two currently return 0 on failure but this is a valid value for the payload (you don't check for it when inserting, so I assume it is a valid payload). You might also use an exception when doing an ordered insert (as opposed to an assert suggested by @uli).

I would change some of your variable names. For example you have three names for a payload, payload, pload and temp. Why not use just one consistently if possible? And you also use temp for a temporary node, but node would be more descriptive.

Here are some detailed comments (some are pedantic and others perhaps only opinion):

  • importing everything from std (using namespace std) is best avoided.
  • I prefer to see type *var rather than type* var - consider the type for var2 in the declaration type* var1, var2. EDIT: as noted by @LokiAstari in the comments, this is a preference carried over from C and is not applicable to C++, where type* var is the convention.
  • you don't have many comments, but those you have are noise (no useful information) and should be deleted. Write useful comments - don't state the obvious.
  • empty loops should be made explicit with braces:

    for (temp = *list; temp->next; temp = temp->next) {
        /* loop */
    }
    
  • ending a function with

    else
    {
        return 0;
    }
    

    is better written as just return 0

  • where possible, define loop variables in the loop:

    for (node_ll *temp = *list; temp->next; temp = temp->next) {...}
    
  • in ordered_insert you'd be better to break the loop by adding a !inserted condition once you've inserted the value rather than continuing to loop:

    for (temp = *list; temp->next && !inserted; temp = temp->next)
    
  • I'm sure that a new_node() function would be useful:

    static node_ll* new_node(node_ll *next, int payload)
    {
        node_ll *node = new node_ll;
        node->payload = payload;
        node->next = *next;
        return node;
    }
    
  • is it really expected that find_remove removes all occurrences of a payload instead of just one?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ with regard to your last point, the question states: void find_remove (node_ll **list, int pload);// Find all nodes with payload pload and remove them from the linked list. (If there is no node with payload pload, do not do anything.) \$\endgroup\$ – Danny Rancher Apr 15 '13 at 10:21
  • \$\begingroup\$ The usage type *vat is C like. C++ convention is type* var as the * is part of the type information. Yes this has the problem type* x,y; issue but that is resolved by not having more than one variable per line. \$\endgroup\$ – Martin York Apr 15 '13 at 15:03
  • \$\begingroup\$ @LokiAstari - I didn't know it was a convention, thanks. I edited the answer. Is there a good reason for it, bearing in mind that people do in practice declare multiple variables on a line.? \$\endgroup\$ – William Morris Apr 15 '13 at 16:20
  • \$\begingroup\$ Like all things C/C++ their is debate. But the majority in C++ consider it part of the type and thus it belongs on the left. While in C old style conventions put it on the right more often. There is one obscure corner case with a typedef where it is better for the type conversely there is the obscure case were people put multiple variable on a line where it is better. \$\endgroup\$ – Martin York Apr 15 '13 at 20:02

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.