Apekshik Panigrahi
Apekshik Panigrahi

Reputation: 206

Declaring structure with itself?

I've begun studying data structures, and the linked list popped up. The idea behind a linked list is simple, but the implementation (I use c++) is a bit confusing, especially regarding the nodes used in linked lists. The way a node is defined for a singly linked list in C++ is as follows

// A linked list node 
struct Node { 
    int data; 
    struct Node* next; 
}; 

or if we were using classes, then it is defined like this.

class Node { 
public: 
    int data; 
    Node* next; 
}; 

My confusion arises here. How can one define another struct inside struct Node with the same name? I see that the new struct is a pointer to a node, but how does this implementation actually work? It's really confusing :(

Upvotes: 1

Views: 339

Answers (2)

lubgr
lubgr

Reputation: 38315

How can one define another struct inside struct Node with the same name?

That's not what's happening. You can omit the struct keyword in the data member declaration struct Node* next; such that it might be easier to digest:

struct Node { 
   int data; 
   Node* next; 
}; 

Except access specifier (the public), this is now identical to the class version, and it can become clear that you don't define a new struct Node inside of Node, but instead you declare a data member next that is a pointer to an instance of type Node. A pointer on a 64bit machine will need 64bit, that's why the compiler can work with this definition of Node, as the size it must reserve for Node instances is known.

Upvotes: 1

user1316208
user1316208

Reputation: 687

To declare a pointer to something you do not need definition of the class, only its declaration. Therefore this is not recursive definition and the compiler won't run into problems.

You can think of it this way: The pointer member will be the same size whatever the type of the pointer, it still needs only the capacity to address a place anywhere in memory.

Upvotes: 1

Related Questions