Converting array to linear linked list

ejknippa · #1 17-Aug-2005, 00:45

I'm fairly new to programming. I have an assignment to create a structure, then convert it using a seperate function to a linear linked list. I have the structure created, and can fill it with data, but I have no idea how to even start converting it to a linked list. The textbook only has a few pages covering linked lists, and nowhere does it talk about array/structures to lists. I've included what I have so far. Any nudge in the right direction to help me get started would be greatly appreciated.

in list.h

CPP / C++ / C Code:

#include <stdio.h>

struct data {
	char name[10];
	int age;
	int weight;
};

typedef	struct data	DATA;

struct linked_list {
	DATA			d;
	struct linked_list	*next;
};

typedef	struct linked_list	ELEMENT;
typedef ELEMENT *			LINK;

in create_structure.cpp

CPP / C++ / C Code:

#include "list.h"

struct data	list[20];

int main(void)
{
	int num, i;
	printf("Enter number of entries:");
	scanf("%d", &num);
	
	for (i = 0; i < num; ++i){
		printf("\nEnter the data as: Name(string) Age(int) Weight(int)");
		scanf("%s %d %d", list[i].name, &list[i].age, &list[i].weight);
	}
	printf("\n\n");
	for (i = 0; i < num; ++i){
		printf("%s %d %d\n", list[i].name, list[i].age, list[i].weight);
	}
	return 0;
}

maprich · #2 17-Aug-2005, 03:10

You have the right notion in your code that linked list nodes have a pointer to the following node. If it was doubly linked list you would have also a pointer to the previous node.

Good explanation about doubly linked lists here:
Doubly-linked List
especially the part "Doubly Linked List Explained" is good for you.

Doesn't matter if it is about doubly linked list since if you understand it you can without difficulty downgrade it to singly linked list.

L7Sqr · #3 17-Aug-2005, 10:19

Why use the typedef statements if you dont utilize the results?
i.e.

CPP / C++ / C Code:

typedef  struct data  DATA;

/* and later ... */
struct data  list[20];

To create the linked list, simply create

CPP / C++ / C Code:

struct data * linked_list = NULL;
struct data * node = linked_list;

malloc memory for that item (node) and assign data to it from list[0].
assign node to node->next.
malloc memory...assign from list[1]
etc...
The above would be best accomplished in a for loop with the index into list being i.
To print the list,
node = linked_list;

CPP / C++ / C Code:

while (node) {
   printf ( ...whatever you want...);
   node = node->next;
}

ejknippa · #4 20-Aug-2005, 17:43

Here's what I have so far....

in list.h

CPP / C++ / C Code:

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

struct data {
	char name[10];
	int age;
	int weight;
};

typedef	struct data	DATA;

struct linked_list {
	DATA	d;
	struct linked_list	*next;
};

typedef	struct linked_list	ELEMENT;
typedef ELEMENT * LINK;

in create_structure.cpp

CPP / C++ / C Code:

#include "list.h"

DATA list[20];

int main(void)
{
	int num, i;
	LINK head;
	printf("Enter number of entries:");
	scanf("%d", &num);
	
	for (i = 0; i < num; ++i){
		printf("\nEnter the data as: Name(string) Age(int) Weight(int)");
		scanf("%s %d %d", list[i].name, &list[i].age, &list[i].weight);
	}
	printf("\n\n");
	for (i = 0; i < num; ++i){
		printf("%s %d %d\n", list[i].name, list[i].age, list[i].weight);
		head = malloc(sizeof(ELEMENT));
		head -> d = list[i];
		head -> next = NULL;
	}
	return 0;
}

I think it looks OK by the book, but I get: error C2440: '=' : cannot convert from 'void *' to 'LINK'. If i remove the stdlib.h from the header, it says it can't locate malloc. Now I'm just getting frustrated. Can anyone point out what I'm doing wrong?

Evil Requiem · #5 20-Aug-2005, 18:46

First, get rid of that LINK typedef. When reading your code, I was wondering why you tried to allocate memory for a non-pointer but then realised that it was actually typedef'ed. This is a very very very bad idea. It makes your code hard to read. Second, the answer to your problem is that you need to cast the result of malloc( ). Here is your code, with some minor corrections:

CPP / C++ / C Code:

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

typdef struct {
	char name[10];
	int age;
	int weight;
} data;

typedef struct {
	data	d;
	NODE* next;
} NODE;

in create_structure.cpp

CPP / C++ / C Code:

#include "list.h"

DATA list[20];

int main(void)
{
	int num, i;
	NODE* head;
	printf("Enter number of entries:");
	scanf("%d", &num);
	
	for (i = 0; i < num; ++i){
		printf("\nEnter the data as: Name(string) Age(int) Weight(int)");
		scanf("%s %d %d", list[i].name, &list[i].age, &list[i].weight);
	}
	printf("\n\n");
	for (i = 0; i < num; ++i){
		printf("%s %d %d\n", list[i].name, list[i].age, list[i].weight);
		head = (NODE*) malloc(sizeof(ELEMENT));
		head -> d = list[i];
		head -> next = NULL;
	}
	return 0;
}

ejknippa · #6 23-Aug-2005, 01:03

Thanks, your wisdom has helped immensely.

maprich · #7 23-Aug-2005, 03:03

Quote:

Originally Posted by Evil Requiem

CPP / C++ / C Code:

#include "list.h"

DATA list[20];

int main(void)
{
  int num, i;
  NODE* head;
  printf("Enter number of entries:");
  scanf("%d", &num);
  
  for (i = 0; i < num; ++i){
    printf("\nEnter the data as: Name(string) Age(int) Weight(int)");
    scanf("%s %d %d", list[i].name, &list[i].age, &list[i].weight);
  }
//...

In the above Evil Requiem binds the data array to 20 ... The whole point of linked list is to become free of the fixedness of arrays and to determine the length at runtime. The above solution is NOT linked list solution.

Quote:

Originally Posted by Evil Requiem

CPP / C++ / C Code:

//...
  for (i = 0; i < num; ++i){
    printf("%s %d %d\n", list[i].name, list[i].age, list[i].weight);
    head = (NODE*) malloc(sizeof(ELEMENT));
    head -> d = list[i];
    head -> next = NULL;
  }
  return 0;
}

In the above there are problems.

ELEMENT is not defined in Evil Requiems version of code.. in the original yes.. it should be NODE there instead so maybe this was just a typo.
the head gets num times malloc:ed ... there is a memory hazard here. 1. time head can be assumed to be NULL and after malloc points to some node. Ok ... but the 2. time malloc just reserves new node and TURNS the head to point to the new memory location... so what happened to the first node? It is still there somewhere reserving memory but without any pointer to point at it. It has become zombie.
The above only appears to print the correct information, but that is done by iterating the fixed array and has nothing to do with linked list.

so here is my corrected version:

list.h:

CPP / C++ / C Code:

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

typedef struct {
  char name[10];
  int age;
  int weight;
} data;

typedef struct {
  data  d;
  NODE* next;
} NODE;

no changes in above as it was already good

create_structure.c:

CPP / C++ / C Code:

#include "list.h"

int main(void)
{
  NODE* head = NULL;  // this should always point to the 1. node
  NODE* pin = NULL;    // used to iterate through nodes.
  
  int num, i;
  printf("Enter number of entries:");
  scanf("%d", &num);

  for( i=0; i<num; ++i )
  {
      if( head == NULL )
      {
          head = (NODE*) malloc(sizeof(NODE));
          head->next = NULL;
          pin = head;
      }
      else {
          pin->next = (NODE*) malloc(sizeof(NODE));
          pin = pin->next;
          pin->next = NULL;
      }
      
      printf("\nEnter the data as: Name(string) Age(int) Weight(int)");
      scanf("%s %d %d", pin->d.name, &(pin->d.age), &(pin->d.weight) );
  }
  
  //Printing the data. Goes through the linked list node by node.
  printf("\n\n");
  pin = head;
  while( pin != NULL )
  {
      printf("%s %d %d\n", pin->d.name, pin->d.age, pin->d.weight);
      pin = pin->next;
  }
  
  // cleanup . !! important !!
  // too often people forget to free the dynamically allocated memory
  while( head != NULL )
  {
      pin = head->next;
      free( head );
      head = pin;
  }
  
  return 0;
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 14:13
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 01:34
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 21:26