Merge two already sorted linked list

Question

This is code to merge two sorted linked lists. l1 and l2 are sorted. While calling the merge function via l3, I am passing l3 as an object by reference in that function. The code is running fine, but can someone suggest how I can code better, with regards to dealing with class objects and passing them in a function?

#include<iostream>
using namespace std;
class linklist{
 private:
 struct node{
 int data;
 node* link;
 }*start;
 public:
 linklist(){
 start=NULL;
 }
 void append(int);
 void display();
 void merge(linklist, linklist,linklist &);
 ~linklist()
 {
 node *q;
 while(start!=NULL)
 {
 q=start->link;
 delete start;
 start=q;
 }
 }
};
void linklist::append(int num){
 node *temp, *r;
 temp=start;
 if(start==NULL)
 {temp=new node;
 temp->data=num;
 temp->link=NULL;
 start=temp;
 }
 else{
 while(temp->link!=NULL)
 {
 temp=temp->link;
 }
 r= new node;
 r->data=num;
 r->link=NULL;
 temp->link=r;
 }
}
void linklist::display() {
 node *temp;
 temp=start;
 cout<<"Linked List is"<<endl;
 while(temp!=NULL)
 {
 cout<<temp->data<<" ";
 temp=temp->link;
 }
 cout<<endl;
}
void linklist::merge(linklist l1, linklist l2,linklist& l3) // Here is my doubt
{
 node *p, *q;
 p=l1.start;
 q=l2.start;
 int dat;
 while(p!=NULL && q!=NULL)
 {
 if(p->data > q->data)
 {
 dat=q->data;
 l3.append(dat);
 q=q->link;
 }
 else{
 dat=p->data;
 l3.append(dat);
 p=p->link;
 }
 }
 if(p==NULL)
 {
 while(q!=NULL)
 {
 dat=q->data;
 l3.append(dat);
 q=q->link;
 }
 }
 else{
 while(p!=NULL)
 {
 dat=p->data;
 l3.append(dat);
 p=p->link;
 }
 }
 cout<<"lists merged"<<endl;
}
int main()
{
 linklist l1,l2,l3;
 l1.append(2);
 l1.append(5);
 l1.append(23);
 l1.append(34);
 l1.append(45);
 l2.append(6);
 l2.append(9);
 l2.append(35);
 l2.append(98);
 l3.merge(l1, l2,l3);
 l3.display();
 return 0;
}

Answer 1

Here are some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Use more whitespace

Lines like this one:

cout<<"Linked List is"<<endl;

become much easier to read and understand with a little more whitespace:

cout << "Linked List is" << endl;

Use consistent formatting

The code seems to have inconsistent indentation and inconsistent placement of brackets {}. It doesn't matter as much which convention you use as much as it matters that you follow some convention. Doing so makes your code easier to read, understand and maintain.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl. For instance, the line quoted above could be written like this:

std::cout << "Linked List is\n";

Prefer modern initializers for constructors

The constructor use the more modern initializer style rather than the old style you're currently using. Instead of this:

 linklist(){
 start=NULL;
 }

you could use this:

 linklist() : start{nullptr} {}

This uses the more consistent {} form for initializing start (and so requires a C++11 compiler) but this can be done using older C++99 if needed. There is not a significant difference in this code, but it's a good habit to get into using.

Use const where practical

The display member functions of linklist does not alter the underlying object and therefore should be declared const:

void display() const;

Make your class destructor virtual

If there's any chance that your class will be derived from, the class destructor should be virtual to avoid problems with collections of objects. See this question for more details on why. If it can't be derived from, enforce that by declaring the class final.

With that said, as @isanae has correctly pointed out, you shouldn't be left with the impression that those are the only options. For a plain old concrete class such as this one, you can reasonably just leave it as it is right now.

Return something useful from functions

The merge function takes two sorted linked lists and returns a new one; or it should. Right now it's declared like this

void linklist::merge(linklist l1, linklist l2,linklist& l3)

but it would make much more sense like this:

linklist linklist::merge(linklist l1, linklist l2)

Better still would be for the first list to be implicit so that one could write this:

l3 = l1.merge(l2);

To do that, I'd write the function like this:

linklist linklist::merge(const linklist &l2) const {
 linklist l3;
 node *nodes[2]{start, l2.start};
 while (nodes[0] && nodes[1]) {
 size_t index = nodes[0]->data < nodes[1]->data ? 0 : 1;
 l3.append(nodes[index]->data);
 nodes[index] = nodes[index]->link;
 }
 l3 += nodes[0]; // one of the lists is empty at this point
 l3 += nodes[1];
 return l3;
}

Note that this assumes the existence of an operator+= which might be implemented like this:

linklist &operator +=(const node *p) {
 while (p) {
 append(p->data);
 p = p->link;
 }
 return *this;
}

