Linked lists

Linked lists..=)

they are allocated chunks of data that are linked together by pointers in C/C++

you usually have the head of the list and then the data chain is attached to it dynamically

struct item {
char data;
struct item *node;
}

this leaves an empty pointer to no man's land.. make sure to secure it
struct item head;
struct item *current_node; //this will point to the current node
head.node = NULL;

** remember to assign the current_node pointer to something
current_node = head
** assigns it to head

** add some data to it
current_node->data=255;
** notice the indirection pointer.. that's because you are using a pointer to access the data

** add another node
current_node->node = new item
** this allocates memory for the new node
** use can use malloc if you like

now that the new node is created .. why not jump to it
current_node = node
** the pointer current_node now is at the newly created node's memory address
** secure it
current_node->node = NULL;
** add something
current_node->data=254;

and make sure to delete your list after you are done with it


I hope this helps


please do not complain why I'm not using semicolons all the time... this is just an example









Edited by - goofprog on September 29, 2001 12:13:16 AM

quote:

---

Original post by GoofProg
Linked lists..=)
...
I hope this helps

---

Except for the fact that goober _specifically_ asked for a tutorial/explanation that doesn''t require knowledge of C-derived languages, probably.

Linked lists are collections of data in which each element - often called a node - is linked to the next; in doubly linked lists each node contains a link to the next and previous elements. The only point in the list that is known is the "head" or "top", which implies that finding an element involves traversing the list from the top down till the node matches the characteristics specified (such as a value). ie, find() is an O(n) operation.

Insertion of an element into a linked list is extremely fast, which is its most significant advantage over vectors (arrays). (insert() on linked lists is O(1), ie constant time as opposed to O(log n) for vectors). Insertion (and deletion) require some care so that you don''t lose the pointer to the second "half" of the list.

That''s a brief and fairly abstract definition of linked lists. I''m sure a search on Google should turn up some good material.

Thanks for the clairification, but goober DOES need to use a programming language that supports pointers such as c/C++ in order to take advantage of linked lists :0)

quote:

---

Original post by GoofProg
...goober DOES need to use a programming language that supports pointers such as c/C++ in order to take advantage of linked lists :0)

---

In terms of implementation, most definitely. However, conceptual understanding should be language independent and make the knowledge portable between languages. Perhaps some language out there only uses the term "references" in the literature, or only supports an "address-of" operator (no explicit pointers); such a language can still be used to implement a linked list.

You could build a linked list in VB using it''s hybrid object pointer/references.

This kinda shows a single linked list. You have nodes that have data in them and something that can reference another node, which in turn has data and references yet another node.

In C or pascal you''d use a struct and a pointer, in VB you could hack something together with object references, in Java you''d have to use the built-in list. With C++ you''d use the provided stl::list.

Node1
| |
| +-Data1
+->Node2
   | |
   | +-Data2
   +->Node3
      | |
      | +-Data3
      +-> 
 

Magmai Kai Holmlor
- Not For Rent

quote:

---

Original post by Magmai Kai Holmlor
in Java you'd have to use the built-in list.

---

Uhmm...?

public class ListNode { public Object data; public ListNode next; }

Of course thats not a really good OO way to write a list, but you get the picture. Its more or less the same as the implementation in C. (BTW...why do you think most recent datastructures books use Java? You'd think there was a limit to how much you could write about the "built-in list")



"A society without religion is like a crazed psychopath without a loaded .45"

Edited by - Arild Fines on October 2, 2001 12:05:24 PM

Oluseyi''s statement
"...conceptual understanding should be language independent and make the knowledge portable between languages..."
is the exact reason why I need a general idea of how linked lists work. I picked on c++ because all of the structure diagrams I have seen resemble it. I can recognise c++ structure diagrams, but not work out what they do. I find the idea of learning a new language, just to understand an abstract idea, silly. So, if anyone who knows about linked lists and would like to bear with me, please post something more fitting with my original request.
Ta.

"Of all the things I''ve lost, I miss my mind the most."
Goober

quote:

---

Original post by Arild Fines

  
public class ListNode
{
   public Object data;
   public ListNode next;
}
  

---

Yuck! Each ListNode contains another ListNode! What, pray tell, does the constructor look like? How do you intialize a ListNode when you need to initialize the ListNode within it, and the ListNode within that, and the ListNode within that... ad infinitum .

Magmai knows what he's talking about; you aren't quite clear on it yet. This is nothing like the C implementation. That's what you get in a language without pointers. (And you can't pass constant references? I'll pass, thank you, data structures books notwithstanding).

quote:

---

...why do you think most recent datastructures books use Java?

---

Because Java includes a huge library of pre-defined, standardized functions - especially output functions - that make it that much easier to write data structure programs and display them. Also because lots of today's intro programming students aren't CS majors, or even programmers, and only need a cursory introduction to the principles.

EDIT: formatting.

Edited by - Oluseyi on October 2, 2001 10:58:04 PM

Yea.. as long as the language supports addressing memory locations ... I can see a programming language using linked lists.. such as delphi.. urr pascal =).

