Dynamic Linked Lists

[jamonathin]

Hey all, what im trying to do here is figure out how to access a specified pointer from a dynamic linked list.

What i mean is, in arrays we have

c:

char array[5] = "abcde"; char temp = array [2];

Where i can pick out the third letter with the number 2.

Then with pointers i can do something like:

c:

char temp = *(string + 2);

But how do i do this when i have a 'dynamic linked list' like such:

c:

struct Record {         char first [40];         char last [40];         char address [100];         char post [6];          char phone [10];                 struct Record *pNext; // self referential point }; struct Record *con = NULL; printf ("%s", *(con + 6) -> first); ????

And i would want to be able to access the, for example ' 7th ' record?

[Skynet]

If you're using a standard linked list, you can't access arbitrary elements - you have to start at the head and iterate n times to get the nth element. However, (though this may not be of help to you), you can create an array of pointers to the nodes of your list and get to items that way. That can be useful in cases where the pointers in your list are not being used for access to the list and are instead being used to represent a specific order of access to the list contents. If all you're doing is a dynamic list, that's probably not going to help, and you're left with using malloc calls and pointers or doing what you've done already with a standard linked list.

[md]

Yeah, usually with lists you have to start at one end and work your way to the index you want. Depending on how much memory you want to use with linking and how much effort you want to put into keeping the pointers up to date there are other things you can do like having a pointer to the middle of the list to make searching easier.

An array of pointers also works; but then you get into things like why not have an array of records; and assuming it's less then 64K items in length why not use indecies instead of pointers. Doing so dynamically isn't too had using malloc. I am more familliar with C++ which has IMHO better memory management facilities; but I know it's not too hard in C.

[jamonathin]

Yeah what you guys said makes a lot of sense. Im gonna try what you guys said and count up to 'n' and each time increment my list.
Thanks for the input guys.

[wtd]

Am I wrong for thinking that linked lists are about the simplest idea in all of programming?

Yeah, implementing them in something like C gets a little messy, but it's still a simple idea, right?

[md]

They are not quite the simplest but they are fairly easy to understand at a theoretical level. It's when you try and implement it that most people get confused and seem to forget everything.

[Bobrobyn]

wtd @ Tue Apr 03, 2007 2:18 pm wrote:

Am I wrong for thinking that linked lists are about the simplest idea in all of programming?

Yeah, implementing them in something like C gets a little messy, but it's still a simple idea, right?

Well, not the simplest, especially when people, for whatever reason, struggle with the concept of pointers. I know _I_ get it...several people get it, but for some reason, a lot of people have trouble grasping the concept of pointers which makes it hard for them to get linked lists. I caught someone trying to do a linked list with a dynamic array, today. What was interesting, was that it sort of worked....it was kind of like a psuedo linked list. It was quite interesting.

I also agree that implementation in C can be...irritating. But learning to implement it in C gets you to understand how it works...so I think it's worth doing at least once.

[wtd]

Bobrobyn @ Wed Apr 04, 2007 3:40 pm wrote:

wtd @ Tue Apr 03, 2007 2:18 pm wrote:

Am I wrong for thinking that linked lists are about the simplest idea in all of programming?

Yeah, implementing them in something like C gets a little messy, but it's still a simple idea, right?

Well, not the simplest, especially when people, for whatever reason, struggle with the concept of pointers.

The idea of linked lists has nothing to do with pointers.

[Bobrobyn]

wtd @ Wed Apr 04, 2007 3:58 am wrote:

The idea of linked lists has nothing to do with pointers.

True. The idea, or concept, isn't that difficult...so yeah, it's the implementation where the problem lies. But that's how you demonstrate that you really know something: by doing it.

Now, you could theoretically use the Java libraries and write something that uses linked lists....but by doing that, you're not going to really know what happens. To write, step by step, how something works (or in this case, how linked lists work...or to code them) is a great way to understand how they work. Then again, not everyone likes to know what goes on behind the scenes, and prefers to know only what's useful. *shrugs* I think that getting this "low" with a concept can be only benefitial. Now, I'm not saying that you'd use C to work with linked lists on a daily basis...at least, not without a library....I just think it's useful for the learning experience.