Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Ghostface

Linked Lists? HUH?!?

This topic is 6172 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

As I'm sure people who've read other topics started by me before have noticed, some things about programming leave me completely dumbfounded. And, now there's another one: linked lists. First of all, the only programming language I have experience with and have been learning for about 9 months is C++. However, the only tutorials on this site I have seen are in C, and so certain things dealing with memory allocation, such as the absense of the keywords "new" and "delete", leave me completely perplexed. Second, the primary book that I am using to learn C++ ever since school has been out (yep, my 6th period class all of 10th grade was "Introduction to C++ Programming". Lucky me) is "Teach Yourself C++ in 21 Days, Third Edition". Now, maybe it's just me...but the author doesn't really explain the implementation and/or uses of linked lists very well. So...can anyone PLEASE help me understand linked lists? Or at least point me in the direction of a good tutorial? Thanks. Edited by - Ghostface on July 29, 2001 7:57:30 PM

Share this post


Link to post
Share on other sites
Advertisement
With all due respect Ghostface, I recommend that you find a good book on C++. This is the second basic concept you''ve asked about recently (the other being the virtual functions thing) and not only are these concepts essential to do any serious work in C++, but they should be covered in any good book that teaches C++. If the books you have at the moment aren''t too good, then you need a better one. Learning from online tutorials is rarely as good because a lot of the people who write tutorials don''t care about ''good'' code, they care about ''working'' code, which is usually based on misunderstandings.

A linked list is a data structure. The ''list'' part implies that it consists of numerous other parts, which are called nodes or elements. The ''links'' are what make these otherwise separate elements into a list. Basically, each element points to the next in the list, wherever it might be in memory. This is usually done with a pointer. So, to go through all the elements, you start with the 1st one, and do whatever you need to do to it. Then you check it''s pointer (usually called the ''next'' pointer) to find out where the next element is in memory. You can then look at that element, and then follow its own next pointer, and so on, until you hit the end of the list (usually signified by a next pointer being NULL).

A linked list is better than an array in that you can add and remove elements very quickly. All you need to do is change the next pointers around a bit. With an array, you would have to shuffle elements along. Linked lists also grow as you need them, whereas an array generally has to be allocated once, meaning that you have wasted memory if the array isn''t full. The downside of a linked list is that it takes time to go from one element to another. To find the 6th element, you must look at the 1st to find the 2nd, the 2nd to find the 3rd, and so on. Whereas with an array, you just look at array[ 6 ] directly, which is faster. Also, the pointers from one element to another constitute a small memory usage overhead compared to array elements. With small elements, this overhead will be significant compared to the size of the element itself.

Share this post


Link to post
Share on other sites
Well, Kylotan, the thing is this: either no book can explain it properly, or I''m just stupid. I''m starting to lean toward the latter. Oh well. I hate programming anyway.

Thank you for your post. I suppose I should reserve questions of such a manner for the "For Beginners" forum. If you would like to the threads there, that''s fine with me.

Share this post


Link to post
Share on other sites
Try looking for books as used in schools for their programming or computer science courses, rather than than "How to learn every language feature without understanding them in 21 days" books. The academic books are better at teaching you the reasoning and the philosophy behind programming. That way, you''ll appreciate the usefulness of inheritance, pointers, linked lists/other data structures, and so on, rather than just being told how to make them.

Share this post


Link to post
Share on other sites
Try Deitel & Deitel''s C++: How to program. It should be pretty cheap and it comes with a copy of VC++ 6.0 (Introductory, of course ).

It is fairly easy to understand and there is a whole chapter dedicated to data structures.

Share this post


Link to post
Share on other sites
NuffSaid: Ugh...either this is highly coincidental, or a sign from God that I shouldn''t program; if memory serves me right, that''s the same book we used as a textbook in my "Introduction to C++ Programming" class that I took in 10th grade (I''m going to 11th). And, if it happens to be the same book (does the book you''re talking about use misquitos as a sort of mascot?), then I have to say that it probably won''t do me much good. Because, frankly, I didn''t like it that much...it was OKAY, but not very GOOD. Even though the farthest we ever got into the book was about classes, I don''t forsee the following chapters being much better.