BTW.. doesn''t using STL cause a performance crunch?

quote:

---

Yuck! Each ListNode contains another ListNode! What, pray tell, does the constructor look like? How do you intialize a ListNode when you need to initialize the ListNode within it, and the ListNode within that, and the ListNode within that... ad infinitum .

---

*cough* all java objects are refrences, not values *cough*

// In C++: class ListNode { public: void* data; ListNode* next; }; // Is essentially equivelent to the Java version: public class ListNode { public Object data; public ListNode next; }

In java anything but a datatype (char, int, long, etc.) automaticly extends java.lang.Object. Every object is essentially created with "new", and then garbage collected for you. So the C version of type "T" where T is an Object would be considered "T*", but would be treated like "T&" (no derefrencing needed).
This is what makes java a good language for teaching data structures, the convienience of pointers without the hassle of memory management.



"If consquences dictate our course of action, it doesn''t matter what''s right, it''s only wrong if you get caught."
- Tool

My name is Alpha (a.k.a. "Head" of the household). I am the beginning, and as of right now, I am also the end since no one is attached to me. Look, here comes my first child, we shall call her Beta. She takes my right hand. I am still the beginning, but she is now the end. Here comes my second child, his name is Charlie. He takes Beta''s right hand. I am still the beginning, Beta is in the middle, and Charlie is at the end. Wait...here comes my mother''s mother, Gamma. She now takes Charlie''s right hand. It is now Alpha->Beta->Charlie->Gamma.

Here comes my pet dog. His name is Delta. I want to keep our family organized. How do I do that? Start with me (Alpha) and ask for my data (name). If my dog''s name is alphabetically higher, go to the person who''s hand I am holding and repeat. So, Delta goes to Beta (since Delta > Alpha). Delta is greater than Beta, so follow the linked hands to Charlie. Delta, once again is greater, so follow the linked hands. Whoa...Delta isn''t greater than Gamma. This is where he belongs. Delta breaks the link between Charlie and Gamma. Delta''s left hand now grabs Charlie''s right hand, and Delta''s right hand now grabs Gamma''s left hand, i.e. Delta is inserted between Charlie and Gamma.

Final result: Alpha->Beta->Charlie->Delta->Gamma where each person is a "node". Alpha is the "Head". Gamma is the "tail". All linked together with their hands.

Sorry...it''s late and I felt poetic and nerdy. Hope this is what you''re looking for.

quote:

---

Yuck! Each ListNode contains another ListNode! What, pray tell, does the constructor look like? How do you intialize a ListNode when you need to initialize the ListNode within it, and the ListNode within that, and the ListNode within that... ad infinitum .

---

Your lack of knowledge about Java is a bit scary, especially given some of the latest slagfests targeting Java on this forum . As wayfarer pointed out, those are actually references to ListNodes. The ListNodes are not embedded recursively within themselves, as you seem to think.(Do you really think any compiler would have allowed that?)

quote:

---

Magmai knows what he's talking about; you aren't quite clear on it yet. This is nothing like the C implementation.

---

Nope. Magmai doesn't know what he's talking about and neither do you. This is exactly like the following C implementation(except for that ugly void* stuff)

struct ListNode { void* Data; ListNode* Next; };

quote:

---

That's what you get in a language without pointers. (And you can't pass constant references? I'll pass, thank you, data structures books notwithstanding).

---

Java isn't a language without pointers, its a language without pointer arithmetic.

quote:

---

(me: )...why do you think most recent datastructures books use Java?

(Oluseyi: )Because Java includes a huge library of pre-defined, standardized functions - especially output functions - that make it that much easier to write data structure programs and display them. Also because lots of today's intro programming students aren't CS majors, or even programmers, and only need a cursory introduction to the principles.

---

Bullshit. Just take a look at the selection of Alg&DS books for Java out there. There are quite a few that are way beyond the "cursory introduction" level. And the console IO functionality in Java is by far inferior to that of C and/or C++. No, the main reason why these authors choose Java over C/C++ is that you can deal with potentially difficult topics without getting bogged down in irrelevant memory management issues.

(Magmai: Did it ever occur to you that the "built-in list" is also written in Java?)


