A linked list, is basically a list of elements that have a link attached to each one to the next. So for example if you have a structure like<\/p>\n
\r\nstruct List {\r\n string name;\r\n List *next;\r\n};\r\n<\/pre>\nthen the List has a internals of a name which is of type string, and then a link (a pointer) to the next List in the list of linked List types. I have called it a Elem in the source code below because then it may make more sense, since it is kinder a element of the whole linked list.<\/p>\n
So to create a I wrote a function to add a element (Elem) to the list already, since we are going to be altering the list then need to pass as a reference (&) so we actually alter the main variable and not just the functions variable and it is not passed back.<\/p>\n
\r\nstruct Elem {\r\n\tstring name;\r\n\tElem *next;\r\n};\r\n\r\n\/\/ inserts a Elem into a linked list\r\nvoid setUpElem(Elem * & list, Elem *addnew)\r\n{\r\n\taddnew->next = list;\r\n\tlist = addnew;\r\n}\r\n\r\n.. \r\nint main()\r\n{\r\n Elem *elem = NULL;\r\n Elem newElem;\r\n newElem.name = \"bob\";\r\n \r\n setUpElem(elem, &newElem);\r\n}\r\n<\/pre>\nwith the function call setUpElem, I am passing the address of the newElem because that is the pointer (the address memory location).<\/p>\n
So to start with the recursive functions, lets print out all of the elements,<\/p>\n
\r\n\/\/ just print out the top element \r\nvoid printOutElem(Elem *elem)\r\n{\r\n\tcout << \"Name : \" << elem->name << endl;\r\n}\r\n\r\n\/\/ recursive loop to print them all out\r\nvoid printThemAllOut(Elem *list)\r\n{\r\n\tif (list != NULL)\r\n\t{\r\n\t\tprintOutElem(list);\r\n\t\tprintThemAllOut(list->next);\r\n\t}\r\n}<\/pre>\nprintOutElem will print out the element name associated with the parameter, and the cool recursive function called printThemAllOut, which just re-calls itself with the link to the next element to print out.. just a nice little function..<\/p>\n
The next recursive that makes allot more sense, is when you are adding a element instead to the head of the list, but in the middle, like it is sorted, then if you was using loops you would require to keep hold of the previous element so that you can insert the new element into that previous elements -> next link and re-link the inserted element -> next to the current element in the list, hopefully the code helps to understand..<\/p>\n
\r\nvoid insertIntoMiddle(Elem *&elem, Elem *midElem)\r\n{\r\n\tElem *cur, *pre= NULL;\r\n\r\n\tfor (cur=elem; cur != NULL; cur= cur->next)\r\n\t{\r\n\t\tif (cur->name > midElem->name) break;\r\n\t\t\/\/ store where we was\r\n\t\tpre = cur;\r\n\t}\r\n\r\n\t\/\/ place the middle next element equal to where we are in the list\r\n\tmidElem->next = cur;\t\r\n\t\/\/ if the previous is not null, e.g. previous was somewhere in the list\r\n\tif (pre != NULL)\r\n\t\tpre->next = midElem; \/\/ update the previous link to the middle element\r\n\telse\r\n\t\telem = midElem;\t\t\t\/\/ else probably is empty !!.. not good.. \r\n}<\/pre>\nand here is a very nice recursive function that will do the same as above but just in recursive calls to itself with passing the previous link to itself so there is no need to keep a element of the previous link, very nice and allot more easier to debug since less code.<\/p>\n
\r\nvoid insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)\r\n{\r\n\tif (elem == NULL || elem->name > midElem->name)\r\n\t{\r\n\t\tmidElem->next = elem;\r\n\t\telem = midElem;\r\n\t}\r\n\telse\r\n\t\tinsertIntoMiddleRecursive(elem->next, midElem);\r\n}<\/pre>\nhere is the full source code<\/p>\n
\r\n#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\n\/\/ the element structure, the name is the name of the person\r\n\/\/ and the next is a link to next name\r\nstruct Elem {\r\n\tstring name;\r\n\tElem *next;\r\n};\r\n\r\n\/\/ inserts a Elem into a linked list\r\nvoid setUpElem(Elem * & list, Elem *addnew)\r\n{\r\n\taddnew->next = list;\r\n\tlist = addnew;\r\n}\r\n\r\n\/\/ just print out the top element \r\nvoid printOutElem(Elem *elem)\r\n{\r\n\tcout << \"Name : \" << elem->name << endl;\r\n}\r\n\r\n\/\/ recursive loop to print them all out\r\nvoid printThemAllOut(Elem *list)\r\n{\r\n\tif (list != NULL)\r\n\t{\r\n\t\tprintOutElem(list);\r\n\t\tprintThemAllOut(list->next);\r\n\t}\r\n}\r\n\r\n\/\/ you have to keep in contact with the current and previous \r\n\/\/ (since that is where we need to place the new element\r\nvoid insertIntoMiddle(Elem *&elem, Elem *midElem)\r\n{\r\n\tElem *cur, *pre= NULL;\r\n\r\n\tfor (cur=elem; cur != NULL; cur= cur->next)\r\n\t{\r\n\t\tif (cur->name > midElem->name) break;\r\n\t\t\/\/ store where we was\r\n\t\tpre = cur;\r\n\t}\r\n\r\n\t\/\/ place the middle next element equal to where we are in the list\r\n\tmidElem->next = cur;\t\r\n\t\/\/ if the previous is not null, e.g. previous was somewhere in the list\r\n\tif (pre != NULL)\r\n\t\tpre->next = midElem; \/\/ update the previous link to the middle element\r\n\telse\r\n\t\telem = midElem;\t\t\t\/\/ else probably is empty !!.. not good.. \r\n}\r\n\r\n\/\/ a far better way of doing this is to use recursive for inserting\r\n\/\/ since the parameter is the previous link :)\r\n\/\/ this is just a far nicer way of doing the above function\r\nvoid insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)\r\n{\r\n\tif (elem == NULL || elem->name > midElem->name)\r\n\t{\r\n\t\tmidElem->next = elem;\r\n\t\telem = midElem;\r\n\t}\r\n\telse\r\n\t\tinsertIntoMiddleRecursive(elem->next, midElem);\r\n}\r\n\r\nint main()\r\n{\r\n\tElem *elem = NULL;\r\n\r\n\tElem newElem;\r\n\tnewElem.name = \"steve\";\r\n\tsetUpElem(elem, &newElem);\r\n\tElem nextElem;\r\n\tnextElem.name = \"genux\";\r\n\tsetUpElem(elem, &nextElem);\r\n\r\n\tprintThemAllOut(elem);\r\n\r\n\t\/\/ now lets insert into the middle of the linked list\r\n\tElem midElem;\r\n\tmidElem.name = \"henry\";\r\n\tinsertIntoMiddle(elem, &midElem);\r\n\r\n\tcout << \"after the insert of \\\"henry\\\" into the middle\" << endl;\r\n\tprintThemAllOut(elem);\r\n\r\n\tElem newMidElem;\r\n\tnewMidElem.name = \"janet\";\r\n\tinsertIntoMiddleRecursive(elem, &newMidElem);\r\n\r\n\tcout << \"after the insert of \\\"janet\\\" into the middle - using recursive :) \" << endl;\r\n\tprintThemAllOut(elem);\r\n\r\n\r\n\r\n return 0;\r\n}\r\n<\/pre>\nand here is the output<\/p>\n
\r\nName : genux\r\nName : steve\r\nafter the insert of \"henry\" into the middle\r\nName : genux\r\nName : henry\r\nName : steve\r\nafter the insert of \"janet\" into the middle - using recursive :)\r\nName : genux\r\nName : henry\r\nName : janet\r\nName : steve<\/pre>\n","protected":false},"excerpt":{"rendered":"A linked list, is basically a list of elements that have a link attached to each one to the next. So for example if you have a structure like struct List { string name; List *next; }; then the List has a internals of a name which is of type string, and then a link … Continue reading Linked list – recursive functions<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[229,226],"class_list":["post-1070","post","type-post","status-publish","format-standard","hentry","category-c_and_cpp","tag-linked-list","tag-recursive"],"_links":{"self":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/comments?post=1070"}],"version-history":[{"count":1,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1070\/revisions"}],"predecessor-version":[{"id":1071,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/posts\/1070\/revisions\/1071"}],"wp:attachment":[{"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/media?parent=1070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/categories?post=1070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingfriends.com\/index.php\/wp-json\/wp\/v2\/tags?post=1070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}