I don`t really understand those linked lists.
http://www.cprogramming.com/tutorial/lesson15.html
A am asking for some extra examples. A linked list with just 3 items and without if, for, while, cin,.. would be fine enough.
Printable View
I don`t really understand those linked lists.
http://www.cprogramming.com/tutorial/lesson15.html
A am asking for some extra examples. A linked list with just 3 items and without if, for, while, cin,.. would be fine enough.
--Code:#include <iostream>
using namespace std;
struct list
{
int id;
struct list *next;
};
void print(list *h)
{
list *p;
p = h;
cout << "Listing of linked list" << endl;
// Have to use some loop construction here, so use "while".
while(p) {
cout << "id=" << p->id << endl;
p = p->next;
}
}
int main(void)
{
list *head = 0; // head is the first item of the list.
list *item;
// Get a "new" item (and set head to this value)
head = item = new list;
item->id = 1;
item->next = 0;
// we now have one item in the list.
// Show us what's in the list.
print(head);
// Lets add another one - first allocate new item and let "next" point to it.
item->next = new list;
// Move on so that item is the new item.
item = item->next;
item->id = 2;
item->next = 0;
// We should now see two items.
print(head);
// And one more.
item->next = new list;
// Move on so that item is the new item.
item = item->next;
item->id = 3;
item->next = 0;
print(head);
// Finally, clean up the list - again, this is not possible to do without a while
// (not in a generic fashion at least)
item = head;
head = 0; // Mark the list empty.
while(item) {
// We are about to delete "item", so we pick the "next" element up before we
// delete it - using data after delete is invalid.
list *temp = item->next;
delete item;
item = temp;
}
return 0; // All done, ok.
}
Mats
Recursion?Quote:
Originally Posted by matsp
It's tail-recursive, so the compiler should be able to optimize it.Code:void delete_list(list *head)
{
if(head)
{
list *next = head->next;
delete head;
delete_list(next);
}
}
Not necessarily recommending it, just responding to your "impossible" claim.
Well, that would mean a separate function to delete the list - I wanted to keep the code as small as possible, with no "unnecessary" functions - and of course, it just goes to show that this list is full of pedants - I'm one of them. :-)Quote:
Originally Posted by brewbuck
Why would you want to code list-deletion in-line everywhere it is required?Quote:
Originally Posted by matsp
No, that's not what I'm saying - I said I wanted this example to be as small and easy to follow as possible - adding functions can confuse things. Of course, if I were to use linked list in my application (assuming I had to do that, and not just use some pre-written library functions), I would of course have separate functions for inserting a new item, removing a selected item [if this is needed] and destruction of the entire list. But if someone asks for a SIMPLE example, I'm not going to write something more complicated just becasue I can avoid a while by using a recursive function. Recursion can make it hard to understand too (at least, it took me a little while to understand that - but maybe I'm just a bit thick... ;-) )Quote:
Originally Posted by brewbuck
--
Mats
A linked list with just 3 items is no simpler than a linked list with any number of items.
I'm also not sure if it is possible to do it with if, for and while (the recursive function still needs if).
If you don't understand the examples because of if, for and while, may-be you should learn about these first.
i want to know how to bake a cookie, but i don't want it to use butter, or dough... honestly how hard can it be, just a simple cookie... no ingredients...
i'm sorry that's not how it works. you need to learn how to mix the ingredients, even for just a cookie.
i hate it when people use "easy" and "simple" to describe what they want, not realizing what's involved. even not realizing how simple -that- really is. it's just a matter of time and understanding.
lol, "adding functions can confuse things" - oh gosh.
http://www.cplusplus.com/doc/tutorial/functions.html
is that better?
Personally, I find that well selected and well named functions make code, even example code, much easier to follow. It beats trying to figure out why a particular block of code exists in the first place, and helps to skip over that block of code once I understand why it is there.Quote:
I wanted this example to be as small and easy to follow as possible - adding functions can confuse things
Implementations will differ, but usually a list node contains two parts: the datum, and a reference of some sort to other nodes. So, if you had a singly linked list of integers it might look like this:Quote:
Originally Posted by sept
Create, manipulate, and maintain the data structure in your code.Code:
+------+ +------+ +-------+
| 1 |*-|--->| 2 |*-|--->| 3 | *-|---> NULL
+------+ +------+ +-------+
I decided to take a crack at it.
I am afraid this is in C, but here is a barebones example of what a list is. It only implements the simplest of list methods (add to head and print).
Code:#include <stdio.h>
#include <stdlib.h>
struct IntList {
int data;
struct IntList * next;
};
/**
* Adds data to the beginning of the list. Modifies the structure of the list.
* @param head The list to modify.
* @param addMe The data to add to the list.
*/
void IntList_add2head (struct IntList ** head, int addMe) {
// Create a new node to be inserted into the list.
struct IntList * NewNode = malloc (sizeof (struct IntList));
NewNode->data = addMe;
// Make the new node precede the head of the list.
NewNode->next = *head;
// Make the head point at the new node.
*head = NewNode;
}
/**
* Prints the contents of the list.
* Output should look like...
* HEAD -> 5 -> 1 -> 7 -> NULL
* @param head The list to print.
*/
void IntList_print (struct IntList * head) {
struct IntList * curr_node;
printf ("HEAD ->");
// The structure of this for loop is characteristic of linked lists.
for (curr_node = head; curr_node != NULL; curr_node = curr_node->next) {
printf (" %d ->", curr_node->data);
}
printf (" NULL\n");
}
int main (void) {
// The end of a list is always NULL. So, an empty list is one where
// the head is NULL.
struct IntList * head = NULL;
printf ("Welcome to the linked list example.\n");
// Repeatedly prompt the user for input and add items to the list.
for (;;) {
int new_value;
printf ("\n");
IntList_print (head);
printf ("Input a number (x to exit): ");
if (scanf ("%d", &new_value) != 1)
break;
IntList_add2head (&head, new_value);
}
return 0;
}
Linked List is a cakewalk... Just do simpler programming if you're not comfortable with for loops or whatever else you said, all knowledge of basic programming is required to do linked lists... they come AFTER you learn everything else like memory and loops.
If it helps you, try to draw a example on paper first to figure out what needs to happen to create/destroy/add/remove... then you can search/sort/ect... step by step, don't code 5 pages of code and expect it to work...
Something like this perhaps?Quote:
Originally Posted by sept
There are no algorithms here, perhaps that's what you were after? Its not really a linked list, being that all the nodes are statically allocated, but it follows the same linked node pattern which underpins the concept of a linked list.Code:#include <iostream>
struct node
{
int data;
node* next;
};
void print(node* head)
{
while( head )
{
std::cout << head->data << '\n';
head = head->next;
}
}
int main()
{
node n1; //Statically creating the nodes rather than 'new'
node n2;
node n3;
node n4;
n1.data = 5;
n2.data = 10;
n3.data = 20;
n4.data = 50;
node* head = &n1; //pointer to the start of the list
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = 0; //NULL pointer - end of singly-linked list
print( head );
}
Thanks for the integer example. I needed to load a linked list from a text file, so I am posting a version that does that.
The thing that drove me crazy for a while was that I wasn't malloc-ing (is that a word? :-) the space for the new data string in the new node, and then strcpy-ing (again?) the data into the newly allocated string of the node. Without those two steps, the same data was getting assigned to each node.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INPUT_LIMIT 101
char input_expression[INPUT_LIMIT] = {'\0'};
struct StrList {
char* data;
struct StrList * next;
};
/**
* Adds data to the beginning of the list. Modifies the structure of the list.
* @param head The list to modify.
* @param addMe The data to add to the list.
*/
void StrList_add2head (struct StrList ** head, char* addMe) {
// Create a new node to be inserted into the list.
struct StrList * NewNode = malloc (sizeof (struct StrList));
// The following two steps are critical to preserve the node's data...
if ((NewNode->data = malloc(strlen(addMe) + 1)) == NULL) {
perror("malloc"); return;
}
strcpy(NewNode->data,addMe);
// Make the new node precede the head of the list.
NewNode->next = *head;
// Make the head point at the new node.
*head = NewNode;
}
/**
* Prints the contents of the list.
* Output should look like...
* HEAD -> str1 -> str2 -> str3 -> NULL
* @param head The list to print.
*/
void StrList_print (struct StrList * head) {
struct StrList * curr_node;
printf ("HEAD ->");
// The structure of this for loop is characteristic of linked lists.
for (curr_node = head; curr_node != NULL; curr_node = curr_node->next) {
printf (" %s ->", curr_node->data);
}
printf (" NULL\n");
}
int main (void) {
// The end of a list is always NULL. So, an empty list is one where
// the head is NULL.
struct StrList * head = NULL;
FILE *file;
char buf[20];
float result;
printf("Enter file name >>> ");
scanf("%s", buf);
file = fopen(buf, "r");
if (file == NULL)
{
fprintf(stderr, "file %s not found\n", buf);
return 1;
}
printf ("Begin linked list example.\n");
while (fgets(input_expression,INPUT_LIMIT,file))
{
int new_value;
printf ("\n");
StrList_print (head);
StrList_add2head (&head, input_expression);
}
return 0;
}