Thread: Inserting new nodes in a sorted double linked list

  1. #1
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56

    Inserting new nodes in a sorted double linked list

    EDIT: Solved the problem with my code. It works, but I would like to optimize it a little and insure that it conforms to the instructions given (my professor nitpicks!).

    Use a double Linked List. Prompt the user for a file with one integer per line. The file will not be sorted.

    You should then sort the file.

    Next, prompt the user to add integers to the list. When the user finishes, you should ask for an output file, and then write the sorted list, one integer per line.

    Anyway, here is my code:
    Code:
    #include <iostream>
    #include <fstream>
    using namespace std;
    
    struct node
    	{
    	int key;
    	node* next; node* last;
    	};
    
    typedef node* node_ptr;
    
    void addNode(node_ptr &list, int x, node_ptr &head)
    	{
    	if (!list)
    		{
    		list = new node;
    	          list->key = x;
    		list->next = NULL;
    		list->last = NULL;
    		head = list;
    		}	
    	else
    		{ 
    		if(list->next == NULL)
    			{
    			node_ptr tmp = new node;
    			tmp->key = x;
    			tmp->last = list;
    			tmp->next = NULL;
    			list->next = tmp;
    			list = list->next;
    			}
    		else
    			{
    			list = list->next;
    			addNode(list, x, head);
    			}
    		}
    	}
    
    void print_list(node_ptr& list, ofstream& write)
    	{
    	while(list)
    		{	
    		write << list->key << endl;
    		list = list->next;
    		}
    	}
    void insertion_sort(node_ptr &list)
    	{
        	int temp = 0; 
    	node_ptr tmp = list;
    	for (tmp = tmp->next; tmp; tmp = tmp->next)
    		{
    		list = tmp;
    	        while(list->last->key > list->key)
    			{
    			temp = list->last->key;
    			list->last->key = list->key;
    			list->key = temp;
    			if (!list->last->last) break;
    			list = list->last;
    			}
    			
    		} 
    	}
    int main()
    {
    	node_ptr p = NULL, head = NULL;
    	char inFileName[16], outFileName[16];
    	int num_nodes = 0, v = 0;
    	ifstream read;	ofstream write;
    
    	/****** Ask user for input file *****/
    	cout << "Enter file name to be read: ";
    	cin >> inFileName;
    
    	/***** open file **********/
    
    	read.open(inFileName);
    	if (read.fail())
    		{
    		cout << "Input file opening failed!"<<endl;
    		//exit(1);
    		}
    
            /* read digits in from file to linked list */
    	for (int i = 0; read >> v; i++)   
    		{
    		addNode(p, v, head);    
    		}
    	p = head;
    	insertion_sort(p); // sort the list
    	
    	/* ask user for input to enter into the linked list */
    	cout << "How many numbers do you wish to add: ";
    	cin >> num_nodes;
    	for (int i = 0; i < num_nodes; i++)
    		{
    		cout << "enter a number: ";
    		cin >> v;
    		addNode(p, v, head);
    		}
    	
    	p = head;
    	insertion_sort(p); // sort the list
    	
    	cout << "Enter a file name to write the sorted list to: ";
    	cin >> outFileName;
    	
    	write.open(outFileName);
    	if (write.fail())
    		{
    		cout << "Disk Error!" << endl;
    		}
    	p = head;
    	print_list(p, write);
    	
    
    	return 0;
    	}
    Last edited by carrja99; 03-06-2003 at 05:42 PM.

  2. #2
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56
    No one has any ideas?
    I am Error. When all else fails, use fire.

    My Current Screenshot

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >No one has any ideas?
    You said you solved your problem. Of course for improved performance you should be using a binary search tree, but apparently teachers don't accept reasonable solutions. If you really want to optimize, first check that the performance is acceptable as it is, there's no point in optimizing what you don't need to. If it is too slow, changing your sort algorithm has a high probability of improving performance, Quicksort can be modified for linked lists without too much difficulty.

    Also always delete the memory you allocated for the list when you're through with it.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. swapping nodes in double linked list
    By a0161 in forum C Programming
    Replies: 15
    Last Post: 10-30-2008, 06:12 PM
  2. Double Linked List Sorting
    By algatt in forum C Programming
    Replies: 5
    Last Post: 09-15-2007, 12:41 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM