linked lists/trees

#1 A linked list is kind of like an array. It's simply a group of "objects" each of which has a piece that points to the next item in the list.

The simplist reason for using a linked list is if you need to store a number of object together, like in an array, but you don't know how many you are going to need to store. a very basic structure for a linked list would look like this:

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

You would then have a pointer, usually called head, that points to the first node in the list. Each node then points to the next node, with the last node in the list next pointer being null.

The above structure if used in a linked list would act like an array of ints. The advantage is if you need to start anywhere from 1 to 100 ints, for an array you would have to declare the array with the full 100 unit capacity, wasting memory if it is only storing a single value. A linked list only uses as much memory as is needed to story the number of items currently being used.

I some of that helps, and that it is understandable. You can do a lot with linked lists, and once you have a handle on them, the applications will show themselves.

Eric

#2 Horray for cs132 concepts! that sort of stuff was part of my cs132 class last year. heh heh

Ryan

#3 With lists and trees you can also easily solve a lot of problems, like optimizations.

Example:
We have a network of railroads, with a city in each node.
We want to get the cheapest route and the shortest route between two cities.
This is done by sorting all cities in a tree with the city we travel from as root. (The sorting is based on the available routes and the route traveling prices.)
Then we get both wanted routes just by searching the tree in two different ways.

//hyzen

#4 thanks guys, this cleared up a bunch of questions I had, now I am wondering, can you have linked lists made out of classes? and if so, how would you write that?

#5 I wrote a simple linked list class in c++ a while ago, I could send it to you if you want it.

Now I use the Standard Template Library (STL) when I need lists and similar functionality. STL comes with several compilers (including VC++). It's a little tricky to understand the STL and you need to know what a c++ template is, but there are several tutorials on it and it's definitively worth it!

//hyzen

#6 Here is a great article from the guy who designed and implemented the C++ language, Bjarne Stroustrup.

The article talks about various ways to implement a stack but the discussion is directly applies to lists as well. Great read.

Sixteen Ways to Stack a Cat

--Rick

#7 that would be great hyzen, and I know what a template is: like, it let's you make a function so that the type you send through it can be different everytime.