473,692 Members | 2,166 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Double linked list

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_FAILU RE);
}

return newobj;
}

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

void
insert_word(cha r* 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("Inserti ng 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("Inserti ng 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

Jun 11 '07 #1
9 4900
In article <11************ ********@g4g200 0hsf.googlegrou ps.com>,
>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(ch ar* 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("Inserti ng 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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Jun 11 '07 #2

"Sheldon" <sh******@gmail .comschrieb im Newsbeitrag
news:11******** ************@g4 g2000hsf.google groups.com...
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/vi...rc/lib/llist.h
http://todoom.svn.sourceforge.net/vi...rc/lib/llist.c

HTH,
copx
Jun 11 '07 #3

"copx" <co**@gazeta.pl schrieb im Newsbeitrag
news:f4******** **@inews.gazeta .pl...
>
"Sheldon" <sh******@gmail .comschrieb im Newsbeitrag
news:11******** ************@g4 g2000hsf.google groups.com...
>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/vi...rc/lib/llist.h
http://todoom.svn.sourceforge.net/vi...rc/lib/llist.c

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

Jun 11 '07 #4
Sheldon wrote:
>
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(st ruct list_node **head, char *newword);
int comparison(cons t struct list_node *, const struct list_node *);
void list_free(struc t list_node *node, void (*free_data)(vo id *));
struct list_node *merge_lists(st ruct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *));
static struct list_node *list_merge(str uct list_node *head,
struct list_node *tail,
int (*compar)(const struct list_node *,
const struct list_node *));
int list_fputs(stru ct list_node *node, FILE *stream);

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

while (index-- != 0) {
if (insert_word(&h ead, *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(st ruct list_node **head, char *string)
{
struct list_node *node;

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

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

void list_free(struc t list_node *node, void (*free_data)(vo id *))
{
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(st ruct 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(str uct 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(stru ct 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 */

--
pete
Jun 12 '07 #5
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(dou ble 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_elem ent: Memory allocation failure\n",stde rr);
exit(EXIT_FAILU RE);
}
return 0; /* Added to list */
}

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
Jun 12 '07 #6
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....2e049159d3950d

--
pete
Jun 12 '07 #7
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....2e049159d3950d

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.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
Jun 12 '07 #8
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.

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.

--
pete
Jun 12 '07 #9
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.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
Jun 13 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
15092
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition should be kept for references to previous element of list. Here is my solution below: struct node {
4
3600
by: JS | last post by:
I have a file called test.c. There I create a pointer to a pcb struct: struct pcb { void*(*start_routine)(void*); void*arg; jmp_bufstate; intstack; }; structpcb*pcb_pointer;
32
5932
by: Clunixchit | last post by:
How can i read lines of a file and place each line read in an array? for exemple; array=line1 array=line2 ...
6
2231
by: deanfamily | last post by:
I am re-posting my second problem. I have a double-linked list. I need to know if it is possible to remove just one of an item, instead of all that match the given criteria with the remove() command. Any thoughts?
3
3319
by: Little | last post by:
Could someone help me get started on this program or where to look to get information, I am not sure how to put things together. 1. Create 4 double linked lists as follows: (a) A double linked list called NAMES which will contain all C like identifiers of less than 256 characters long identified in the input file F. Each identifier will be represented by a triple (I, length, string) where I is used to identify the type of
1
4157
by: Little | last post by:
Could someone help me figure out how to put my project together. I can't get my mind wrapped around the creation of the 4 double Linked Lists. Thank your for your insight. 1. Create 4 double linked lists as follows: (a) A double linked list called NAMES which will contain all C like identifiers of less than 256 characters long identified in the input file F. Each identifier
3
472
by: Little | last post by:
Could someone tell me what I am doing wrong here about declaring mutiple double linked lists. This is what the information is for the project and the code wil be below that. Thank your soo much for your assitance in helping me solve this problem. Information: Create 4 double linked lists as follows: (a) A double linked list called NAMES which will contain all C like
4
4281
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event is stored in a double linked list, the whole list is sorted for the next round. My problem appears when subjecting the program to heavy load, that is, when I run the simulation for more than 10,000 miliseconds (every event occurs in...
6
4155
by: tgnelson85 | last post by:
Hello, C question here (running on Linux, though there should be no platform specific code). After reading through a few examples, and following one in a book, for linked lists i thought i would try my own small program. The problem is, I seem to be having trouble with memory, i.e. sometimes my program will work and display the correct output, and sometimes it will not and display garbage (in a printf call) so i assume i have been using...
0
8604
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, well explore What is ONU, What Is Router, ONU & Routers main usage, and What is the difference between ONU and Router. Lets take a closer look ! Part I. Meaning of...
0
8538
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8961
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8800
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8801
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
6459
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupr who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5819
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4324
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
2238
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.