Singly linked list

Question

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;
}

Answer 1

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.

Answer 2

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?