Use operator<< instead of display

It would be convenient to be able to redirect the output to something other than std::cout, so the usual idiom is to use something like this:

friend std::ostream& operator<<(std::ostream& out, const linklist &list) {
 for (auto temp=list.start; temp; temp=temp->link) {
 out << temp->data << " ";
 }
 return out << '\n';
}

Now we can use it within main like this:

std::cout << "finished merging\n" << l1 << l2 << l3;

Consider using a template

As the code is currently written, it can only store a single int as data, but with only a very minor change in the code, it could become a template. The first few lines could look like this:

template <class T>
class linklist{
private:
 struct node{
 T data;
 node* link;

Thereafter, anywhere you specifically refer to an int for the data, replace it with the templated type T and you now have a generic container. For your int version, you can write this:

linklist<int> l1;

Consider providing a std::initializer_list constructor

linklist(std::initializer_list<T> list) : start{nullptr} {
 for (auto item : list) {
 append(item);
 }
}

Implementing all of the suggestions above give a main like this:

int main()
{
 linklist<int> l1{2, 5, 23, 34, 45};
 linklist<int> l2{6, 9, 35, 98};
 std::cout << "Before merging\n" << l1 << l2;
 auto l3 = l1.merge(l2);
 std::cout << "After merging\n" << l1 << l2 << l3;
}

Don't destroy passed objects

Right now the code destroys the passed objects in creating the new list. That's not a good design, especially because the lists are not even passed by reference, so it would be very surprising to someone looking at the code. That can be fixed with the following suggestion.

Create a copy constructor if you need one

The compiler will create a default copy constructor which does a shallow copy, but this won't work for data structures, like yours, which use pointers. Instead, if you really want to create a new linklist from an existing one, you'll need to create your own copy constructor:

linklist(const linklist &other) : start{nullptr} {
 for (auto temp = other.start; temp; temp = temp->link) {
 append(temp->data);
 }
}

Consider using smart pointers

Using something like a std::unique_ptr would free you (pun intended) from having to manage the mechanics of new and delete explicitly.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

• Neil: Whilst I agree with everything you say, it's not really answering his question. "I mean while dealing with class objects and passing them in a function."
• Edward: @Neil I've added some more to the answer to try to more fully address that question.

Answer 2

A proper C++ implementation would be generic, i.e. a code that can merge any linked lists (of the same type). This could be implemented by taking iterators (and templating over iterator type). At the present, your code looks like C.

Btw, you can simplify the body of merge somewhat as follows

auto p=l1.start, q=l2.start;
auto append = [&](auto x) { l3.append(x->data); x=x->link; }
while(p && q) {
 if(p->data > q->data)
 append(q)
 else
 append(p);
}
if(p==nulltr)
 p=q;
while(p)
 append(p);

• Bijon Guha: okay i will keep in mind.
• Eric Lippert: Your suggestion that you be able to merge two lists of giraffes or two lists of rectangles is a good one. Could we be even more generic, and say that it should be legal to merge a list of giraffes with a list of animals and get a list of animals? (Not a rhetorical question; I do not know enough about generics in C++ to know the answer.)
• Edward: @EricLippert: If giraffewere a class derived from animal and the list were declared to hold type animal, then yes. Here's a barnyard-related sample that may be helpful.

Answer 3

Note: I'm at least trying to avoid repeating @Edward's points, which I think are all quite good. It looks like while I was writing this @Loki wrote a few things that are a lot closer to what I said--sorry 'bout that, but I think I raise at least a couple of interesting new points as well.

I'd change a few things here. First, instead of leaving node as purely "dumb data", I'd add a constructor to construct a legitimate node:

node(int i) : data(i), link(nullptr) {}

Then I'd add a *tail in addition to *start:

*start, *tail;

We'll use this tail pointer to point to the last node in the list. This will let us append a new node to the list without traversing the entire list to get there, so append can be simplified to something like this:

void linklist::append(int num) {
 if (tail) {
 // add new item to list with existing contents
 tail->link = new node(num);
 tail = tail->link;
 }
 else {
 // adding first node to empty list:
 start = tail = new node(num);
 }
}

Since merge uses append to add items to the result list, we don't have to modify merge to use this.

As an entirely separate point, let's consider merge though. There are a couple of obvious points here, and one that's a little less obvious.

The first obvious point is to prefer to define an initialized variable over creating the variable without initialization, then assigning a value later, so we change this:

node *p, *q;
p=l1.start;
q=l2.start;

...to this:

node *p = l1.start;
node *q = l2.start;

Note that as a rule, I'd advise defining each variable individually (especially when defining pointers/references).

You also defined dat outside your while loop where you do the merging--as a rule of thumb, you want to keep the scope of any variable as small as reasonable, so I'd prefer to define it at the point of use, inside the loop.

Inside that loop, you have an if statement, where the true and false legs nearly duplicate each other, but one manipulates p and the other q. I'd rather eliminate that duplication. One possibility would be to define a reference to whichever pointer points to the less data item, then do the work with that:

 node *&less = p->data < q->data ? p : q;
 int dat = less->data;
 l3.append(dat);
 less = less->link;

Finally, I'd eliminate the cout line from merge. Putting (even part of) a user-interface inside a function like this makes the function essentially impossible to put to much (if any) real use.

To get an idea of how much difference it makes when we avoid traversing the entire list to append a new item, I rewrote main a little bit to generate a couple of lists of 500 elements apiece, then see how long it takes to merge the two:

int main()
{
 static const int length = 1000;
 linklist l1, l2, l3;
 for (int i = 0; i < length; i += 2)
 l1.append(i);
 for (int i = 1; i < length; i += 2)
 l2.append(i);
 using namespace std::chrono;
 auto start = high_resolution_clock::now();
 l3.merge(l1, l2, l3);
 auto end = high_resolution_clock::now();
 l3.display();
 std::cout << "Time: " << duration_cast<nanoseconds>(end - start).count() << "\n";
}

With your original definition of append, the result was:

Time: 3735198

With my modified append, I got:

Time: 74626

That's about 50 times as fast. If we increase the size of the list to 100,000 items, the time difference grows just a bit:

Original: Time: 9657619316
Revised: Time: 10380544

So at this size, we've improved speed by a factor of approximately 930:1--not too bad an investment, considering that we got this improvement by making the code shorter and simpler.

Answer 4

Everything @Edward said.

Dry up your code.

You have a lot of repeated code.

Declare objects as close to first use as possible.

 while(start!=NULL)
 {
 node* q = start->link; // Move the `node* q` declaration to here.
 delete start;
 start=q;
 }

For loops are usually more tidy than while loops.

 for(node* next; start != null; start = next)
 {
 next = start->link;
 delete start;
 }

Use object constructors and don't repeat code

if(start==NULL)
{temp=new node;
temp->data=num;
temp->link=NULL;
start=temp;
}
else{
 while(temp->link!=NULL)
 {
 temp=temp->link;
 }
 r= new node;
 r->data=num;
 r->link=NULL;
 temp->link=r;
}

This becomes:

if(start==NULL)
{
 start=new node{num, nullptr};
}
else
{
 node* temp = start
 while(temp->link != NULL)
 {
 temp=temp->link;
 }
 temp->link = new node{num, nullptr};
}

Which with a bit we can use pointers to get tidy.

/* OK now that I have done it.
 * Don't do this.
 *
 * It may be slightly better but the degrade in
 * readability is not worth the tiny performance gain of not using
 * a conditional.
 */
node** find = &start;
while((*find) != NULL)
{
 find = &((*find)->link);
}
(*find)->link = new node{num, nullptr};

Remove repeated code

while(p!=NULL && q!=NULL)
{
 if(p->data > q->data)
 {
 dat=q->data;
 l3.append(dat); // This is the same for both sides of the else.
 q=q->link;
 }
 else{
 dat=p->data;
 l3.append(dat);
 p=p->link;
 }
}
if(p==NULL) // Don't need this test. Code works fine without it.
{
 while(q!=NULL)
 {
 dat=q->data;
 l3.append(dat);
 q=q->link;
 }
}
else{ // Don't need this else. Code works fine without it.
 while(p!=NULL)
 {
 dat=p->data;
 l3.append(dat);
 p=p->link;
 }
}

We can refactor to this:

while(p!=NULL && q!=NULL)
{
 node** valid = (p->data > q->data)
 ? &p
 : &q;
 l3.append((*valid)->data);
 (*valid) = (*valid)->link;
}
for(;q != NULL; q = q->link)
{
 l3.append(q->data);
}
for(;p != NULL; p = p->link)
{
 l3.append(p->data);
}

• scottbb: suggested hyper-optimization to shorten the last bit of code: the while loop will "exhuast" either of p or q (or perhaps both), so there's no need to have 2 for loops to go through the remainders of both of them. Thus, they can be reduced to the single loop: for (node *n = p ? p : q; n != NULL; n = n->link) { l3.append(n->data); }
• Loki Astari: @scottbb: Yes. But when you do it that way it makes the code less readable. I prefer putting both loops at the end. It does not change the number of tests you need to do.

Answer 5

The question sounds like you are asking if this line is correct:

void linklist::merge(linklist l1, linklist l2,linklist& l3)

Personally, I would code it like this:

void linklist::merge(const linklist& l1, const linklist& l2, linklist& l3)

This implies that you are saying l1 & l2 are not going to change (const), and they are being passed by reference (so not being copied onto the stack). I can now infer that probably l1 & l2 are inputs and l3 is the output parameter.