"A society without religion is like a crazed psychopath without a loaded .45"

Edited by - Arild Fines on October 3, 2001 9:11:04 AM

Go check out my tut on linked lists at my website at www.infantrydb.com/kingsrevenge

Eric Wright o0Programmer0o

AcidRain Productions

without the "hassel" of memory management you say ?
bahhh.....that is the sign of a lazy programmer who doesn''t know how to clean up after himself.

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."
- Mr. T

I stand corrected.

quote:

---

without the "hassel" of memory management you say ?
bahhh.....that is the sign of a lazy programmer who doesn't know how to clean up after himself.

---

Actually, being as Java is a purely high-level language, the guys at Sun realized that not only would removing pointers make the language easier to use, but it would make it roubust in the fact that memory leaks are impossible.
Think about this: with the number of badly-written Java applets floating around on the web, imagine if those apps were leaking memory or trying to read and write memory that they shouldn't? Would you want a web page to do that?
It also completly liberates the Java programmer from having to even think about the architecture of the underlying machine (memory alignment issues and such).
Of course, these things come at a price. Since all Objects are created with new and then tracked by the garbage collector, Object creation becomes one of the slowest operations you can to in Java. You also lose control of when unused memory actually gets freed (although the Java2 VMs are pretty good about this).
In essence: C/C++ and Java do things different for a reason. It's not being lazy, it's offering developers options about how they want to implement specific solutions.

"If consquences dictate our course of action, it doesn't matter what's right, it's only wrong if you get caught."
- Tool



Edited by - wayfarerx on October 3, 2001 12:42:18 PM

quote:

---

without the "hassel" of memory management you say ?
bahhh.....that is the sign of a lazy programmer who doesn't know how to clean up after himself.

---

I'm not going to argue the merits of garbage collection versus no garbage collection. There are valid arguments on both sides of that debate. (And let's not forget the three most important virtues of a programmer: Laziness, hubris and impatience. )
All I was saying is that if you are going to teach advanced datastructures, you don't want to cloud the issue by having to teach memory management as well.


(BTW...I'd love to have some maid clean my appartment for me, instead of having to do it myself. I guess that makes me lazy...)



Edited by - Arild Fines on October 3, 2001 1:02:05 PM

There are lots of languages that use linked lists without memory access. Anyone ever hear of Prolog, Lisp, Scheme, or ML? Linked list support is built into these languages.

The way these languages see linked lists is that there is a head and a tail. The head contains data the tail is the rest of the list, which itself is a list.

Oh, here''s the Java constructor:

public ListNode( Object _data) { data = _data; next = null; }

A linked list is basicly a structure containing two structures within that point to other structures; previous and next .

struct node
{
node* next;
node* prev;
}

ok, we have a structure that contains references to itself within. What are these referances within used for you ask? Well, lets continue the example.

node* FirstNode=new node;

Alright, we have the first node(if you don''t know what addresses are and how they effect variables, then you need to go learn that before you continue reading).

Since this is a structure and not a class, you''ll have to manually do the following:

FirstNode->next=NULL;
FirstNode->prev=NULL;

So you want to make this a linked list? Ok, well, you''ll need to allocate another node.

node* NewNode=new node;

Now what? Ah yes, we want to LINK this new node to the FirstNode. This is how:

FirstNode->next=NewNode;

Cool, now if we check FirstNode->next, we''ll actually be referencing NewNode. How cool is that. That''s not all though. We need to do more setup to NewNode before we continue. NewNode has to be setup so we can see where the previous node is(this setup is esential to the adding and deleting of new nodes).

NewNode->prev=FirstNode;
NewNode->next=NULL;

NULL in this case means end of link list.

Now you''re wondering why the hell we did this. It''s so you can allocate any number of nodes dynamicly. Say you don''t know how many monsters you want in your game. With a linked list you can add and subtract monsters from the linked list all you want...dynamicly. You''re only limited to how much memory you have, instead of some static array.

Ok, you want to know how to use the linked list now huh? Well, you have your FirstNode. You use it like this:

node* CurrentNode=FirstNode;

Ah yes. now CurrentNode is the same as FirstNode. What now? Now we can cycle through the list :D. You don''t ever want to cycle through the nodes with the FirstNode. If you did, you would lose your home reference address.

while(CurrentNode)
{
//do some stuff

CurrentNode=CurrentNode->next;
}

The above will cycle through all the allocated and linked nodes. Adding nodes and deleting nodes can be a little tricky, so we''ll leave that up to you to figure out.

By the way, this is legal in C++:

FirstNode->next->next->next->next...to, well, as many as C++ allows you to do I guess.

Hope I helped.