473,898 Members | 2,888 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Linked List

13 New Member
I'm messing around with linked lists and so far I was able to do a little something. However, I want to improve this code so I would like for any help.

First, I want improve the function insertFirst() so that it tests if memory allocation worked.

Second, I want improve main() so that it tests if insertFirst() returns NULL. If it does, main() should write out an error message and terminate any loop.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stddef.h>
  3. #include <stdlib.h>
  4. struct NODE
  5. {
  6. struct NODE *link;
  7. int value;
  8. };
  9. typedef struct NODE Node;
  10. Node *insertFirst( Node **head, int val )
  11. {
  12. Node *node = (Node *)malloc( sizeof( Node ) );
  13. node->value = val;
  14. node->link = *head;
  15. *head = node;
  16. return node;
  17. }
  18. void traverse( Node *p )
  19. {
  20. while ( p != NULL )
  21. {
  22. printf("%d ", p->value );
  23. p = p->link;
  24. }
  25. }
  26. void freeList( Node *p )
  27. {
  28. Node *temp;
  29. while ( p != NULL )
  30. {
  31. temp = p;
  32. p = p->link;
  33. free( temp );
  34. }
  35. }
  36. int main()
  37. {
  38. Node *head = NULL;
  39. int j;
  40. for ( j=0; j<13; j++ )
  41. insertFirst( &head, j );
  42. traverse( head );
  43. freeList( head );
  44. return 1;
  45. }
Nov 3 '06 #1
8 4198
sicarie
4,677 Recognized Expert Moderator Specialist
I'm messing around with linked lists and so far I was able to do a little something. However, I want to improve this code so I would like for any help.

First, I want improve the function insertFirst() so that it tests if memory allocation worked.

Second, I want improve main() so that it tests if insertFirst() returns NULL. If it does, main() should write out an error message and terminate any loop.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stddef.h>
  3. #include <stdlib.h>
  4. struct NODE
  5. {
  6. struct NODE *link;
  7. int value;
  8. };
  9. typedef struct NODE Node;
  10. Node *insertFirst( Node **head, int val )
  11. {
  12. Node *node = (Node *)malloc( sizeof( Node ) );
  13. node->value = val;
  14. node->link = *head;
  15. *head = node;
  16. return node;
  17. }
  18. void traverse( Node *p )
  19. {
  20. while ( p != NULL )
  21. {
  22. printf("%d ", p->value );
  23. p = p->link;
  24. }
  25. }
  26. void freeList( Node *p )
  27. {
  28. Node *temp;
  29. while ( p != NULL )
  30. {
  31. temp = p;
  32. p = p->link;
  33. free( temp );
  34. }
  35. }
  36. int main()
  37. {
  38. Node *head = NULL;
  39. int j;
  40. for ( j=0; j<13; j++ )
  41. insertFirst( &head, j );
  42. traverse( head );
  43. freeList( head );
  44. return 1;
  45. }
DeFault-

Are you set in C, and not C++? You could do those things very easily in C++, but if you need C, you can always just put the insertFirst() inside the condition of an 'if' statement, and a break in the body:

Expand|Select|Wrap|Line Numbers
  1. if ( (insertFirst(&head, j) ) {
  2.    break;
  3. }
  4.  
Though the infamous story of the crashing PBX that caused an almost nationwide phone outage comes to mind - and you might (if you don't want to do anything else) consider 'return 0;' instead of 'break;'

As for 'malloc' this link http://www.opengroup.o rg/onlinepubs/009695399/functions/malloc.html says that errno is set if malloc fails (or you get a null pointer, which is easy to check for). So you would need to include <errno.h> but then it's as easy as

Expand|Select|Wrap|Line Numbers
  1. if ( (*node == NULL) || (errno != 0) ) {
  2.    printf("Malloc failed!\n");
  3. }
  4.  
PS - you can look more in to that here: http://publib.boulder. ibm.com/infocenter/iadthelp/v6r0/index.jsp?topic =/com.ibm.etools. iseries.pgmgd.d oc/cpprog416.htm
They suggest setting errno immediately before any tests and then resetting it immediately after you check.
Nov 4 '06 #2
DeFault
13 New Member
-Sicarie

Thanks I'll give that a try.

I was also thinking about adding a function called insertLast() I haven't tried yet it but what do you think of this.

Expand|Select|Wrap|Line Numbers
  1. Node* insertLast ( Node **head, int val)
  2. {
  3.  
  4. Node *last;
  5. Node *temp;
  6.  
  7. if (*head != NULL)
  8.  
  9.    last = (Node *)malloc( sizeof( Node ));
  10.    last->value = val;
  11.  
  12.    last->link=temp; 
  13.    last=temp;
  14.  
  15. }
You think that will get the job then.
Nov 4 '06 #3
sicarie
4,677 Recognized Expert Moderator Specialist
DeFault-

If you're eventually going for the full functionality I would recommend creating a head and tail node that carry sentinel values to identify them, so that doing such insertions are easier.

As for inserting to the tail, it seems that you pass it a node and a value, however the 'last' node is only set to temp, not joined to any nodes in the list (such as the 'head' or any nodes after it). But it's possible that I have been staring at my screen for too long today and I'm just not seeing it - I've been known to do that ;)

If you were to add a 'previous' pointer to the nodes as well, then you could set the tail nodes pretty easily, and create iterators to go through the list backwards as well, it's all a matter of how you want to implement it (how big you want them to be, how much you want to do with them, etc...).
Nov 5 '06 #4
DeFault
13 New Member
Is this any better?

Expand|Select|Wrap|Line Numbers
  1. Node* insertLast ( Node **head, int val)
  2. {
  3.  
  4. Node *current;
  5. Node *previous;
  6. Node *last;
  7.  
  8.  
  9. current = (Node *)malloc(sizeof(Node));
  10.  
  11. if (current != NULL)
  12.  
  13.    previous = current;
  14.    current = current->link;
  15.  
  16.    last = (Node *)malloc( sizeof( Node ));
  17.    last->value = val;
  18.  
  19.    last->link=current; 
  20.    previous->link = last;
  21.  
  22. }
Nov 6 '06 #5
sicarie
4,677 Recognized Expert Moderator Specialist
Better? I think you covered 'better' when you decided to program your own linked list set to better understand the workings of the language.

The only thing I can see (with a quick glance - I will take a better look at it later, so ignore me if I'm wrong), is that you pass this **head, but then don't do anything with it. What is being passed to insertLast()? Are you passing it the current 'last' node, and the value you want it to hold? I think the only thing you're missing is something tying it to the rest of the list, something along the lines of:

Expand|Select|Wrap|Line Numbers
  1. head->next = current;
  2. current->previous = head;
  3. current->next = 
  4. /* and here is where you need to decide what you are going to do, 
  5. *  if it is going to be a sentinal 'end' node, or if you're going to tie it
  6. *  back around to the first node, etc...
  7. */
  8.  
Does that make sense, or am I on something and just missed where you did that?
Nov 6 '06 #6
DeFault
13 New Member
Better? I think you covered 'better' when you decided to program your own linked list set to better understand the workings of the language.

The only thing I can see (with a quick glance - I will take a better look at it later, so ignore me if I'm wrong), is that you pass this **head, but then don't do anything with it. What is being passed to insertLast()? Are you passing it the current 'last' node, and the value you want it to hold? I think the only thing you're missing is something tying it to the rest of the list, something along the lines of:

Expand|Select|Wrap|Line Numbers
  1. head->next = current;
  2. current->previous = head;
  3. current->next = 
  4. /* and here is where you need to decide what you are going to do, 
  5. *  if it is going to be a sentinal 'end' node, or if you're going to tie it
  6. *  back around to the first node, etc...
  7. */
  8.  
Does that make sense, or am I on something and just missed where you did that?
To answer your question about what is being passed to insertLast() that is basically inserting a node containing val at the end of a linked list.

For the code you wrote I would have a sentinal 'end' node so could you so me how it would be then by your code.
Nov 8 '06 #7
sicarie
4,677 Recognized Expert Moderator Specialist
To answer your question about what is being passed to insertLast() that is basically inserting a node containing val at the end of a linked list.

For the code you wrote I would have a sentinal 'end' node so could you so me how it would be then by your code.
Hang on, I'm gonna run it and look into it - I was just spot reading that, I could be totally missing something. It's just weird to me that you are passing a node and a value - not just one or the other (a node to just insert, or a value from which insertLast will create a node to add onto the list), but I probably am missing something, I'm not feeling too well today.
Nov 8 '06 #8
DeFault
13 New Member
This is a silly question but when I ask how to improve insertFirst() and the code you wrote I would have to put that in insertFirst() right? The same goes to the malloc part I would have to put that in main right?
Nov 10 '06 #9

Sign in to post your reply or Sign up for a free account.

Similar topics

11
3106
by: C++fan | last post by:
Suppose that I define the following class: class example_class{ public: example_class(); void funtion_1(); void function_2(); protected:
5
859
by: Dream Catcher | last post by:
1. I don't know once the node is located, how to return that node. Should I return pointer to that node or should I return the struct of that node. 2. Also how to do the fn call in main for that LOCATE subroutine that returns a node???? Any help would be appreciated. Thanks
10
15144
by: Kent | last post by:
Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy *enemydata; // Holds information about an enemy (in a game) // Its a double linked list node
6
4605
by: Steve Lambert | last post by:
Hi, I've knocked up a number of small routines to create and manipulate a linked list of any structure. If anyone could take a look at this code and give me their opinion and details of any potential pitfalls I'd be extremely grateful. Cheers Steve
12
15113
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 {
12
3968
by: joshd | last post by:
Hello, Im sorry if this question has been asked before, but I did search before posting and couldnt find an answer to my problem. I have two classes each with corresponding linked lists, list1 and list2, each node within list1 has various data and needs to have a pointer to the corresponding node in list2, but I cant figure out how to do this. Could someone explain what I might be missing, or maybe point me in the direction of a good...
51
8683
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort for linked lists, I couldn't find one. I read something about Mcilroy's "Optimistic Merge Sort" and studied some implementation, but they were for arrays. Does anybody know if Mcilroys optimization is applicable to truly linked lists at all?
1
15595
by: theeverdead | last post by:
Ok I have a file in it is a record of a persons first and last name. Format is like: Trevor Johnson Kevin Smith Allan Harris I need to read that file into program and then turn it into a linked list. So on the list I can go Trevor, Kevin, Allan in a straight row but I can also call out there last name when I am on their first name in the list. Sorry if it doesn't make sense trying to explain best I can. So far I have // list.cpp
0
8644
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered. The single-linked list travels only one...
7
5784
by: QiongZ | last post by:
Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it compiled no problem. But I can't find the what the problem is with templates? Please help. The main is in test-linked-list.cpp. There are two template classes. One is List1, the other one is ListNode. The codes are below: // test-linked-list.cpp :...
0
9993
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, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9839
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
11254
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10480
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...
0
9658
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
8034
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
5876
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...
0
6076
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4295
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.