Archived

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

Ghostface

Linked Lists? HUH?!?

Recommended Posts

Ghostface    122
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
Kylotan    9881
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
Ghostface    122
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
Kylotan    9881
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
NuffSaid    122
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
Ghostface    122
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   
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
Ghostface    122
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
khawk    2904
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
cyn    138
no offense, but going from ''i need help'' to ''i hate programming'' back to ''i almost understand this crazy stuff'' prozac mood swings is not going to help your understanding of anything. any of those learn in 21 day books gives you the bare foundation. every other application (linked lists, hash tables, fast graphics, etc) is all an uphill battle. it is very unlikely that you will look at a new, complex concept and immediately say ''ok, i understand this and i can write professional quality code.'' you are going to have to stick with it. as for the books, my personal suggestion for a foundation is C++ Program Design by Cohoon and Davidson. that was the book i used in my college level programming classes and has pretty good sections on the more advanced topics.

cyn

Share this post


Link to post
Share on other sites
ShawnO    145
Take a look at http://cslibrary.stanford.edu/. There is a series of pointer, memory and linked list lessons, some downloadable as .pdf files. I have found them very useful.

Shawn

Share this post


Link to post
Share on other sites
Ghostface    122
cyn: Contrary to your comical statement, I am not going into "prozac mood swings". In all honesty, everything you said is true: I do need help, I hate programming, and I almost completely understand the concept of linked lists. But, what you don''t seem to realize is that all of these feelings inhabit my mind simultaneously.

I really do hate programming, however I have two reasons for learning it: first, my true passion is game design. Even though I am only 15, I am not so naive to think that one can break into the industry as a game designer. So programming seems just as good a way as any other...

Second, I want to learn the intricacies of programming so as to avoid any over-ambition in my game designs.

Thanks for the suggestion

Share this post


Link to post
Share on other sites
MaNiAk    122
Ghostface... its pretty simple. A pointer would be basically a name for an adress. A pointer points to data instead of being the data itself. When you make a variable basically the program behind the scenes make a pointer to data and it deletes it for you. But when you make a pointer you are saying that you want to make the data yourself and point to it and also delete it yourself.

when you do a *name when you are declaring its a pointer:

int *iVar = NULL; //Pointer to int

now initially it shouldn''t be pointing to any data so to be on the save side i have it pointing to NULL (0) which means its pointing to no data for sure (if i try changing data it wont change any part of my memory). Now if i were to put some data in it i could:

iVar = new int; //Creates data for the var to be pointing to

or i could:

iVar = (*int) malloc(sizeof(int)); //C style way of creating a new int

malloc, or memory alloc is the way of c style data creation. Let me explain it... the (*int) is to cast the data as a pointer integer because it normally is not (you have to cast to whatever pointer type it is with the star before it). sizeof(type or variable) gets how many bytes the type is, which is how much memory we are going to need to store.

memory is arranged in bytes of data which is eight bits each. 1 byte can hold 256 numbers... 2 bytes can hold more... 3 bytes can hold more... and so on, so basically the bigger the type, the more bytes it must use, int i believe is 2 or 3 bytes. so when you do a sizeof(int) it will return 2 or 3 (not sure off the top of my head), which means if you do a malloc(sizeof(int)) it will return a memory adress of your newly created data.

malloc(sizeof(int)) returns

|1|2| = 2 bytes of data

What if we wanted to define the data? Simple you just put a star behind the pointer and then its treated like any other variable.

*iVar = 30; //We had to put the star before it to make it like a normal variable

I am aware that you use a star when creating a pointer to, believe me the compiler wont get confused or anything and start making another pointer.

int *iVar; //Pointer creation

*iVar = BLA; //setting pointer data

Now you ask how would i make an array dynamically (when its running). Well the new keyword, or malloc make it possible. A pointer is basically a number to a spot in memory... its kind of like a sign pointing to a house number. Every time you add 1 to a pointers adress it increments the array number. Well first let me tell you how to create a pointer to an array.

int *iVar; //Pointer creation

iVar = new iVar[numofelements]; //Creates an array

iVar = (*int) malloc(sizeof(int) * numofelements); //C way of creating an array

What this does is create an adress to an array. To access different parts of the array you would just add the number of the element you are trying to acess. Which you can use * to treat its like a normal variable... o ya btw u can use the * with parentheses to save some work. SO to set an element in our to pointer to an array you would just do:

*(iVar + 3) = 30; //this sets the third entry in the array to 3

Finally, as for linked lists, u gotta go find some tutorial on the net which isn''t hard.

-MaNiAk

Share this post


Link to post
Share on other sites
Warpstorm    122
If your truly hate programming, I doubt that you will be able to get a job as a programmer in a game company. A love of programming for it''s own sake is one of the primary things I look for in prospective programmers (besides talent) and I''m sure most other people in the position of hiring programmers will agree. In addition, games programmers must love playing games, otherwise they won''t have the passion to make the next great game.

Besides, do you really want to do something you truly hate for years just to have the chance of doing something you love? I''d try looking for a different path to doing what I liked.

Now if only I could live on what the game companies offered me, I''d take my own advice...

Share this post


Link to post
Share on other sites
Ghostface    122
MaNiak: the fact that I have a terrible headache right now, combined with the fact that your post is too long, means that I''ll have to read it later

Warpstorm: there are only two reasons why I hate programming; the first one is that whatever half of the brain is responsible for analytical things, obviously is difunctional in me The second reason is a result of the first reason: programming seems too tedious for me. I''m much better at imagining and creating game stories and gameplay systems. However, my analyitical prowess is severely lacking (well...except for when it comes to gameplay systems. I think that''s kinda odd)

Share this post


Link to post
Share on other sites
KaMiKaZ    122
personally, i think that using linked lists is totally optional. although some situations might totally require using a linked list, for the majority of programs (including games) they are many ways to get around using them. plus, they''re a huge hassle... give me an old fasion array any day
~~KaMiKaZ~~

Share this post


Link to post
Share on other sites
Forcas    181
In some situations you really have to learn linked lists. It''s a lot better than making an array that''s way too big and eats up all your RAM. If you''re making a game, you''ll want as much free RAM as possible.

The bottom line is this: If you''re making an insanely large structure that will grow and shrink use linked lists. If you''re making a smaller structure that you''re pretty sure won''t surpass a certain size, use collections or dynamic arrays. If you''re making something that always stays the same size, just use an array.

When I learned about linked lists, it also helped me learn why pointers were useful.


-Forcas


"Elvis is alive. He is Barney the purple dinosaur. He is the pied piper that leads our children into the wages of sin and eternal damnation."



Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
i''m not completely sure on this, but who says you have to go from being a programmer to becoming a game designer? i''m sure it can help if understood programming and being a designer, but you really don''t have to learn it. i think there are different paths that you can take. if you''re hating programming now, how you are you going to like it when that''s your job and you have to do it everyday for the whole day? people that become programmers do it because they love to program, and love the challenge, and you''re already hating it, and you''ve barely scratched the surface.

Share this post


Link to post
Share on other sites
justinhj    122
I agree with the previous post that you don''t have to learn to program to be a game designer. You may find it helpful to learn how to use a multimedia authoring package like Director, since then you can test your game design skills by making mock up versions of your game without doing any programming. This is limited to screen layouts and story flow type design however.

If you don''t enjoy programming then I think you will find it very hard to be good at it. To really understand a linked-list structure you should try to code one; each time you get stuck you will have to learn something more about the problem. Eventually you will understand them and have a correct implementation, and if you get pleasure from that you are likely going to make a good programmer.

Share this post


Link to post
Share on other sites
c_wraith    122
quote:
Original post by Forcas
In some situations you really have to learn linked lists. It''s a lot better than making an array that''s way too big and eats up all your RAM. If you''re making a game, you''ll want as much free RAM as possible.

The bottom line is this: If you''re making an insanely large structure that will grow and shrink use linked lists. If you''re making a smaller structure that you''re pretty sure won''t surpass a certain size, use collections or dynamic arrays. If you''re making something that always stays the same size, just use an array.



