Double linked list

[Sheldon]

Hi,

I am trying to understand linked lists and the different ways to write
a linked list and double linked list. I have been trying to get this
function called insert_word to work but to no avail. The function
receives a string from main and then inserts in the list the new word
in alphabetical order. Here is my function:

struct word { // double linked list. Here the list is global
and is first built
struct word *next; // This is the pointer to the next node
struct word *prev; // Pointer to the previous node
char *word; // This is the node that contains the data: a
string
};

struct word *list = NULL; // This is the main header for the list

// smalloc
// replaces malloc and always returns a valid pointer.
void *
smalloc(size_t size)
{
void *newobj;

newobj = malloc(size);
if (!newobj) {
fprintf(stderr, "Cannot allocate memory\n");
exit(EXIT_FAILURE);
}

return newobj;
}

// ************* MY FUNCTION **************

void
insert_word(char* newword)
{
struct word* currentnode = list; // creating a counter to loop over
the list
struct word* newnode = NULL; // new node to be inserted
struct word* prevnode = NULL; // node before current in loop
struct word* afternode = NULL; //node after current in loop

newnode = (struct word*) smalloc(sizeof(struct word)); // alocates
memory for new node

printf("Newword = %s\n",newword);

/* Insert new word in correct alphabetical order
Iterate over the list with a local pointer */
while (1) {
if (currentnode == NULL) { //List is empty. Appending data
printf("List is empty. Inserting first word\n");
newnode->word = newword;
newnode->next = NULL;
newnode->prev = NULL;
list = newnode; // changes the head pointer to point to the new
node so that it is the fist node in the list: it updates the list
afternode = newnode;
prevnode = newnode;
break;
}
if (strcmp(newword,currentnode->word) < 0) { // goes before the
current node
printf("Inserting word before %s node\n", currentnode->word);
newnode->word = newword; // assings the data
newnode->next = currentnode; // links the new node to the
current node
if (prevnode != NULL) {
newnode->prev = prevnode; // links the new node to the previous
node
} else {
newnode->prev = NULL;
}
currentnode = newnode; // move the current to point to
the new node
break;
} else if (strcmp(newword,currentnode->word) > 0) { // insert
after element
printf("Inserting word after %s element\n", currentnode->word);
newnode->word = newword;
if (currentnode->next != NULL) {
newnode->next = afternode;
} else {
newnode->next = NULL;
}
newnode->prev = currentnode; // links the new node to the
previous node
break;
}
afternode = afternode->next;
prevnode = prevnode->next;
currentnode = currentnode->next;
}
}

Any help would be truly appreciated.

Thanks,
Sheldon

 

[Richard Tobin]

I am trying to understand linked lists and the different ways to write
a linked list and double linked list. I have been trying to get this
function called insert_word to work but to no avail. The function
receives a string from main and then inserts in the list the new word
in alphabetical order. Here is my function:
[...]

