On linked lists (was Re: [prog] C++ - linked list and segmentation fault)

[Jacinta Richardson]

On Tue, 8 Apr 2003, Jennifer Davis wrote:

> like having a GPA of 4.0 and would like to maintain it.  That being said.
> I am having so much trouble getting my head around pointers in general
> and linked lists in particular.

Jenny Brown wrote an excellent write up on linked lists, but I thought I
might give my understanding of them (C-style only I'm afraid) as well.
Sometimes it helps to have different ways of explanation.

First of all linked lists are often implemented as a way of keeping
distinct sets of data in some sorted order.  This does not need to be
the case, as linked lists are common in uses as stacks (first in, first
out (think about a stack of paper on your desk where you only add to the
top and take from the top)) and also in queues (first in, first out).

The code that implements stacks and queues are subsets of the code that
allows insertion anywhere in the linked list, so I'll pretend for the
purposes of this note, that we're keeping an ordered list.

Let's pretend we're sorting (insertion sort) on some id number.  Our
c-style struct would have at least "id" and "next", where next is a
c-style pointer to another struct of the same type.  We can put all sorts
of other things in this struct, but for this example, we don't need to
worry about them.  Keep in mind though, that the other things in the
struct may also be pointers to other structs.  There is nothing saying
that a struct can be part of only one linked list for example.

I'm going to representing my structs as follows:

		A->

where A represents the id number and the arrow represents next.  We'll
sort the id values as according to the alphabet.

In the case that we don't have a linked list already inserting is really
easy:

	if(head == NULL)
	{
		head = newthing;
	}

so we won't worry about that case any more.

There are three cases we do need to worry about.
*  Insertion at the head of the list (the entirity of stack based
   insertion) which occurs if our id is less than that at the head.
*  Insertion at the tail of the list (queue) which occurs if our id is
   less than that of the last value
*  Insertion between two elements of the list.

Let's create three extra pointers.
head -	 always points to the first element
curr -   always points to the element we are currently examining
prev -   always points to the previous element we examined.

** Insertion at head of the list.

we have:	B------>C->D->
		^
		|
	      head/curr

	  prev->
          newptr---->A->

that is, we have an existing linked list with the elements B->, C-> and
D->,  we have both the head and curr pointers pointing at the first
element and we have prev pointing into nowhere yet.  "newptr" points to
the element A-> which we'd like to add to the front of the list.

What we're going to have to do is, make the A-> element point to B-> and
make the head pointer now point to A.  Should be easy:

	if(newptr.id < head.id)	# insertion at head of list!
	{
		newptr.next = head;
		head = newptr;
	}
Easy as pie!


** Insertion at the tail of the list:

we have:	A-->B--->C---->D->
		^	 ^     ^
		|	 |     |
	      head     prev   curr  	

          newptr---->E->

What we're going to have to do is, make the next part of the D-> element
point to E.

	if(curr.id < newptr.id && curr->next == NULL)  # tail of list
	{
		newptr.next = NULL;    # usually a good idea
		curr.next = newptr;
	}
Done!


** Insertion in the middle.
Now the fun bit.
	  
we have:	A-->B--->C---->E->
		^	 ^     ^
		|	 |     |
	      head     prev   curr  	

          newptr---->D->

What we're going to have to do is:  make C-> (prev) point to D-> (newptr) 
and D-> point to E-> (curr).  Not much else...

	if(curr.id < newptr.id)  # insert it here
	{
		prev->next = newptr;	# C-> points to D->
		newptr->next = curr;	# D-> E->
	}

and it's done!

So, hopefully this has helped you understand linked lists a little
better.   You'll find more concise code in Sedgewick (Algorithms in C,
Robert Sedgewick, Addison Wesley Press) which is THE book to have besides
you when you're learning linked lists in the first place.

I've left out the traversing the linked list because I hope that's
self-evident since it's pretty much
	while(curr != NULL)
	{
		prev = curr;
		curr = curr->next;
	}
although you want to put a whole lot more into that while loop. ;)


Double linked lists are very much the same, except instead of just
having D-> as an element you get  <-D-> because then each element knows
who was before it as well as who was next.  Still, I think you'll find
that if you draw your pictures and where you travelling pointers curr,
and prev are at, working out how to change all the links around will
become easy.

The biggest problem students had when I taught linked lists, was that
they'd forget to draw it out.  They'd draw it in their heads and get
confused and write confused code.  It's much easier to take up a few
sheets of paper with ugly pictures of pointers going everywhere until
you get the hang of it.  The second biggest problem was that they'd
forget that right at the start it's better to handle the end of the list
and the start of the list separately, even if later the code can be
condensed into less conditions and so on...

So good luck and make sure you have fun.  Linked lists and red and black
trees and in fact any kind of tree in C is probably one of the most FUN
things you'll do with C for a while.  The rest is kinda just data entry.

	All the best

			Jacinta

PS:  I don't know any C compiler who allows # as comments but /**/ takes
up so much room.  Make sure you translate correctly.  ;)

--
   ("`-''-/").___..--''"`-._          |  Jacinta Richardson	    |
    `6_ 6  )   `-.  (     ).`-.__.`)  |  Perl Training Australia    |
    (_Y_.)'  ._   )  `._ `. ``-..-'   |      +613 9354 6001 	    |  
  _..`--'_..-_/  /--'_.' ,'           | contact at perltraining.com.au |
(il),-''  (li),'  ((!.-'              |   www.perltraining.com.au   |