mercredi 7 janvier 2015

Review my Doubly linked list code in C [on hold]



/*
* Doubly Linked List
*
* Each node of the list contain two references (or links) – one to the previous node and other to the next node.
* The previous link of the first node and the next link of the last node points to NULL.
* In comparison to singly-linked list, doubly-linked list requires handling of more pointers
* but less information is required as one can use the previous links to observe the preceding element.
*/

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

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

void insert(Node *current, int data);
void delete(Node *current, int data);
void print(Node *current);
int find(Node *current, int data);

void insert(Node *current, int data) {

// current is pointing to first element
// we iterate until we find the end
while(current->next != NULL) {
current = current->next;
}
// create a new Node and insert the item
current->next = (Node *)malloc(sizeof(Node));
(current->next)->prev = current;
current = current->next;
current->data = data;
current->next = NULL;
}

void delete(Node *current, int data){

// Iterate until we find a pointer next to the one we need to delete
while (current->next != NULL && (current->next)->data != data) {
current = current->next;
}

// Item is not found
if(current->next == NULL) {
printf("\nElement %d is not present in the list\n", data);
return;
}

// The element is found in the node next to the one that current points to
// We removed the node which is next to the pointer (which is also temp)
Node *tmp = current->next;
// In special case that we are deleting last node
if(tmp->next == NULL) {
current->next = NULL;
} else {
current->next = tmp->next;
(current->next)->prev = tmp->prev;
}
tmp->prev = current;

// We got rid of the node, now time to dellocate the memory
free(tmp);

return;
}
void print(Node *current) {
while(current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}

int find(Node *current, int data) {
// First pointer is head aka dummy node with no data
// so we go to next one
current = current->next;

// Iterate through the linked list
while(current != NULL) {
if(current->data == data) {
return 1;
}
current = current->next;
}
return 0;
}

int main() {

Node *head = (Node *)malloc(sizeof(Node));
head->next = NULL;
head->prev = NULL;

int data = 0;
int usr_input = 0;

while(1){
printf("0. Exit\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Print\n");
printf("4. Find\n");


scanf("%d", &usr_input);

// can also use a switch instead
if( usr_input == 0) {
exit(0);

} else if(usr_input == 1) {
printf("\nEnter an element you want to insert: ");
scanf("%d", &data);
insert(head, data);

} else if(usr_input == 2) {
printf("\nEnter an element you want to delete: ");
scanf("%d", &data);
delete(head, data);

} else if(usr_input == 3) {
printf("The list is ");
print(head->next);
printf("\n\n");

} else if(usr_input == 4) {
printf("\nEnter an element you want to find: ");
scanf("%d", &data);
int is_found = find(head, data);
if (is_found) {
printf("\nElement is found\n\n");
} else {
printf("\nElement is NOT found\n\n");
}
}
}
return 0;
}


Let me know if it seems right to you and if anything can be optimized.





Aucun commentaire:

Enregistrer un commentaire