0

While I get the concept behind lists and pointers, I just don't understand the script, what each part is saying. Here's an example of what we've been doing in class:

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

struct Node * first; 

first=NULL;

I do get the second part: simply defining the first element in the list and assigning an empty value to it. But what about the struct Node part?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
agaminon
  • 121
  • 1
  • 6
    https://en.wikipedia.org/wiki/Linked_list – Eraklon Jan 14 '21 at 20:01
  • 3
    This appears to be C, not C++. The `struct Node *` notation is never needed in C++. – Drew Dormann Jan 14 '21 at 20:02
  • `struct Node * first;` in `c++` you don't need the `struct` on this line. `Node * first;` is sufficient. – drescherjm Jan 14 '21 at 20:04
  • 2
    @DrewDormann So it's C? I'm in a C++ course, though. Maybe my teacher is doing some... sneaky stuff. – agaminon Jan 14 '21 at 20:04
  • _"what about the "struct Node part"?"_ ... **which** "struct Node part"? You show us two. – Drew Dormann Jan 14 '21 at 20:06
  • 1
    @drescherjm same with `struct Node * next;` -> `Node * next;` – Remy Lebeau Jan 14 '21 at 20:07
  • 5
    @agaminon "*So it's C? I'm in a C++ course, though*" - C++ has its roots in C, but the two are separate languages, and modern C/C++ are vastly different. It is not uncommon for C++ teachers to teach C-isms in a C++ environment. Typically to teach low-level ideas before introducing higher-level ideas (some would argue the reverse way should be taught instead). The C++ way to create a linked list is to use the standard [`std::list`](https://en.cppreference.com/w/cpp/container/list) class instead. Your teacher probably wants you to understand what `std::list` does under the hood. – Remy Lebeau Jan 14 '21 at 20:08
  • @DrewDormann Well, the part that defines a structure called "Node" with "int info", etc. – agaminon Jan 14 '21 at 20:09
  • 1
    @agaminon That's not good. If your teacher isn't clear on ancient differences between C and C++, then I doubt you're going to learn much about modern C++. C++ has changed hugely in the past 10 years, but it seems your teacher is still in the 1990s. – john Jan 14 '21 at 20:10
  • @agaminon And it seems even worse that they introduced such a fundamental concept as a `struct` without properly explaining it to you. Given all this maybe the best you can do it get yourself a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – john Jan 14 '21 at 20:12
  • @agaminon is probably not in a position to tell their teacher what we are saying here. They are trying to pass a course. – Drew Dormann Jan 14 '21 at 20:14
  • Linked lists are used as a teaching tool because the density of lessons packed into a single assignment. They are typically one of the most challenging early assignments. Like Yunnosch's example below with the coat hangers, the best way to grasp what's happening and what you have to do is visualizing the list. Draw pictures. Draw a lot of pictures. Draw what the list looks like before. Draw what it should look like after. Sometimes you'll need to draw a task step by step to make sure you've gotten it right. Keep the pictures because they're invaluable when debugging. – user4581301 Jan 14 '21 at 20:25
  • @user4581301 I think I more or less understand the concept behind it, but I'm having trouble understanding what the code is saying. – agaminon Jan 14 '21 at 20:28
  • 1
    Ask your teacher for clarification/support. That's what they're there for: to teach you. – Asteroids With Wings Jan 14 '21 at 20:34
  • @AsteroidsWithWings She doesn't seem very keen on replying to emails, though. – agaminon Jan 14 '21 at 20:38
  • @agaminon Can you use the telephone? I do appreciate that, in this day and age, you're probably not physically _in_ the school, which is a shame. Does she put on classes for you? And you can ask questions? – Asteroids With Wings Jan 14 '21 at 21:07
  • @agaminon -- A linked list is a type of data structure -- it isn't a C++ or even a computer language thing. The real issue I have with all of this is that to implement such data structures in C++ requires you to know C++ beforehand. Otherwise all you will be doing is fighting two battles -- learning the language, and learning the data structure. – PaulMcKenzie Jan 14 '21 at 21:12

2 Answers2

3
struct Node
{
   int info;
   struct Node * next;
};

Defines a struct type named Node containing 2 data members, an int and a struct Node* pointer. A struct is a way to group related data together in memory. A class is another way. These are more formally known as compound types.

When used in a linked list of nodes, each node's next member will be set to point at the following node in the list. The last node in the list will have its next member set to NULL instead. Starting with the first node in a list, you can iterate the whole list from one node to the next until NULL is reached.

struct Node * first;

Declares a pointer variable named first of type struct Node * (the struct keyword is optional here in C++, but is required in C).

first=NULL;

Sets the pointer variable first to a value of NULL (ie, for a linked list with no nodes in it).

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • I'm confused as to why the pointer is written as 'struct Node *', could you clear that up? Thanks for the extensive answer, too. – agaminon Jan 14 '21 at 20:30
  • In C, any reference to a struct typename requires the `struct` keyword, unless you alias it with a `typedef`, ie: `typedef struct Node { ... } Node;` then you can use `Node *first;` instead of `struct Node *first;`. C++ supports C syntax, but it also simplifies the syntax by making the `struct` keyword optional everywhere outside of the `struct` type's declaration, thus no `typedef` is needed. – Remy Lebeau Jan 14 '21 at 20:33
2

Get five coat hangers. Consider each of them one variable of type Node (struct Node is the same, just in a C-style of syntax, which a C++ compiler also accepts).
Your hand is the pointer first (of type Node * in C++ syntax and struct Node * in the C-style).
Your hand being still empty is like first being NULL.

Take one of the coat hangers in your hand. (Hold it on one end, not on the hook.)
Now first points to the first hanger. (Hold the first hanger with the hook pointing down.)

Hang the second hanger into the hook of the first, so that the second hook is empty and pointing down. You have added the second element to your list, by making the hook/pointer of the first hold the second. The hook of the second is empty, NULL.

Hang the third hanger into the second, third hook pointing down and empty.

Add the fourth likewise.

Your second hand, if you ever use it, is a helper pointer, you will often need one.

Whatever you are asked to do with linked lists, try it with your five hangers first,
this should help you with all programming problems you encounter.

Good luck.

I am thinking of coat hangers looking like this

\----------/
 \        /
  \      /
   --|-- 
     J

Not like this

----   ----
    \ /
     J

If you have hangers made from wire, like used by many laundry services, you can bend it a little to make a convenient spot for hooking into.

\----^-----/
 \        /
  \      /
   --|-- 
     J
Yunnosch
  • 26,130
  • 9
  • 42
  • 54