i trying write linked list basic operations (push, pop, add_at_end, pop_from_end, add_at_index, pop_from_index). not school assignment, though may one. have written code. have tested myself quite bit, although no c guru. if tell me if there suggestions / corrections have code in terms of efficiency, memory handling, readability, clarity etc.
the resulting code has been added here: http://vladotrocol.ro/wiki/linked-lists
#include <stdio.h> #include <stdlib.h> //node structure typedef struct node { int data; struct node * next; } node_t; void print_list(node_t *head); //print list data iteratively int push(node_t **head, int data); //add node @ head of list int pop(node_t **head); //remove node head of list int add_at_end(node_t **head, int data); //add node @ end of list int remove_last(node_t **head); //remove node end of list int add_at_index(node_t **head, int n, int data); //add node @ nth position int remove_by_index(node_t **head, int n); //remove node @ nth position int main() { node_t *head = null; //create new list //initialise list 1 element head = malloc(sizeof(node_t)); //check if memory allocation possible if (head == null) { return -1; } head->data = 1; head->next = null; //print list print_list(head); return 0; } //print list data iteratively void print_list(node_t *head) { node_t *current = head; while (current != null) { printf("%d\n", current->data); current = current->next; } } //add node @ head of list int push(node_t **head, int data) { //create new node diven data node_t *new_node = null; new_node = malloc(sizeof(node_t)); //check if memory allocation possible if (new_node == null) { return -1; } new_node->data = data; new_node->next = *head; //the new node link points old head of list *head = new_node; //the new node becomes new head of list return 1; } //remove node head of list int pop(node_t **head) { int retval = -1; //if list empty nothing if (*head == null) { return -1; } //if there 1 node in list make list empty if ((*head)->next == null) { printf("here"); retval = (*head)->data; free(*head); *head = null; return retval; } //if list has multiple nodes node_t *next_node = null; next_node = (*head)->next; //get second node retval = (*head)->data; free(*head); *head = next_node; //the second node becomes head of list return retval; } //add node @ end of list int add_at_end(node_t ** head, int data) { node_t *new_node = null; new_node = malloc(sizeof(node_t)); //check if memory allocation possible if (new_node == null) { return -1; } //create new node new_node->data = data; new_node->next=null; //if list empty new node becomes head of list if(*head==null){ *head = new_node; return 1; } //otherwise iterate end of list node_t *current = *head; while (current->next != null) { current = current->next; } //the last node instead of pointing null points new node current->next = new_node; return 1; } //remove node end of list int remove_last(node_t **head) { int retval = -1; //if list empty nothing if (*head == null) { return -1; } //if list has 1 node list beomes empty if ((*head)->next == null) { (*head)->data; free(*head); *head = null; return retval; } //if list has multiple nodes go second last 1 node_t *current = *head; while (current->next->next != null) { current = current->next; } retval = current->next->data; //remove last node free(current->next); current->next = null; return retval; } //add node @ nth position int add_at_index(node_t **head, int n, int data) { /*if list empty or position inserted @ first 1 add new node @ head of list*/ if(n == 0 || *head==null){ push(head, data); return 1; } //if list not empty iterate n-2 times reach (n-1)th node node_t *current = *head; while(n>1 && current->next!=null){ current = current->next; n--; } /*if didn't perform iterations means required position bigger length of list*/ if(n>1){ return -1; } //if reached desired node create new 1 node_t *new_node = null; new_node = malloc(sizeof(node_t)); //check if memory allocation possible if (new_node == null) { return -1; } new_node->data = data; //the new node points node current node pointing new_node->next = current->next; //the current node points our newly create node current->next = new_node; return 1; } //remove node @ nth position int remove_by_index(node_t **head, int n) { /*if list empty or required position first 1 use pop function removes head node or nothing if list emty*/ if(n == 0||*head==null){ pop(head); return 1; } //if list has multiple elements got nth node node_t *current = *head; node_t *curr_head = null; while(n>0 && current->next!=null){ curr_head = current; //this time need remember previous node current = current->next; n--; } /*if iterations have not completed means list emty , there nothing do*/ if(n>0){ return -1; } /*instead of pointing current node, previous node pointing next node*/ curr_head->next = current->next; free(current); //delete current node return 1; }
i didn't thoroughly review of code, had superficial , think there couple of points worth mentioning. note may subjective sometimes, not agrees on using same conventions. here's small list of think improved:
1.
in pointer declarations, seem follow convention of placing space between star(s) , identifier. wouldn't recommend this. why? because pointer declarator not part of primitive type (it's declarator). if put space between star , identifier, will write code someday:
int * x, y; and mistakenly assume x , y pointers int, whereas reality x pointer, y int. favor , write instead:
int *x, y; (either way, not bad people write int* x,y - asking trouble).
2.
do not hardcode type name when determining amount of memory allocate. instead of this:
head = malloc(sizeof(node_t)); use more flexible form:
head = malloc(sizeof(*head)); sizeof doesn't evaluate operand, safe this. if this, you're safe because allocate correct amount of memory. furthermore, makes code easier maintain, because if type of head changes, code still work , still allocate right amount of memory.
3.
add_at_end() , other functions allocate memory not checking whether malloc() successful.
Comments
Post a Comment