Singly linked list for review c++

Question

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

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, tail_insert in my ordered insert function?

I look forward to reading your comments. Regards.

EDIT: Hi, I have updated my code after reading your comments. Large changes include:

new node function was not necessary because I re-factored tail_insert to use head_insert function to insert a new node.
tail return was refactored to make more use of the head_return function removing node deletion/manipulation.
ordered list was refactored. Iteration removed. Recursion implemented to make for a neater solution.
ordered insert is still iterative (I couldn't work out how to implement recursion). However, it has been slightly changed with removal of inserted boolean value and inclusion of a return statement for neater code. (I thought this may be akin to adding a goto statement so was unsure of this alteration at the start).
find remove was re-factored to use recursion dramatically reducing nesting and creating an incredibly neat solution! very proud :)

Changes I did not make:

although I feel assert and exceptions would be a useful addition, I feel they go beyond the scope of the task.
although I am aware that the type of var2 would be type in the example, type* var1, var2, I feel that *var1 visually confuses the type with the identifier.
do not import everything from namespace std; I was unsure what to import instead.

Thank you for your comments, here is the updated code. Feel free to critique further.

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

You could shave off some lines and make your code a bit clearer by removing the curly braces for single-line block statements. This would apply to most of your ifstatements. You also shouldn't use using namespace std. Read this post for more information: stackoverflow.com/questions/1452721/…. — Jamal♦, Apr 15 '13 at 14:09
Its not C++. This is just C code that happens to use new instead of malloc and << instead of print(). Please re-tag as such or re-write as C++. The worst of both worlds. — Loki Astari, Apr 15 '13 at 14:58
Is it because it's not really C++, or because of readability? If you thought I meant the code with multiple-lines (mostly the else statements), then I'm sorry for the confusion. I don't know how to word it exactly. — Jamal♦, Apr 15 '13 at 16:00

uli · Answer 1 · 2013-04-13 07:26:00Z

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

it is empty (*list == 0)
it has only a single element ((*list)->next == 0)
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.

with regard to your third point, the question states: int head_return(node_ll **list);//Returns the ﬁrst 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. — Danny Rancher, Apr 15 '13 at 10:24

William Morris · Answer 2 · 2013-04-15 16:22:46Z

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?

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.) — Danny Rancher, Apr 15 '13 at 10:21
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. — Loki Astari, Apr 15 '13 at 15:03
@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.? — William Morris, Apr 15 '13 at 16:20
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. — Loki Astari, Apr 15 '13 at 20:02

asked	1 year ago
viewed	233 times
active	1 year ago

current community

your communities

more stack exchange communities

Singly linked list for review c++

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ linked-list or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Singly linked list for review c++

2 Answers

Did you find this question interesting? Try our newsletter

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ linked-list or ask your own question.

Related

Hot Network Questions