Linked Lists 101
Hello..
I have studied.. and studied and studied the concepts of linked lists for several weeks now.. I think I have hit the wall in my c++ career.. I understand all the theory behind them.. but when it comes to coding one up.. I am stuck.. I think the reason for this is two fold:
1.) My book I have used thus far do not provide an fully written program as an example of how to use linked lists. (but does provide full code for other things such as "stacks" and "queues"). It provides some example classes.. so there is some ambiguity when it comes to actually coding one up.
2.) Linked lists are more abstract in nature.. as compared to other data structures... like the array for example, which is much more easy to manipulate.. and doesn't require a bunch of user defined functions.
I have very seldom made a plea for help.. but this is it.
I have provided a program that I have attempted so far.. I have made up a handful of functions that I think would be useful as far as linked lists go.. I have coded up function prototypes... switch case menu.. and function definitions.
What I am looking for is simple...
I would like for someone to "fill in the gaps" of this program... complete a full example code that I can study.. so I can move on to bigger things (such as circularly linked lists and binary trees)
I would like just to be able to iterate forward and backward through a list of information.. be able to search for specific information.. and be able to insert and delete specific nodes.. and maybe make and display a copy of the current list.
Or... if you could post your own example code of how a basic linked list can be manipulated.
Either way will be fine for me.. and hopefully this thread will be of help for many others out there who are having the same problems with linked lists as I have. I will consider any answer provided groundbreaking... and I will take this knowledge and run with it.
Anyway.. here is what I've come up so far.. I call this program my, "linked list toolkit"
Code://My Linked List Toolkit #include<cstdlib> //Provides "EXIT_SUCCESS" and "system( )" #include<string> //Provides the "string" type qualifier #include<iostream> //Provides "cin" and "cout" using namespace std; /******* Linked List Function Prototypes *********/ void list_head_insert(node*& head_ptr, const node::double& entry); void list_tail_insert(node*& head_ptr, const node::double& entry); void list_insert(node* previous_ptr, const node::value_type& entry); void list_remove(node* previous_ptr); const node* list_search(const node* head_ptr, const node::value_type& target); node* list_locate(node* head_ptr, int position); void view_list(node* head_ptr); int list_length(const node* head_ptr): void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr); void list_clear(node*& head_ptr); void list_head_remove(node*& head_ptr); /******* Other Functions *********/ void print_menu(); void exit_message(); //prototype for my list struct node { string employee_name; int phone_number; node *next_ptr; node *previous_ptr; } int main() { char choice = 'x'; do { print_menu(); cin >> choice; switch(choice) { case 1: list_head_insert(); break; case 2: list_tail_insert(); break; case 3: void list_insert(); break; case 4: list_remove(); break; case 5: list_search(); break; case 6: list_locate(); break; case 7: view_list(); break; case 8: list_length(); break; case 9: list_copy(); break; case 9: list_clear(); break; case 11 list_head_remove(); break; case 12 exit_message(); break; default: cout << "Invalid Entry. Please Try Again."; } }while (choice != 12); return EXIT_SUCCESS; } /******************** Function Definitions ************************/ void print_menu() { cout << endl << endl << "\t\t*******************************************\n" << "\t\t* MAIN MENU *\n" << "\t\t*******************************************\n" << "\t\t* *\n" << "\t\t* 1-> ADD to the front of the list *\n" << "\t\t* 2-> ADD to the back of the list *\n" << "\t\t* *\n" << "\t\t* 3-> INSERT a node *\n" << "\t\t* 4-> DELETE a node *\n" << "\t\t* *\n" << "\t\t* 5-> SEARCH *\n" << "\t\t* *\n" << "\t\t* 6-> VIEW a specific node *\n" << "\t\t* 7-> VIEW entire list *\n" << "\t\t* 8-> VIEW list LENGTH *\n" << "\t\t* *\n" << "\t\t* 9-> COPY the current list *\n" << "\t\t* 10-> CLEAR the entire list *\n" << "\t\t* *\n" << "\t\t* 11-> Remove HEAD node *\n" << "\t\t* *\n" << "\t\t* 12-> QUIT *\n" << "\t\t* *\n" << "\t\t*******************************************\n" << endl << endl; } void list_head_insert(node*& head_ptr, const node::double& entry) { head_ptr = new node(entry, head_ptr); } void list_tail_insert(node*& head_ptr, const node::double& entry) { tail_ptr = new node(entry, head_ptr); } void list_insert(node* previous_ptr, const node::value_type& entry) { node *insert_ptr; insert_ptr = new node; insert_ptr->set_data(entry); insert_ptr->set_link(previous_ptr->link()); //Make the new node point to the node after insertion previous_ptr->set_link(insert_ptr); //Made the previous node point to the newly inserted node } void list_remove(node* previous_ptr) { node *remove_ptr; remove_ptr = previous_ptr->link(); previous_ptr->set_link(remove_ptr->link()); delete remove_ptr; } const node* list_search(const node* head_ptr, const node::value_type& target) { const node *cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) if (target == cursor->data()) return cursor; return NULL; } node* list_locate(node* head_ptr, int position) { const node* cursor; cursor = head_ptr; for (int i = 1; (i < position) && (cursor != NULL): ++i) cursor = cursor->link(); return cursor; } void view_list(node* head_ptr) { const node *cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) cout << cursor->get_data(entry); //or just "cout << entry" perhaps? } int list_length(const node* head_ptr) { const node *cursor; int answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) ++answer; return answer; } //I would like the copy of the linked list to be displayed next to the original list when view_list() is called void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) { head_ptr = NULL; tail_ptr = NULL; //Handle the case of the empty list if (source_ptr == NULL) return; //Make the head node for the newly created list and put data in it. list_head_insert(head_ptr, source_ptr->data()); tail_ptr = head_ptr; //Copy the reast of the nodes one at a time, adding at the tail of the new list source_ptr = source_ptr->link(); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data()); tail_ptr = tail_ptr->link(); source_ptr = source_ptr->link(); } } void list_clear(node*& head_ptr) { while (head_ptr != NULL) list_head_remove(head_ptr); } void list_head_remove(node*& head_ptr) { node *remove_ptr; remove_ptr = head_ptr; head_ptr = head_ptr->link(); delete remove_ptr; } void exit_message() { cout << "\n\tProgram will now terminate " << endl; }
I believe that being able to manipulate a linked list using these types of functions will provide basic groundwork for linked list manipulation. I hope one of you out there will be willing to just maybe put the pieces of the puzzle together.
Feel free to use, "artistic liscense" as necessary.. make any changes you need.. (like the parameter lists) This code is mainly just a skeletal outline of something I envisioned as something that could actually work someday.
So here it is... my cry for help. Anything you guys can provide will be definately appreciated.
