[prog] C++ - linked list and segmentation fault

[Jenny Brown]

On Tue, 8 Apr 2003, Jennifer Davis wrote:

> That being said.
> I am having so much trouble getting my head around pointers in general
> and linked lists in particular.

Try approaching it visually instead of through code to begin with.  The
code syntax will follow the understanding.  If my explanation is too
simple and not helpful, I apologize, but it's an analogy that seemed to
work well for me when I was learning this same stuff a few years back.

Let's say you have a class named TrainCar.  TrainCar holds some of its
own data - it has a color and it has an id number.  It also is part of
a linked list - it can tell you what other TrainCar is attached to it.


|-------|   |-------|  |-------|  |-------|
|next=47|   |next=21|  |next=39|  |next=  |
|-------|   |-------|  |-------|  |-------|
|blue   |   | red   |  | orange|  | yellow|
| #32   |   | #47   |  | #21   |  | #39   |
|       |   |       |  |       |  |       |
|       |   |       |  |       |  |       |
|-------|   |-------|  |-------|  |-------|


This linked list shows a bit of data (each node's own identity) plus it
has an area that says what comes next.  This one is unsorted - the
items aren't alphabetical or anything.  If I decided arbitrarily that
I wanted to stick something between #47 and #21...


|-------|   |-------| |-------|  |-------|  |-------|
|next=47|   |next=21| |       |  |next=39|  |next=  |
|-------|   |-------| |-------|  |-------|  |-------|
|blue   |   | red   | |       |  | orange|  | yellow|
| #32   |   | #47   | |       |  | #21   |  | #39   |
|       |   |       | |       |  |       |  |       |
|       |   |       | |       |  |       |  |       |
|-------|   |-------| |-------|  |-------|  |-------|

Then I need to set #47 to point to 'newitem' and set newitem's "next" to
point to #21.  I don't want to lose #21 in the process though.  So,
it's useful to take newitem... look at where I want to stick it (after
#47), figure out what 47 was pointing to (#21), and set newitem to also
point to it at the same time.  This way I won't drop 21.  Then I can
change 47 to point to newitem instead, knowing 21 is safe.


This is a singly linked list.  The "next" goes in only one direction,
and ends at the end of the line, with yellow #39 acting as a caboose.
There are a couple of other variations.

One is a double-linked list.  This means each train car has both a
next and a previous - you can walk to the front of the train as
easily as you can walk to the back of the train.

Another is a circular list.  In that case, there is no caboose.  The
tail connects right back to the head, like circular model train tracks.
All that matters is that you keep track of one entry place in the
list, and it doesn't matter if it's beginning, end or middle - it's all
middle.

If you make a linked list in alphabetical order, then there's a reason
for where to insert a new item.  You walk down the line looking at
two items at a time, until you find the place where the new item should
fit in... then insert it just like above.


Now, when you go to actually use these in C or C++, you have to keep in
mind that a pointer is like a name, it's not the actual object but it
allows you to find it.  You have to allocate a real object with new in
order to actually find it - like manufacturing a real train car to
paint the number on.

The syntax in C is a bit hairy to keep straight what syntax means the
object (dereferencing the pointer = following it by name to its actual
object)... and what syntax is manipulating the pointer itself.

If you've said,  mynode = new Node();  and other = mynode;  then you've
made pointer other and pointer mynode both point to the same object
which was 'new Node()'.  You may find it valuable to write out in
summary what you intend the code to do before actually working through
the syntax, since the syntax may lead you offtrack to forgetting what
you were intending to accomplish, at lesat while you're still learning
it.

Draw lots of pictures.  Linked lists are a very visual-style data type
and may get easier to track down algorithms for by drawing.  You may
also benefit from making a small physical model with paper cards and
playing with it - sometimes manipulating it with your hands makes it
much more clear than any drawing could.



Jenny Brown