Linked Lists in C

[rar]

Could someone briefly go over Linked Lists in C for me? I've been taught it in class, but I can't quite comprehend how it's been explained.

I seem to slightly understand the concept, but I have no idea how I'd implement it into code. So could someone please explain the concept and provide a coding example? That would be extremely helpful, thanks!

[jbking]

There are 2 ideas at the core of a linked list:

Node - This is the heart of the whole process as the node contains both the data inside the node which could be a class or almost anything, and a pointer to another node.

Pointer - This is how nodes are connected and how one can just add another node to an unsorted list in constant time.

Sample code for a linked list in C that can easily be found via Google.

[Euphoracle]

Well assuming you were taught how using C structs, here's a brief outline.

So first a definition,

A linked list is a

• an element, and
  
• another linked list, or empty

So to translate that directly line-by-line to C code, you could use (this is an example of an integer)

c:

struct node {         int val;         struct *node next; }; typedef struct node *list;

Now to create a list in the heap, you can simply do

c:

list Lst1 = malloc(sizeof(struct node)); list Lst2 = malloc(sizeof(struct node)); Lst1->val = 4; Lst1->next = Lst2; Lst2->val = 3; Lst2->next = NULL;

Now you have a list with two nodes (first value 3, second value 4) and the 'empty' node.

Now you can write functions to manipulate these so you don't have the reinvent the wheel every time.

[rar]

So I've made up my program to be a modification of my previous, contact book structure program, using linked lists. However, whenever I have more than 2 contacts, it goes into an infinite loop of printing the first contact.

code:

struct Contact //contact structure {         char fname[41]; //strings for first name, last name, address, postal code, and phone numbers         char lname[41];         char address[101];         char postcode[7];         char pnum[11];         int count; //a count variable to count the number of contacts         struct Contact *ptrNext; }; int main() { PrintContacts(); //assume that there are 2 or more contacts already put in, only putting a main here so you can see how it is called } void PrintContacts() {         int x = 0;         struct Contact *ptrPrint = ptrFirst;         while(ptrPrint != NULL) //prints each contact         {                        printf("Contact #%d:\n", x + 1);                 printf("First name: %s\n", ptrPrint->fname);                 printf("Last name: %s\n", ptrPrint->lname);                 printf("Address: %s\n", ptrPrint->address);                 printf("Postal Code: %c%c%c-%c%c%c\n", toupper(ptrPrint->postcode[0]), ptrPrint->postcode[1], toupper(ptrPrint->postcode[2]), ptrPrint->postcode[3], toupper(ptrPrint->postcode[4]), ptrPrint->postcode[5]);                 printf("Phone Number: (%c%c%c) %c%c%c-%c%c%c%c\n", ptrPrint->pnum[0], ptrPrint->pnum[1], ptrPrint->pnum[2], ptrPrint->pnum[3], ptrPrint->pnum[4], ptrPrint->pnum[5], ptrPrint->pnum[6], ptrPrint->pnum[7], ptrPrint->pnum[8], ptrPrint->pnum[9]);                 printf("\n");                 ptrPrint = ptrPrint->ptrNext;                 x++;                         }         }

[Tony]

Well it sounds like ptrNext in ptrFirst is pointing at ptrFirst. It's likely a problem in how you create/add nodes to the list.

[rar]

Tony @ Wed Mar 31, 2010 7:53 pm wrote:

Well it sounds like ptrNext in ptrFirst is pointing at ptrFirst. It's likely a problem in how you create/add nodes to the list.

So what should it be I'm still new to linked lists..

[TerranceN]

Your last node should point to NULL so your loop will exit when you get to the last node, as you have basicly tied a rope in a circle and told the computer to follow it until it ends.

Hope that helps.

[rar]

I don't have a last node, I just have a while loop that operates while the current node does not equal NULL, which is basically what you're saying...

[TerranceN]

Analogy time!

Image you can make peices fo string that can attach to other peices of string. You always know two places, the beginning of the rope (the rope is all the strings) and where you are on the rope (what string). You can also move to the next string that your current string is attached to. When you add a a new string, the last string ties to the beginning of the new string, but where does the end of the new string go? The answer is NULL or in this case nowhere, so that there is an end to the rope.

From this analogy we know that every piece of string/node that is added onto the rope/list must go to to nowhere until we tie something (another string/node) onto it, therefore the last node will always tie onto/go to nothing/NULL, and therefore our rope/list will have an end.

What you did was instead of that last string/node going to nowhere/NULL it tied back onto the rope/list somewhere, creating an endless loop, which is why your program would write the same data over and over.

Hope that helps, but I honestly only know this stuff from reading a few things online so it may be (and it probably is somewhere) wrong.

[Tony]

You need to watch this. Seriously. http://www.youtube.com/watch?v=CObg3tbT2lg

[LeeShane]

rar @ Mon Mar 22, 2010 4:33 pm wrote:

Could someone briefly go over Linked Lists in C for me? I've been taught it in class, but I can't quite comprehend how it's been explained.

I seem to slightly understand the concept, but I have no idea how I'd implement it into code. So could someone please explain the concept and provide a coding example? That would be extremely helpful, thanks!

Most obviously, linked lists are a data
structure which you may want to use in real programs.
Seeing the strengths and weaknesses of linked lists will give you an appreciation of the some of the time, space,
and code issues which are useful to thinking about any data structures in general.

[DtY]

Tony @ Wed Mar 31, 2010 9:20 pm wrote:

You need to watch this. Seriously. http://www.youtube.com/watch?v=CObg3tbT2lg

Just keep in mind that the `new` keyword does not exist in C.

[unoho]

Tony @ Wed Mar 31, 2010 9:20 pm wrote:

You need to watch this. Seriously. http://www.youtube.com/watch?v=CObg3tbT2lg

omgg...that's the same video our TA showed us when explaining pointers. it makes it very easy to understand but coding is always the difficult part

[SmokeMonster]

For anyone having trouble with pointers check out this http://cslibrary.stanford.edu/102/ read the pdf on pointers and memory and work through some of the linked list and tree examples on the website. It helped me out a lot when I was first learning about pointers.