But...thanks anyway.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
oh you have the book he is talking about. I read the java one and didn''t like it very much. Ok how about this explanation: a linked list is a way of storing things. Why is it so complex? The reason is that computers can''t see memory in the same way that we can see stuff on paper. Imagine (or actually make) a list six or seven of numbers on a piece of paper. It works even better if you use graph paper and put each number in its own square, use single digit numbers it will be easier.

Now since you have the numbers lined up you can tell that they are all in the same list. So can the computer, if you are making an array. If you want the computer to print out all the numbers you start at the first box and work your way through them, printing as you go. However you don''t always want an array, sometimes you want something else. Now erase one of the numbers. You decide to loop through all the boxs and print again, but what do you do at that empty box? It can''t actually be empty of course, something is there, probably a 0. You can''t get rid of the box, that''s your problem. So what do you do? You can move all the boxes to the right of the empty box one space to the left but that takes a lot of erasing and writing doesn''t it? Just like it takes you a long time it will take the computer a long time.

Time to make a linked list. On a nice new sheet of graph paper use your pencil to draw around a box (so it stands out) and draw around a box next to it, so you have a pair of boxes. I''ll assume you put them side by side. You can put the pair of boxes anywhere you want, except in the upper left corner. In the upper left corner draw a circle with a line through it, that is the symbol for null. It represents nothingness, basically the concept of 0 when applied to objects of classes. Now in your pair of boxes put a number in the left box, this is the value. Next draw an arrow from the middle of the right box and make it point to null. That is a pointer, its value is null. Now you want to add more numbers to your list. Make another pair of boxes somewhere, anywhere will do. In the left put your second number, in the right make another arrow and point it to null, you should now have two pointing to null. Now erase the first node''s (that is what the pairs of boxes are called) arrow and draw it again, this time pointing to the second node. Do this several more times, put each node in a random part of the paper. The first node should not have any arrows to it, every other node should have one pointing to it. All nodes except the last should point to the next node in the list. The last node should point to null. Now you have a linked list.

Ok time to print. Start at the first node you drew and pretend you are the computer printing out the number in the left box. Now follow the pointer to another node and print, and so on. When you get to null stop. It is a little slower than going straight through an array of boxes in order but it works right? Now here is the nice part. Find a middle note to delete (like with the array). Let''s call it T for this. We''ll call the node it points to N for next and the node that points to it P for previous. Make P''s arrow point to N and then erase T. Erase everything. That''s it. You can now go through your print loop and if you have the arrows linked properly it should work. Of course in real code there are some temporary variables to deal with and other things but now do you see why you might want a list? The links keep everything organized. Since you can add more and more links you are essentially creating variables at run time. They don''t have names, they are just part of the list but they hold information just the same.

Share this post


Link to post
Share on other sites
Wow. I would like to thank the Anon. poster for that absolutely wonderful explanation of linked lists. With this newfound level of [almost complete] comprehension, I suppose I should go back and reread the chapters in the C++ books I have on linked lists. Thanks.

Does anyone else have any other explanation of anything that the anon. poster may have missed?

Share this post


Link to post
Share on other sites
quote:
Original post by Ghostface
Wow. I would like to thank the Anon. poster for that absolutely wonderful explanation of linked lists. With this newfound level of [almost complete] comprehension, I suppose I should go back and reread the chapters in the C++ books I have on linked lists. Thanks.

Does anyone else have any other explanation of anything that the anon. poster may have missed?



Look in the GameDev.net "Previous Featured Articles" section, under Programming. "Understanding Data Structures Part 1: Linked Lists" is the article.

Kevin

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!