Sorting Linked Lists (code not concept)

This is a discussion on Sorting Linked Lists (code not concept) within the C++ Programming forums, part of the General Programming Boards category; I am a little new at this (notice the name ) I created a linked list and want to sort ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    8

    Question Sorting Linked Lists (code not concept)

    I am a little new at this (notice the name )

    I created a linked list and want to sort it (notice thread name )

    Here is my linked list:

    Code:
    struct NODE
    {
    	int data; 
    
    	NODE *next; 
    				
    };
    
    class LINKED_LIST
    {
    	public:
    		LINKED_LIST();
    		~LINKED_LIST();
    		void insertAfterHead(int);	
    		int getHead() { return head->data; } 
    		int getTail() { return tail->data; }
    		int printList();
    		bool searchList(int);
    		void clear();	
    		void removeNode(int);
    		NODE *head; 
    		NODE *tail; 
    };

    Here is my sorting method:

    Code:
    LINKED_LIST sortList(LINKED_LIST List)
    {
    	LINKED_LIST Temp;
    	NODE *walker = new NODE, *temp_node = new NODE;
    	int a = 0,b = 0;
    	walker = List.head;
    	temp_node->data = 1;
    
    	while(walker != NULL)
    	{
    		if(walker->data > temp_node->data)
    			temp_node = walker;
    		walker = walker->next;
    		if(walker->next == NULL)
    		{
    			Temp.insertAfterHead(temp_node->data);
    			delete temp_node;
    			walker = List.head;
    			NODE *temp_node = new NODE;
    			temp_node->data = 1;
    		}
    	}
    	return List;
    }
    And I have double checked it and didn't see anything wrong with it, but I make many mistakes in debugging and no idea what is wrong, perhaps some help can be offered

  2. #2
    sockets mad
    Join Date
    Mar 2002
    Posts
    126
    If you could post the exact behaviour of your sorting algorithm that would be helpful so we know exactly what's going wrong.
    C/C++ Support IRC Channel

    Server: irc.dal.net Channel: #csupport

    Come along and help make it a great resource for the community.

  3. #3
    Registered User
    Join Date
    May 2004
    Posts
    127
    The function has quite a few problems. Most notable are the fact that releasing the memory for temp_node destroys the structure of List and will cause future searches to fail with an access violation, an off by one error due to advancing walker before testing walker->next against null, returning the destroyed List instead of the sorted Temp, and memory leaks due to allocating memory for the first test using temp_node, but no release before reassigning the pointer to a node within the list.

    The following fixes all but the memory leak.
    Code:
    LINKED_LIST sortList(LINKED_LIST List)
    {
      LINKED_LIST Temp;
      NODE *walker, *temp_node = new NODE;
      walker = List.head;
      temp_node->data = 0;
    
      while(walker != NULL)
      {
        if(walker->data > temp_node->data)
          temp_node = walker;
        if(walker->next == NULL)
        {
          Temp.insertAfterHead(temp_node->data);
          List.removeNode(temp_node->data);
          walker = List.head;
          temp_node = new NODE;
          temp_node->data = 0;
        }
        walker = walker->next;
      }
    
      return Temp;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multiple Linked Lists w/HeadNode
    By tofugirl in forum C Programming
    Replies: 12
    Last Post: 12-10-2005, 10:21 AM
  2. Linked Lists
    By wvu2005 in forum C Programming
    Replies: 12
    Last Post: 10-06-2005, 12:36 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Questions on Linked Lists
    By Weng in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2003, 01:17 AM
  5. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21