I thought the same thing about size comparisons between dynamic arrays and linked lists. Then I learned something interesting. This depends on your interface with the array/linked list. In particular, this is true when your list/array stores pointers to objects, rather than the object themselves. In that case, if you use n elements, the amount of memory used by those n objects is the same, regardless of how you store the list of pointers to them. So all that matters is comparing the memory used by the linked list to the memory used by the array. Now, consider the node structure for a typical doubly linked list. It contains a pointer to its contents, a pointer to the previous, and a pointer to the next. Given that most compilers align structures to power of 2 boundries, that will usually end up being 16 bytes, and it would require 12 at minimum on a 32 bit machine. So that''s 12 * n or 16 * n bytes for the nodes. Now consider an array of pointers. Each pointer is 4 bytes. In a growing only dynamic array, the array will never be larger than double the number of elements, or 8 * n bytes. In a dynamic array that grows and shrinks, the array''s size will never be more than 4 times the number of elements, or 16 * n bytes.

Are you still sure linked lists are more memory efficient?

Ok, then, you might be wondering "what if you store the object directly in the linked list nodes and array?" Well, there''s no point storing directly into the array unless the objects are only 4 bytes. It''s still faster to iterate over an array of pointers than to iterate over a linked list. It might potentially reduce the overhead for a linked list node by 4 bytes, but that''s not likely due to the overhead imposed by aligning to a power of 2 boundry as most compilers do. Switching to a singly linked list can cut the overhead further, but the power of 2 boundry is still an issue, and it significantly removes functionality as opposed to a dynamic array or doubly linked list.

The only advantages linked lists really have over dynamic arrays are these:
1. They are better when order matters, and many elements are being inserted/removed from the middle. However, if you have to search for the insert/remove position, (balanced) binary search trees are even better than linked lists. If elements are only being inserted and removed from the ends, dynamic arrays can do better. If order doesn''t matter, dynamic arrays do better.

2. You have a HARD real-time constraint. Dynamic arrays are faster on average for the above operations. However, every O(n) operations, you have one particular insert/delete that takes O(n) time. In most situations, this doesn''t matter. When it does, linked lists are superior.

It might seem like I''m kind of against linked lists... I suppose I am. They are incredibly overused structures, and I''ve taken enough data structures courses to see that there are better structures for the majority of their common uses. That caught me by surprise when I realized it, because I''d been a big fan of linked lists before that. However, dynamic arrays are really a lot more efficient than I had thought, and I found them to be superior to linked lists in most cases.

Share this post


Link to post
Share on other sites
bstepa    122
Here''s a great C++ book. It''s definately work it. I have an older edition but still a great book to own. It''s written by the creator of C++. You can also search Gamedev.net or Flipcode.com for tutorials and explanations on link lists.

The C++ Programming Language Special Edition

Share this post


Link to post
Share on other sites
Ghostface    122
First of all, I would like to thank everyone for their posts.

Second of all, I would like to say that I still beleive that my reason for learning how to program is perfectly valid. For those of you who read Game Developer magazine, take a look at the April 2001 issue''s "Soapbox" section (the topic of which is "Whatever Happened to the Designer/Programmer?") for further reasons that support my logic.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
yeah linked lists aren''t as good as a lot of other structures but I think they are an important step in learning how to program. They are one of the first types that newbies can learn how to make. They are also a good way to learn about pointers, memory, and recursion.

Share this post


Link to post
Share on other sites
Kylotan    9881
Ghostface: I agree that it is better if designers at least know the basics of programming before taking up a career in designing. After all, game design requires a good detail of understanding of the whole process, of which programming is an important part (but not the only part, I stress). And designers are being called upon more and more to do basic scripting for the game, which is similar to programming in many respects.

But, be warned: most designers don''t seem to make it into the industry in an overall design role. They tend to make it up to that position either through testing, or programming, or some sort of auxiliary design (eg. map editing). So be sure to specialize in something while you work towards the designer goal.

Share this post


Link to post
Share on other sites