CODEWITHSUNDEEP
c++classobjectpointerslinked-list
Subrato Kumar Mahato
Subrato Kumar Mahato

Reputation: 11

Can I implement linked list using object of a class instead of pointer to an object?

In C++ Suppose I have

class Sample{
 public:
 void someFunction();
};

In main() is there any difference between doing

Sample obj;
obj.someFunction();

AND

Sample *obj = new Sample();
obj->someFunction();
delete obj;

Can I use just obj instead of *obj to implement the linkedlist and tree data structure in C++? That's the only doubt.

Upvotes: 0

Views: 68

Answers (2)

avm
avm

Reputation: 399

I will take the question as- What is the role of pointers in linked list?

Linking the nodes is the basic role of pointers in linked list but at the core its all about dynamic nature of linked list.

To get to the answer you first need to understand the concept of memory management. Mainly there are 2 segments of memory allocated to a running program i.e. Stack and Heap. Stack is called static memory because it is fixed in size and does not grow as per the requirement of program. Heap is called dynamic memory because it can grow and shrink as per the requirement.

This is how we allocate memory in stack and heap respectively-

Sample obj;  //this takes up space from stack i.e. `obj` resides in stack
Sample *obj = new Sample(); //a new chunk of memory is allocated from heap

And pointers are the way to access memory allocated in heap section. Now the question changes to- Why use dynamic memory(or heap)?

Tree or linked list is a type of dynamic data structure which means we can not know beforehand the size of the tree or list because they can grow and shrink during program operation. So if we keep using memory from stack then at some point we may run out of stack memory which will cause Stack overflow.

Here's a link if you want to learn more about pointers and dynamic memory.

Upvotes: 0

George Glavan
George Glavan

Reputation: 134

You will always need a pointer (or a reference) when implementing a linked list. This is needed in order to link to the next value in the list. For example, for your code you will need

class Sample{
public:
 Sample *next;
 void someFunction();
};

You cannot build something like this:

class Sample{
    public:
     Sample next;
     void someFunction();
    };

because there is will be infinite samples boxed in one another. The compiler cannot know how long the list should be (tho you can use some template arguments for this if you know the size at compile time)

And next will point to the next value in the list. So in your main you will have:

int main() {
 // allocate 2 Sample objects 
 Sample *s1 = new Sample();
 Sample *s2 = new Sample():

 // link them together
 s1->next = s2;
 delete s1;
 delete s2;
}

Of course, you can have them local to main for example:

int main() {
 // 2 Sample objects on  the stack 
 Sample s1;
 Sample s2:

 // link them together
 s1.next = &s2;
}

the big difference here is that s1 and s2 are local to the main function. This is fine as long as we talk about main, but you cant do something like this:

Sample f() {
 Sample s1, s2;
 s1.next = &s2;
 return s1;
}

because s2 does not live after f ends, so s1.next will be an invalid pointer.

Upvotes: 1

Related Questions