c - Singly linked list - deleting/adding item at position x -
this singly-linked list. have following code. want extend these code it's possible add/delete element @ specific position. don't know how go implementing it.
this have far:
#include <stdio.h> #include <conio.h> #include <stdlib.h> struct list { int amount; struct element *first; }; struct element { int number; struct element *next; int *temp; }; int main() { struct list lk; struct element *ptr, *temp; int amount; int i; printf("how elements u want enter?"); scanf("%d", &amount); ptr = (struct element *) calloc(1, sizeof(struct element)); lk.first = ptr; lk.amount = 0; printf("please enter 1. number :"); scanf("%d", &(ptr->number)); temp = ptr; (i = 2; <= amount; i++) { printf("please enter %d. number", i); ptr = (struct element *) calloc(1, sizeof(struct element)); lk.amount++; scanf("%d", &(ptr->number)); ptr->next = null; temp->next = ptr; temp = ptr; } ptr = lk.first; while (ptr != null) { printf("%d \n", ptr->number); ptr = ptr->next; } getch(); return 0; } i found following method, dont know how adjust program:
void insertinlist (list* l, element* position, element* new) { if (position == 0) { new->next = l->first; l->first= new; l->amount++; } else { new->next = position->next; position->next = new; l->amount++; } } i tested after user input:
struct list lk; struct element *ptr, *temp, number1, number2; int amount; int i; printf("which element u want add:"); scanf("%d", number1.number); printf("on position u want add element?:"); scanf("%d", number2.number); initlist(&lk); insertinlist(&lk, &zahl2, &zahl1); i accessviolentexception, after line > scanf("%d", number1.number);
let's start 2 special cases singly-linked non-circular list. first, generic way add data, continue add nodes end of list. function there may like:
/* insert node @ end of list */ void insert_end (list *l, int n) { struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; if (l->cnt == 0) { l->first = ptr; l->cnt++; return; } lnode *iter = l->first; /* pointer iterate list */ while (iter->next) iter = iter->next; iter->next = ptr; l->cnt++; } above allocate storage next element (i have remained them nodes). check if amount (renamed cnt) 0. if so, add first node. if not, create pointer list use iterator , iterate on list pointers until node->next null , add new node @ end.
(note: if insertion efficiency key, double-linked circular list, no iteration required, add node @ end adding @ list->prev position, makes additions blindly fast in lists hundreds of millions of nodes)
the next variation wanting add new node @ beginning or start of list. here make ptr->next = l->first , l->first = ptr:
/* insert node @ beginning of list */ void insert_start (list *l, int n) { struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; if (l->cnt == 0) ptr->next = null; else ptr->next = l->first; l->first = ptr; l->cnt++; } what inserting node @ given position in list. need validate position (0 <= pos <= lk->cnt) (or set value greater lk->cnt equal lk->cnt). have seen how iterate through nodes end of list using list pointer iterate iter = lter->next until arriving @ last node. getting nth node no different. insert @ give position, given position, becomes matter of iterating pos number of times reach insertion point:
/* insert node @ position */ void insert_pos (list *l, int n, int pos) { /* validate position */ if (pos < 0 || pos > l->cnt) { fprintf (stderr, "%s() error: invalid position.\n", __func__); return; } /* if empty or pos 0, insert_start */ if (l->cnt == 0 || pos == 0) { insert_start (l, n); return; } struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; lnode *iter = l->first; /* pointer iterate list */ while (--pos) iter = iter->next; if (iter->next) ptr->next = iter->next; iter->next = ptr; l->cnt++; } the next variation adding node anywhere in list in numeric sort order. if new ptr->number = 6; , have 5 , 7, insert new ptr between holding 5 , 7. note: function below handles placing first node, , nodes less first node in list, placing nodes @ end of list. in finding given new node go. use input routine if goal insert nodes in sorted order or can use fill in special cases.
/* insert node @ end of list */ void insert_ordered (list *l, int n) { /* if first node of n < first->number */ if (l->cnt == 0 || n < l->first->number) { insert_start (l, n); return; } struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; lnode *iter = l->first; /* pointer iterate list */ while (iter->next && n > iter->next->number) { iter = iter->next; } if (iter->next) ptr->next = iter->next; iter->next = ptr; l->cnt++; } as long expanding list, should keep main function clean functions print list , free memory allocated list when done. couple of helper functions can accomplish be:
void prn_list (list l) { lnode *ptr = l.first; int = 0; while (ptr) { printf(" node[%2d] : %d\n", i++, ptr->number); ptr = ptr->next; } } void free_list (list l) { lnode *ptr = l.first; while (ptr) { lnode *del = ptr; ptr = ptr->next; free (del); del = null; } } deleting works in similar manner. putting list semi-robust input features. note struct have had typedefs created cut down on typing , improve readability.
#include <stdio.h> #include <stdlib.h> // #include <conio.h> typedef struct lnode { int number; struct lnode *next; } lnode; typedef struct { int cnt; lnode *first; } list; void insert_end (list *l, int n); void insert_start (list *l, int n); void insert_ordered (list *l, int n); void insert_pos (list *l, int n, int pos); void prn_list (list l); void free_list (list l); int main (void) { list lk = { 0, null }; int num = 0; int = 0; printf ("\n number of nodes enter: "); scanf ("%d", &num); (i = 0; < num; i++) { int n = 0; printf (" enter node[%d]->number: ", i); scanf("%d", &n); insert_end (&lk, n); } printf ("\n list contains '%d' nodes.\n", lk.cnt); printf ("\n list nodes are:\n\n"); prn_list (lk); printf ("\n enter number add @ start: "); scanf("%d", &num); insert_start (&lk, num); printf ("\n list contains '%d' nodes.\n", lk.cnt); printf ("\n list nodes are:\n\n"); prn_list (lk); printf ("\n enter number add in order: "); scanf("%d", &num); insert_ordered (&lk, num); printf ("\n list contains '%d' nodes.\n", lk.cnt); printf ("\n list nodes are:\n\n"); prn_list (lk); printf ("\n enter number add @ position: "); scanf("%d", &num); printf ("\n position must (0 <= pos <= %d)\n", lk.cnt); printf ("\n enter position in list '%d': ", num); scanf("%d", &i); insert_pos (&lk, num, i); printf ("\n list contains '%d' nodes.\n", lk.cnt); printf ("\n list nodes are:\n\n"); prn_list (lk); printf ("\n freeing list memory:\n\n"); free_list (lk); //getch(); return 0; } /* insert node @ end of list */ void insert_end (list *l, int n) { struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; if (l->cnt == 0) { l->first = ptr; l->cnt++; return; } lnode *iter = l->first; /* pointer iterate list */ while (iter->next) iter = iter->next; iter->next = ptr; l->cnt++; } /* insert node @ beginning of list */ void insert_start (list *l, int n) { struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; if (l->cnt == 0) ptr->next = null; else ptr->next = l->first; l->first = ptr; l->cnt++; } /* insert node @ end of list */ void insert_ordered (list *l, int n) { /* if first node of n < first->number */ if (l->cnt == 0 || n < l->first->number) { insert_start (l, n); return; } struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; lnode *iter = l->first; /* pointer iterate list */ while (iter->next && n > iter->next->number) iter = iter->next; if (iter->next) ptr->next = iter->next; iter->next = ptr; l->cnt++; } /* insert node @ position */ void insert_pos (list *l, int n, int pos) { /* validate position */ if (pos < 0 || pos > l->cnt) { fprintf (stderr, "%s() error: invalid position.\n", __func__); return; } /* if pos 0, insert_start */ if (l->cnt == 0 || pos == 0) { insert_start (l, n); return; } struct lnode *ptr = null; if (!(ptr = calloc (1, sizeof *ptr))) { fprintf (stderr, "%s() error: memory exhausted.\n", __func__); exit (exit_failure); } ptr->number = n; ptr->next = null; lnode *iter = l->first; /* pointer iterate list */ while (--pos) iter = iter->next; if (iter->next) ptr->next = iter->next; iter->next = ptr; l->cnt++; } /* print nodes in list */ void prn_list (list l) { lnode *ptr = l.first; int = 0; while (ptr) { printf(" node[%2d] : %d\n", i++, ptr->number); ptr = ptr->next; } } /* free memory nodes */ void free_list (list l) { lnode *ptr = l.first; while (ptr) { lnode *del = ptr; ptr = ptr->next; free (del); del = null; } } use/output
$ ./bin/ll_single_ins number of nodes enter: 3 enter node[0]->number: 5 enter node[1]->number: 7 enter node[2]->number: 9 list contains '3' nodes. list nodes are: node[ 0] : 5 node[ 1] : 7 node[ 2] : 9 enter number add @ start: 2 list contains '4' nodes. list nodes are: node[ 0] : 2 node[ 1] : 5 node[ 2] : 7 node[ 3] : 9 enter number add in order: 6 list contains '5' nodes. list nodes are: node[ 0] : 2 node[ 1] : 5 node[ 2] : 6 node[ 3] : 7 node[ 4] : 9 enter number add @ position: 4 position must (0 <= pos <= 5) enter position in list '4': 4 list contains '6' nodes. list nodes are: node[ 0] : 2 node[ 1] : 5 node[ 2] : 6 node[ 3] : 7 node[ 4] : 4 node[ 5] : 9 freeing list memory: valgrind memory error check
$ valgrind ./bin/ll_single_ins ==22898== memcheck, memory error detector ==22898== copyright (c) 2002-2012, , gnu gpl'd, julian seward et al. ==22898== using valgrind-3.8.1 , libvex; rerun -h copyright info ==22898== command: ./bin/ll_single_ins ==22898== number of nodes enter: 3 enter node[0]->number: 5 enter node[1]->number: 7 enter node[2]->number: 9 list contains '3' nodes. <snip> ==22519== heap summary: ==22519== in use @ exit: 0 bytes in 0 blocks ==22519== total heap usage: 5 allocs, 5 frees, 80 bytes allocated ==22519== ==22519== heap blocks freed -- no leaks possible ==22519== ==22519== counts of detected , suppressed errors, rerun with: -v ==22519== error summary: 0 errors 0 contexts (suppressed: 2 2)
Comments
Post a Comment