Comp Sci Understanding C++ Linked List Code: Node Structure and Pointers Explained

  • Thread starter Thread starter bd411
  • Start date Start date
  • Tags Tags
    C++ List
AI Thread Summary
The discussion focuses on understanding the C++ linked list code, particularly the structure of nodes and the use of pointers. The typedef statement defines an alternative name for an integer as "Item," while the Node structure contains an integer data field and a pointer to the next Node. The pointer "next" indeed points to another Node, allowing traversal through the linked list starting from the head. The conversation also touches on variations of linked lists, such as doubly linked lists, which have pointers to both the next and previous nodes. Overall, the key takeaway is that pointers in C++ are used to reference the memory address of structures, facilitating dynamic data structures like linked lists.
bd411
Messages
39
Reaction score
0

Homework Statement


Hello, just having a bit of trouble understanding this bit of code:

typedef int Item;

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

typedef Node* NodePtr

NodePtr hdlist = NULL;


Homework Equations



None.

The Attempt at a Solution



I understand that typedef is used to assign alternative names to existing types. So Item is now (int). Node is the name of the structure and inside the structure we have Item data = int data basically. What I'm not sure about is Node* next.

As far as I am aware, pointers are declared with the int* ptr method. This is a pointer ptr of type int. However does this mean that next is a pointer of type Node? But Node is simply the name of the structure?
 
Physics news on Phys.org
Yes, so every Node has a pointer to a(nother) Node. This will be the next item in the list, like this:
ll2.gif


What you do is you keep a pointer to the first node in the list, which is called the head. The first item in the list is head->data. From there you can skip to head->next, which is the second node in the list, and the ->next of that is the third node, etc. until you eventually reach the end of the list which has it's next pointer pointing to nothing (null).

There are also variations where every Node has two pointers, one to the next item in the list and one to the previous one, which allows you to go through it in two directions; and computer scientists can probably tell you more complicated ones which have their various advantages (for example for easily searching sorted lists, etc).
 
Last edited:
Here is a "C" example with the next pointer at the start of the structure. This allows different structures with a next pointer at the beginning to share common code for handling lists of structures. This first example also uses the old "microsoft" "C" style for the typedef syntax. I left out the int item typedef, since I wanted to focus on the structure typedef:

typedef struct _NODE { // underscore used on struct name
struct _NODE* next;
int data;
}NODE, *NODEPTR; // no underscore on typedef names

NODEPTR hdlist = NULL;

Here is a "C++" example that uses inherited class:

class Node{ // base node class
public:
Node * next;
Node(){next = NULL;}
};

class NodeInt : public Node{ // inherited node class with int
public:
int value;
NodeInt(int v) : value(v) {next = NULL;};
};

NodeInt * hdlist = NULL;
 
Last edited:
bd411 said:
As far as I am aware, pointers are declared with the int* ptr method.
To declare a pointer you use syntax that looks like this:
Code:
[[I]type[/I]] * ptr;

In the above, type is some data type, such as int, float, char, or some user-defined type, such as Node in your code.
bd411 said:
This is a pointer ptr of type int.
No it's not. The declaration int * ptr; says that ptr is a variable whose type is "pointer to int." The value that is stored in a pointer is the address of the thing it points to.
bd411 said:
However does this mean that next is a pointer of type Node?
No, the type is "pointer to Node."
bd411 said:
But Node is simply the name of the structure?
 

Similar threads

Replies
2
Views
2K
Replies
1
Views
10K
Replies
2
Views
2K
Replies
3
Views
2K
Replies
5
Views
2K
Replies
10
Views
2K
Replies
1
Views
1K
Replies
2
Views
4K
Replies
3
Views
1K
Replies
5
Views
3K
Back
Top