Originally Posted by
cold_dog
well..ok I will try to write those functions...but...I have no idea of what I just did...my question is about the program running even though I did it wrong...I don't understand quite well about this linked list thing...
The idea of a "linked list" is something of an abstract one. its easy to imagine a list being a big object in memory, wheras in fact its just a bunch of scattered objects in memory, which contain pointers. These pointers are the "links", which allow the objects to function as a list together. creating a linked list is a good test of how well you really understand pointers (one of the big milestone hurdles for any new programmer to jump across)
Code:
+----+-----------------------------+
|1234| Addr 58 (Pointer to Head) | We always know where the head is, but rely
+----+-----------------------------+ on pointers to maintain the "links" between the
other nodes
+----+-----------------------------+
| 1 | gobbledeegook |
+----+------------------+----------+
| 2 | Node Data(int 3) | Addr 10 |
+----+------------------+----------+
| 3 | gobbledeegook |
+----+-----------------------------+
| .. | ........... |
+----+------------------+----------+
| 10 | Node Data(int 2) | Addr 99 |
+----+------------------+----------+
| 11 | gobbledeegook |
+----+-----------------------------+
| 12 | gobbledeegook |
+----+-----------------------------+
| .. | .......... |
+----+-----------------------------+
| .. | .......... |
+----+-----------------------------+
| 57 | gobbledeegook |
+----+------------------+----------+
| 58 | Node Data(int 4) | Addr 2 |
+----+------------------+----------+
| .. | .......... |
+----+------------------+----------+
| 99 | Node Data(int 1) | Addr NULL|
+----+------------------+----------+
sorry for the naff ASCII drawing
The numbers along the left-hand column might be your memory addresses. The bigger right-hand column might be whats at each address (gobbledeegook is unused by your program, maybe memory in use elsewhere, or junk left over from other programs.)
Code:
#include <iostream>
struct node_t // 'blueprint' for our list nodes.
{
int data;
node_t* next;
};
node_t* node_create(node_t* head, int i)
{
node_t* newnode = new node_t; // new node is created (will become new head)
newnode->next = head; // old head becomes the 2nd element.
newnode->data = i; // new node gets data
return newnode; // returns a pointer to the new head, back to the caller.
}
int main()
{
node_t* head(NULL); // We begin with a pointer to NULL - our list has 0 elements to begin with.
// head is always a pointer to the first element in the list.
const int size(10); // lets have 10 elements.
// build a list in 'reverse' order.
for(int i(0); i!=size; ++i)
head=node_create(head, i);
// each time this is called, we add a new element, which becomes the new "head".
// output list, and delete each node as we go along.
// we built the list in reverse, so head is still always the first element
while(head)
{
std::cout << head->data << std::endl;
node_t* temp = head; // temporary placeholder for old head before deleting
head=head->next; // 2nd element becomes head
delete temp; // clean up old head.
}
}