insert_word(char* newword)
{
struct word* currentnode = list; // creating a counter to loop over
the list
struct word* newnode = NULL; // new node to be inserted
struct word* prevnode = NULL; // node before current in loop
struct word* afternode = NULL; //node after current in loop

newnode = (struct word*) smalloc(sizeof(struct word)); // alocates
memory for new node

printf("Newword = %s\n",newword);

You might as well fill in newnode->word here, rather than doing it in
various places below.

while (1) {
if (currentnode == NULL) { //List is empty. Appending data

Why's this test in the loop? You only want to test once whether
the existing list is empty.

if (strcmp(newword,currentnode->word) < 0) { // goes before the
current node
printf("Inserting word before %s node\n", currentnode->word);
newnode->word = newword; // assings the data
newnode->next = currentnode; // links the new node to the
current node
if (prevnode != NULL) {
newnode->prev = prevnode; // links the new node to the previous
node
} else {
newnode->prev = NULL;
}
currentnode = newnode; // move the current to point to
the new node
break;

You haven't updated prevnode to point to the new node as its next.

} else if (strcmp(newword,currentnode->word) > 0) { // insert
after element

You're checking that the new word should go after this word, but not
that it should go *immediately* after.

It would be simplest to just continue until you find the word it should
go *before*, and if you run off the end of the list handle the case where
it goes right at the end.

-- Richard

 

[copx]

Hi,

I am trying to understand linked lists and the different ways to write
a linked list and double linked list. I have been trying to get this
function called insert_word to work but to no avail. The function
receives a string from main and then inserts in the list the new word
in alphabetical order.

Linked lists can easily be written in generic form i.e. you could write
code that accepts any kind of node data, not just "words".
Your insert_word function could be generalized into a "insert sorted"
function which takes a pointer to the sorting function as an argument.

I have written a generic double linked list lib for the game I am working
on. It features an "instert sorted" function. Code links:

http://todoom.svn.sourceforge.net/viewvc/*checkout*/todoom/wrogue/src/lib/llist.h
http://todoom.svn.sourceforge.net/viewvc/*checkout*/todoom/wrogue/src/lib/llist.c

HTH,
copx

 

[copx]

Linked lists can easily be written in generic form i.e. you could write
code that accepts any kind of node data, not just "words".
Your insert_word function could be generalized into a "insert sorted"
function which takes a pointer to the sorting function as an argument.

I have written a generic double linked list lib for the game I am working
on. It features an "instert sorted" function. Code links:

http://todoom.svn.sourceforge.net/viewvc/*checkout*/todoom/wrogue/src/lib/llist.h
http://todoom.svn.sourceforge.net/viewvc/*checkout*/todoom/wrogue/src/lib/llist.c

HTH,
copx

Just wanted to add that you can find great educational material about linked
lists here: http://cslibrary.stanford.edu/

 

[pete]

Hi,

I am trying to understand linked lists and the different ways to write
a linked list and double linked list. I have been trying to get this
function called insert_word to work but to no avail. The function
receives a string from main and then inserts in the list the new word
in alphabetical order.

Here's how I would do that with a singley linked list:

/* BEGIN insert_word.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct list_node {
struct list_node *next;
void *data;
};

struct list_node *insert_word(struct list_node **head, char *newword);
int comparison(const struct list_node *, const struct list_node *);
void list_free(struct list_node *node, void (*free_data)(void *));
struct list_node *merge_lists(struct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *));
static struct list_node *list_merge(struct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *));
int list_fputs(struct list_node *node, FILE *stream);

int main(void)
{
char *array[] = {"the","quick","brown","fox",
"jumps","over","the","lazy","dog"};
char **ptr = array;
size_t index = sizeof array / sizeof *array;
struct list_node *head = NULL;

while (index-- != 0) {
if (insert_word(&head, *ptr++) == NULL) {
list_free(head, free);
head = NULL;
puts("node == NULL");
}
}
list_fputs(head, stdout);
list_free(head, free);
return 0;
}

struct list_node *insert_word(struct list_node **head, char *string)
{
struct list_node *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(strlen(string) + 1);
if (node -> data != NULL) {
strcpy(node -> data, string);
*head = merge_lists(*head, node, comparison);
} else {
free(node);
node = NULL;
}
}
return node;
}

int comparison(const struct list_node *a, const struct list_node *b)
{
return strcmp(a -> data, b -> data);
}

void list_free(struct list_node *node, void (*free_data)(void *))
{
struct list_node *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

struct list_node *merge_lists(struct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *))
{
if (tail != NULL) {
if (head != NULL) {
head = list_merge(head, tail, compar);
} else {
head = tail;
}
}
return head;
}

static struct list_node *list_merge(struct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *))
{
struct list_node *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;
list = sorted = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = head != NULL ? head : tail;
return list;
}

int list_fputs(struct list_node *node, FILE *stream)
{
while (node != NULL) {
if (fputs(node -> data, stream) == EOF) {
return EOF;
}
if (putc('\n', stream) == EOF) {
return EOF;
}
node = node -> next;
}
return '\n';
}

/* END insert_word.c */

 

[Morris Dovey]

pete wrote:
| Sheldon wrote:
||
|| I am trying to understand linked lists and the different ways to
|| write a linked list and double linked list. I have been trying to
|| get this function called insert_word to work but to no avail. The
|| function receives a string from main and then inserts in the list
|| the new word in alphabetical order.
|
| Here's how I would do that with a singley linked list:

<snipped>

I don't think you really need that much code. I did something similar
a while back for doubles (but can't remember why). It'd be easy to
reverse the ordering and/or use string data.

#include <stdio.h>
#include <stdlib.h>

struct element /* List element */
{ struct element *next;
double data;
};

struct element *list = NULL; /* List head pointer */

/* Add elements to the list in order of decreasing data values */

int add_element(double data)
{ struct element *cur, *new, *prv = NULL;

for (cur=list; cur; cur=cur->next)
{ if (data < cur->data) prv = cur;
else if (data == cur->data) return 1; /* Found in list */
else break;
}
if (new = malloc(sizeof *new))
{ if (prv) prv->next = new;
else list = new;
new->next = cur;
new->data = data;
}
else
{ fputs("add_element: Memory allocation failure\n",stderr);
exit(EXIT_FAILURE);
}
return 0; /* Added to list */
}

 

[pete]

pete wrote:
| Sheldon wrote:
||
|| I am trying to understand linked lists and the different ways to
|| write a linked list and double linked list. I have been trying to
|| get this function called insert_word to work but to no avail. The
|| function receives a string from main and then inserts in the list
|| the new word in alphabetical order.
|
| Here's how I would do that with a singley linked list:

<snipped>

I don't think you really need that much code.

I can think of two things I did,
that might have contributed to the seemingly extra code.
1 I didn't use a global variable
2 Three of the functions that I used,
list_free
merge_lists
list_merge
are completely generic, that is to say that they
can be used for lists of anything, even lists of lists.

Here's an example of list_free being used with a list of lists:
http://groups.google.com/group/comp.lang.c/msg/282e049159d3950d

 

[Morris Dovey]

pete wrote:
| Morris Dovey wrote:
||
|| pete wrote:
||| Sheldon wrote:
||||
|||| I am trying to understand linked lists and the different ways to
|||| write a linked list and double linked list. I have been trying to
|||| get this function called insert_word to work but to no avail. The
|||| function receives a string from main and then inserts in the list
|||| the new word in alphabetical order.
|||
||| Here's how I would do that with a singley linked list:
||
|| <snipped>
||
|| I don't think you really need that much code.
|
| I can think of two things I did,
| that might have contributed to the seemingly extra code.
| 1 I didn't use a global variable
| 2 Three of the functions that I used,
| list_free
| merge_lists
| list_merge
| are completely generic, that is to say that they
| can be used for lists of anything, even lists of lists.
|
| Here's an example of list_free being used with a list of lists:
| http://groups.google.com/group/comp.lang.c/msg/282e049159d3950d

Yuppers. I've done the same but am too lazy/sleepy to DAGS. I think I
ended up tossing part of my generic collection into
http://www.iedu.com/mrd/c/queue.c

The global list head pointer could, of course, be passed as a
parameter to add_element() - and I suspect that the application for
which I scribbled the function used only a single list (and I'm still
wondering what that application might have been <g>).

The point (I almost forgot!) was that it may be more helpful to post
the shortest compilable code that exhibits the requested behavior.
It's what we expect of people asking for help with debugging and,
seemingly, would work the same way in both directions.

 

[pete]

The point (I almost forgot!) was that it may be more helpful to post
the shortest compilable code that exhibits the requested behavior.

That's a good point.

I didn't think it was *very* bloated.

The part of my 140 line program,
that corresponded to OP's 90 line snippet, was just the functions:
insert_word,
comparison,
merge_lists,
and list_merge;
that's only 60 lines of code.

It's what we expect of people asking for help with debugging and,
seemingly, would work the same way in both directions.

He said he was interested in
"the different ways to write a linked list and double linked list",
so I showed him the way that I like.

I especially like to use the generic list for strings,
mostly for two reasons:
1 strings are the only data I know, that aren't more
complicated to use with a generic list node,
than with a specific type list node.
2 I have a small collection of functions that I'm
accustomed to using, for generic lists.

 

[Morris Dovey]

pete wrote:
| Morris Dovey wrote:
|
|| The point (I almost forgot!) was that it may be more helpful to
|| post the shortest compilable code that exhibits the requested
|| behavior.
|
| That's a good point.
|
| I didn't think it was *very* bloated.

It wasn't, really. There may be a few people snickering because they
remember how weird I get about not squandering bytes (a consequence of
learning to program on a slow computer that had /no/ RAM at all).

| The part of my 140 line program,
| that corresponded to OP's 90 line snippet, was just the functions:
| insert_word,
| comparison,
| merge_lists,
| and list_merge;
| that's only 60 lines of code.

Ninety to sixty is a definite improvement, IMO (see above).

|| It's what we expect of people asking for help with debugging and,
|| seemingly, would work the same way in both directions.
|
| He said he was interested in
| "the different ways to write a linked list and double linked list",
| so I showed him the way that I like.

As a (sometimes) C programmer, I can see why you like it. OTOH, if I
were a newbie learning C, my reaction would be: "Holy smokes! Does it
really take all that just to make a list?"

I think (but can't prove) there's an exponential relationship between
length of example and amount of effort required for a newbie to grasp
a programming concept or technique.

| I especially like to use the generic list for strings,
| mostly for two reasons:
| 1 strings are the only data I know, that aren't more
| complicated to use with a generic list node,
| than with a specific type list node.
| 2 I have a small collection of functions that I'm
| accustomed to using, for generic lists.

Yup - makes perfect sense to me. I have a couple of generic
collections somewhere - I've been promising myself that I'd organize
them someday (RSN), and yet it seems that whenever I actually /need/ a
list, I develop this strange compulsion to pick just the functions I
need and optimize 'em for the task at hand (see above again).

I strongly suspect that was how add_element() came to be.