sexta-feira, 29 de julho de 2011

Playing with Linked Lists

It seems silly post some code that lies in a such basic concept, but, lately I was asking myself about my basic coding skills, and decided to practice to see how I'm doing.

Since my first semester in College, I had never implemented again a Linked List manually, actually, I had never implemented it in C, only in Pascal. During the coding process, I became impressed on how much I had to struggle to simply add new elements in order to the list.

Here is the code (very ugly, btw):


#include
#include

typedef struct nodeT {
int value;
struct nodeT *next;
} node;

//insert always at the head
void insertBeginning(int number, node **head) {
node *newNode = (node *) malloc(sizeof(node));
newNode->value = number;
newNode->next = *head;
*head = newNode;
}

//insert in order
void insertInOrderRecursive(int number, node **head) {
//walk through the tail
if (!(*head)->next) {
node *newNode = (node *) malloc(sizeof(node));
newNode->value = number;
if ((*head)->value > number) {
newNode->next = *head;
*head = newNode;
} else {
newNode->next = NULL;
(*head)->next = newNode;
}
//found the right place
} else if ((*head)->value >= number) {
node *newNode = (node *) malloc(sizeof(node));
newNode->value = number;
newNode->next = *head;
*head = newNode;
} else {
//walk to the next node
insertInOrderRecursive(number, &(*head)->next);
}
}

void walkThrough(node *head) {
if (!head->next) {
printf(" %d\n", head->value);
return;
}

printf("%d -> ", head->value);
walkThrough(head->next);
}

int main() {

//init the linked list
node *list = (node *) malloc(sizeof(node));
list->next = NULL;

printf("Enter a number:\n");
int number;
scanf("%d", &number);

list->value = number;

//insert numbers
while (1) {
printf("Enter a number: (-1 to stop)\n");
scanf("%d", &number);

insertInOrderRecursive(number, &list);
walkThrough(list);

if (number == -1) {
break;
}
}

return 0;
}

Nenhum comentário:

Postar um comentário