Convert array to singly linked list

Question

I have more experience with linked lists after gaining practice and support from SO, given my last few questions. Essentially, I am now following an algorithm that will convert an array to a singly linked list.

Algorithm: CONVERT (A, N, HEAD)
1. Set HEAD = NULL
2. Repeat steps 3 to 8 while N ≠ -1
3. Allocated memory for NEW node
4. IF NEW = NULL then Print: “Memory not Available” and Return
5. Set NEW→DATA = A[N-1]
6. Set NEW→LINK = HEAD
7. Set HEAD = NEW
8. Set N = N - 1
[End of loop]
9. Return

I have attempted creating the code for this, however, after printing out the node carrying the data, I get a bunch of zeros. I know that with an array, if I assign a large size to the array and do not fill all values in, then these are assigned 0. However, this is not the case for my example.

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

typedef struct node {
    int DATA;
    struct node* LINK;
} node;

void convert(int A[], int N, node* head){
    head = NULL;
    while(N != -1){
        node* new;
        new = (node*)malloc(sizeof(node));
        if (new == NULL){
            printf("Memory not available");
            return;
        }
        printf("%i", new->DATA);
        new->DATA = A[N-1];
        new->LINK = head;
        head = new;
        N--;
    }
    return;
}

int main(){
    int arr[10] = {0, 1, 2, 3, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    node* former;
    former = (node*)malloc(sizeof(node));
    convert(arr, size, former);
    return 0;
}

Would print out the following:

00000000000%

How do I convert the array values to the singly linked list, what might I be missing?

printf("%i", new->DATA); should be after new->DATA = A[N-1];, you are printing uninitialized values currently. — mch
– mch, Commented Dec 30, 2022 at 12:42
well, you totally lose that head pointer with head = NULL; — theemee
– theemee, Commented Dec 30, 2022 at 12:43
@theemee Ah I see, I have updated my script to free the memory. No, I am not inverting it, however, it seems to invert the array. Why might it be doing this? — Emil11
– Emil11, Commented Dec 30, 2022 at 12:59
You should return head from convert and replace former = malloc(...) with former = convert(...) — William Pursell
– William Pursell, Commented Dec 30, 2022 at 13:06

theemee · Accepted Answer · 2022-12-30 13:56:52Z

2

There are a few problems with your code:

You don't receive the created list head pointer back to main.
You print the data before you assign it and the printing will be inverted if you do during the creation of the list.
You don't free the allocated memory and create memory leaks.

Here is how to fix it:

Return the created list head pointer from the convert function.
Write a separate function for printing the list.
Write a function for freeing the memory of the list.

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

typedef struct node
{
    int DATA;
    struct node *LINK;
} node;

node *convert(int A[], int N);
void printList(node *head);
void freeList(node *head);

node *convert(int A[], int N)
{
    node *head = NULL;
    for (int i = N - 1; i >= 0; i--)
    {
        node *new = malloc(sizeof(node));
        if (new == NULL)
        {
            printf("Memory not available");
            freeList(head); // free already allocated memory
            return NULL;
        }
        new->DATA = A[i];
        new->LINK = head;
        head = new;
    }
    return head; // return the head pointer
}

void printList(node *head)
{
    node *current = head;
    while (current != NULL)
    {
        printf("%d ", current->DATA);
        current = current->LINK;
    }
}

void freeList(node *head)
{
    node *current = head;
    node *next = NULL;
    while (current != NULL)
    {
        next = current->LINK;
        free(current);
        current = next;
    }
}

int main()
{
    int arr[5] = {0, 1, 2, 3, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    node *former = convert(arr, size);
    printList(former);
    freeList(former);
    return 0;
}

edited Dec 30, 2022 at 13:56

answered Dec 30, 2022 at 13:07

theemee

8344 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

chux Over a year ago

Cast not needed in (node *)malloc(sizeof(node)).

theemee Over a year ago

@chux-ReinstateMonica some compilers and compiler options won't compile without it. It doesn't hurt

chux Over a year ago

All compliant C compilers compile node *new = malloc(sizeof(node));. Please post a sample one that does not.

theemee Over a year ago

@chux-ReinstateMonica i mixed it up with c++ behaviour

Sachith Wickramaarachchi · Accepted Answer · 2022-12-30 13:08:50Z

1

Seems you are trying to print new->DATA value before you assign it's value. print it after assigning the value.

And head pointer is a local variable, so it's changes will not be reflected in Main() function. Change head pointer as follows inside Convert() function.

*head = NULL;

And your Main() function should be updated as follows,

int main(){
    int arr[10] = {0, 1, 2, 3, 4};
    int size = sizeof(arr)/sizeof(arr[0]);
    node* head;
    convert(arr, size, &head);
    return 0;
}

updated:

Change your Convert() function as follows,

void convert(int A[], int N, node ** head) {
  * head = NULL;
  while (N != -1) {
    node * new;
    new = malloc(sizeof new[0]);
    if (new == NULL) {
      printf("Memory not available");
      return;
    }
    new -> DATA = A[N - 1];
    printf("%i", new -> DATA);
    new -> LINK = * head;
    * head = new;
    N--;
  }
  return;
}

edited Dec 30, 2022 at 13:08

answered Dec 30, 2022 at 12:42

Sachith Wickramaarachchi

5,9167 gold badges45 silver badges78 bronze badges

6 Comments

Emil11 Over a year ago

Not sure whether the &head is needed in this instance. My compiler would throw an error, otherwise. I think for this to work, I need a double pointer for the parameter.

Sachith Wickramaarachchi Over a year ago

@Emil11 Have you updated the head as follows inside the Convert function *head = NULL;

chux Over a year ago

Sachith, new = malloc(sizeof new[0]); is simpler and more direct than new = (node * ) malloc(sizeof(node));

Sachith Wickramaarachchi Over a year ago

@chux-ReinstateMonica Thank you very much, I'll update it

chux Over a year ago

Notice that new -> DATA = A[0 - 1]; is attempted.

|

0___________ · Accepted Answer · 2022-12-30 13:09:36Z

0

Split the problem into smaller bits. Use functions to program them.

typedef struct node {
    int DATA;
    struct node* LINK;
} node;

node *add(node *last, int data)
{
    node *wrk = malloc(sizeof(*wrk));
    if(wrk)
    {
        wrk -> DATA = data;
        wrk -> LINK = NULL;
    }
    if(last) last -> LINK = wrk;
    else last = wrk;
    return wrk;
}

node *convert(int *data, size_t size)
{
    node *head = NULL, *last;
    
    if(data && size) 
    {
        if((head = add(NULL, *data++)))
        {
            last = head;
            while(--size)
            {
                if(!(last = add(last, *data++))) break;
            }
        }
    }
    return head;
}

void printList(const node *head)
{
    while(head)
    {
        printf("%d\n", head -> DATA);
        head = head -> LINK;
    }
}

int main(void)
{
    int arr[] = {9, 1, 2, 3, 4};
    size_t size = sizeof(arr)/sizeof(arr[0]);

    node *head = convert(arr, size);

    printList(head);
    return 0;
}

answered Dec 30, 2022 at 13:09

0___________

71.6k4 gold badges41 silver badges94 bronze badges

1 Comment

Emil11 Over a year ago

Creative! will have to study your interpretation

Collectives™ on Stack Overflow

Convert array to singly linked list

3 Answers 3

4 Comments

6 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related