implementation of link list in C without the input size

Question

First, I define a structure to implement linked list:

typedef struct node
{
    int data;
    struct node *next;
} Node;

Then, I have to insert an element into the linked list. And I cannot finish this part.

A example from my lecture notes tells me, when we insert an element, we should do something like that:

Node a, c; // originally
Node b; // insert-element
b->next = &c;
a->next = &b;

However, I have to declare a Node to implement it. But, here is my situation: I don't know the input size, maybe I have to insert 60 elements, or maybe I just have to insert 2 elements. What is the solution?

And another small, stupid problem, is there it any different between a->next and a.next?

You should read about pointers and about dynamic memory allocation (`malloc` and friends) first. `a->next` is the same as `(*a).next`. — Jabberwocky, Feb 11 '16 at 15:03
please comment on posts you downvote, to let the OP know how the question can be improved — sp2danny, Feb 11 '16 at 15:12
@sp2danny no, in many cases, that's not a good idea. In some cases, it's a very bad idea indeed. — Martin James, Feb 11 '16 at 15:47

ReshaD · Answer 1 · 2016-02-11T15:40:58.927

3

This is how you can implement an empty linked-list:

typedef struct node
{
  int data;
  struct node *next;
} Node;

int main(){

  Node *a, *b;

  a=malloc(sizeof(Node));
  //here check if allocation has been done, if not error
  a->data=1;
  a->next=NULL;


  b=malloc(sizeof(Node));
  b->data=2;
  b->next=a;

  //and so on




  return 0;
}

in this way your linked-list will be like: b ----> a -----> NULL Now let's suppose you want to add 3 to the end of the linked-list; you can use this function:

void insertToEnd(Node *head, int newNumber)
{
   Node *newNode, *tmp;
   newNode=malloc(sizeof(Node));
   newNode->data=newNumber;
   newNode->next=NULL;

   tmp=head;

   if(head->next == NULL){
     head->next = newNode;
   }

   else
   {
   while(tmp->next != NULL)
    {
        if(tmp->next == NULL)
        {
            tmp->next = newNode;
        }
        tmp = tmp->next;
    }
}


head=tmp;
}

I hope it works fine because i don't have c compiler right now. check it and let me know that if the function works fine

edited Feb 11 '16 at 15:40

answered Feb 11 '16 at 15:08

ReshaD

936
2
18
30

[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). – unwind Feb 11 '16 at 15:10
@unwind you mean b=malloc(sizeof(Node)); ? – ReshaD Feb 11 '16 at 15:13
You should probably click the link. :) But yes, or even better `b = malloc(sizeof *b);`. – unwind Feb 11 '16 at 15:14
@unwind thanks, Edited ;) – ReshaD Feb 11 '16 at 15:15
Then, if I want to insert an element at the end of the linked list. How can I implement it? beacuse I cannot do something like "node *c". – zodiac Feb 11 '16 at 15:16
@zodiac now I will add to the post that function too. – ReshaD Feb 11 '16 at 15:18

score 2 · Answer 2 · answered Feb 11 '16 at 15:13

The sensible thing is to create a function that prepends a new list node to an existing list. We use NULL to mean "the empty list". We prepend since that saves having to step through the entire list every time.

Node * list_prepend(Node *head, int data)
{
  Node *n = malloc(sizeof *n);
  if(n != NULL)
  {
    n->next = head;
    n->data = data;
    return n;  /* The new head. */
  }
  return head;
}

Then use it like so:

int main(void)
{
  Node *list;

  list = list_prepend(NULL, 47);
  list = list_prepend(list, 11);
}

score 1 · Answer 3 · answered Feb 11 '16 at 15:03

If you don't know how many Nodes you'll get, you'll have to allocate memory at runtime. malloc() and free() will do the job.

The difference between a->next and a.next is, well actually, a. In the first construction the "a" is a pointer to a struct, in the second case "a" is a struct itself.

implementation of link list in C without the input size

3 Answers3