sort linked list using BST

Hi, in FAQ, Prelude's corner in section Linked List I found this:
". Another alternative way of sorting a linked list is not obvious at first, but uses the fact that a binary tree is always sorted. Simply walk the list, removing the first item and inserting it into a binary tree. Then do an inorder traversal of the tree, inserting at the end of a new list. Often it makes sense to switch between data structures, despite what people may tell you. "

So I tried to write that. Here's my code:

Code:

---

/* SingleLinkedList.h*/
#ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H

enum {FAIL,SUCCES};
typedef struct Node
{
        int data;
        struct Node* next;
}node;

//for sort
typedef struct _BST
{
        int data;
        struct _BST* left;
        struct _BST* right;
}BST;

int InsertHead(node**,int);
int InsertEnd(node**,int);
int InsertNext(node*,int);
int RemoveHead(node**);
int RemoveEnd(node**);
int RemoveNext(node*);
int RemoveAll(node**);
int RemoveDuplicates(node*);
int Length(node*);
void Show(node*);
node* Find(node*,int);
//for sort purpose
BST* CreateBST(node*);
void InsertBST(BST**,int);
node* Sort(node*);
node* HelperSort(BST*);

void PrintTree(BST*);
#endif

---

Implementation file:

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include "SingleLinkedList.h"


int InsertHead(node** head,int data)
{
        node* current=(node*)malloc(sizeof(node));
        if(!current)
        {
                return FAIL;
        }
        current->data=data;
        current->next=NULL;
        if(*head==NULL)
        {
                *head=current;
                return SUCCES;
        }
        current->next=*head;
        *head=current;
        return SUCCES;
}

int InsertEnd(node** head,int data)
{
        node*walk=*head;
        node* current=(node*)malloc(sizeof(node));
        current->data=data;
        current->next=NULL;
        if(!current)
        {
                return FAIL;
        }
        if(!*head)
        {
                *head=current;
                return SUCCES;
        }
       
        for(;walk->next;walk=walk->next);
        walk->next=current;
        return SUCCES;
}

int InsertNext(node* prev,int data)
{
        node* current;
        if(!prev)
        {
                return FAIL;
        }
        current=(node*)malloc(sizeof(node));
        if(!current)
        {
                return FAIL;
        }
        current->data=data;
       
        current->next=prev->next;
        prev->next=current;
        return SUCCES;
}

int RemoveHead(node** head)
{
        node* helper;
        if(!*head)
        {
                printf("\nNothing to remove!");
                return FAIL;
        }
       
        helper=*head;
        *head=(*head)->next;
        free(helper);
        return SUCCES;
}

int RemoveEnd(node** head)
{
        node* helper;
        if(!*head)
        {
                printf("\nNothing to remove!");
                return FAIL;
        }
        for(helper=*head;helper->next->next;helper=helper->next);
        free(helper->next);
        helper->next=NULL;
        return SUCCES;
}

int RemoveNext(node* prev)
{
        node* helper;
        if(!prev)
        {
                return FAIL;
        }
        helper=prev->next;
        prev->next=helper->next;
        free(helper);
        return SUCCES;
}

int RemoveAll(node** head)
{
        node* save;
        if(!*head)
        {
                return FAIL;
        }
        while(*head)
        {
                save=(*head)->next;
                free(*head);
                *head=save;
        }
        return SUCCES;
}

int RemoveDuplicates(node* head)
{
        node* helper=head;
        node* tmp;
        if(!helper)
        {
                return FAIL;
        }
        while(helper->next)
        {
                if(helper->data==helper->next->data)
                {
                        tmp=helper->next->next;
                        free(helper->next);
                        helper->next=tmp;
                }
                else
                {
                        helper=helper->next;
                }
        }
        return SUCCES;
}

int Length(node* walk)
{
        int len=1;
        if(!walk)
        {
                return FAIL;
        }
        while(walk=walk->next)
        {
                len++;
        }
        return len;
}

void Show(node* walk)
{
        if(!walk)
        {
                printf("There are no elements in the list!");
                return;
        }
        printf("Elements:\n");
        for(;walk;walk=walk->next)
        {
                printf("%d ",walk->data);
        }
        printf("\n");
}

node* Find(node*walk,int data)
{
        if(!walk)
        {
                return NULL;
        }
        for(;walk;walk=walk->next)
        {
                if(walk->data==data)
                        return walk;
        }
        return NULL;
}

BST* CreateBST(node* head)
{
        BST* root=NULL;

        while(head)
        {
                InsertBST(&root,head->data);
                head=head->next;
        }
        return root;
}

void InsertBST(BST** root,int data)
{
        if(!*root)
        {
                *root=malloc(sizeof(BST));
                (*root)->data=data;
                (*root)->left=NULL;
                (*root)->right=NULL;
                return;
        }
        else
        {
        if((*root)->data>data)
                InsertBST(&(*root)->left,data);
        else
                InsertBST(&(*root)->right,data);
        }
}

node* Sort(node* head)
{
        node* sortlist;
        BST* root=CreateBST(head);
        RemoveAll(&head);
        sortlist=HelperSort(root);
       
        return sortlist;
}

node* HelperSort(BST* root)
{
        node*head=NULL;
        if(!root)
        {
               
                return NULL;
        }
        HelperSort(root->left);
        InsertEnd(&head,root->data);
        HelperSort(root->right);
        return head;
}

void PrintTree(BST* root)
{
        if(!root)
        {
                return;
        }
        PrintTree(root->left);
        printf("%d ",root->data);
        PrintTree(root->right);
}

---

And finally test file

Code:

---

#include <stdio.h>
#include "SingleLinkedList.h"

int main()
{
        node* head=NULL;
        node*sorted;
        InsertHead(&head,1);
        InsertHead(&head,1);
        InsertHead(&head,2);
        InsertEnd(&head,3);
        Show(head);
       
        sorted=Sort(head);
        Show(sorted);
        return 0;
}

---

And, of coure it's not working properly. I think that Binary Tree is created ok, but problem is how to create new list from tree in HelperSort because head is created again and again in recursion. I was thinking to add another argument to function, int value to ensure head is created only once. But there must be another way.

Thanks for help!

Here's the basic idea (except I used front list insertion instead of rear insertion, thus requiring the inorder tree traversal to go in descending order):

Code:

---

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node *link[2];
};

struct node *make_node ( int data )
{
  struct node *node = malloc ( sizeof *node );

  if ( node == NULL )
    return NULL;

  node->data = data;
  node->link[0] = node->link[1] = NULL;

  return node;
}

struct node *insert_tree ( struct node *tree, struct node *node )
{
  if ( tree == NULL )
    tree = node;
  else {
    int dir = node->data > tree->data;
    tree->link[dir] = insert_tree (tree->link[dir], node );
  }

  return tree;
}

struct node *insert_list ( struct node *list, struct node *node )
{
  /* Front insertion */
  node->link[1] = list;
  node->link[0] = NULL;

  if ( list != NULL )
    list->link[0] = node;
 
  return node;
}

void tree_to_list ( struct node *tree, struct node **list )
{
  struct node *save;

  if ( tree == NULL )
    return;

  tree_to_list ( tree->link[1], list );

  save = tree->link[0];
  tree->link[0] = tree->link[1] = NULL;
  *list = insert_list ( *list, tree );

  tree_to_list ( save, list );
}

struct node *tree_sort ( struct node *list )
{
  struct node *tree = NULL;
  struct node *save;

  while ( list != NULL ) {
    save = list->link[1];
    list->link[0] = list->link[1] = NULL;
    tree = insert_tree ( tree, list );
    list = save;
  }

  tree_to_list ( tree, &list );

  return list;
}

int main ( void )
{
  struct node *list = NULL;
  struct node *it;
  int i;

  for ( i = 0; i < 10; i++ )
    list = insert_list ( list, make_node ( rand() % 100 ) );

  for ( it = list; it != NULL; it = it->link[1] )
    printf ( "%d->", it->data );
  printf ( "\n" );

  list = tree_sort ( list );

  for ( it = list; it != NULL; it = it->link[1] )
    printf ( "%d->", it->data );
  printf ( "\n" );

  return 0;
}

---

Oh no, I can't believe it, I can't believe it, I refuse to believe it. I can swear I tried that before I posted this issue. I don't know how this happened.
Thanks Prelude, I knew it is only a matter of minutes when you'll respond. I tried to implement your code and actually I manage to get it works:

Code:

---

node* Sort(node* head)
{
        node* sorted=NULL;
        BST* root=CreateBST(head);
        HelperSort(root,&sorted);
        return sorted;
}

void HelperSort(BST* root,node** list)
{
        if(!root)
        {
                return ;
        }
        HelperSort(root->left,list);
        InsertEnd(list,root->data);
        HelperSort(root->right,list);
}

---

I think it would be good to destroy tree after I've done with it.
I'll need a little more help from you though.
Is this OK?

Code:

---

void DestroyBST(BST** root)
{
        if(!*root)
        {
                return;
        }
        DestroyBST(&(*root)->left);
        DestroyBST(&(*root)->right);
        free(*root);
        *root=NULL;
}

---

I'm looking forward to your answer!
However you mentioned earlier that insert sort is very useful with sorting linked list. Please, could you post a sample code?

>I think it would be good to destroy tree after I've done with it.
Um, that wouldn't be wise. The whole reason that this algorithm is reasonably efficient is because malloc isn't called. The tree is built using nodes already in the list and the list is built using nodes from the tree. The only thing we're doing is performing link surgery. That's why the list must be doubly linked, because the left and right tree links correspond to forward and back list links.

Anyway, since the nodes already exist and are just being restructured, the result of destroying the tree would be destroying the list as well. While that certainly makes future searching and sorting operations zippy, it's not conducive to a robust program. ;)

>However you mentioned earlier that insert sort is very useful with sorting linked list.
Mergesort is better for large lists, insertion sort is quick and easy for short lists.

>Please, could you post a sample code?

Code:

---

struct node *insertion_sort ( struct node *list )
{
  struct node dummy = {0};
  struct node *it_list, *it_new;
  struct node *save;

  for ( it_list = list; it_list != NULL; it_list = save ) {
    save = it_list->next;

    for ( it_new = &dummy; it_new->next != NULL; it_new = it_new->next ) {
      if ( it_new->next->data > it_list->data )
        break;
    }

    it_list->next = it_new->next;
    it_new->next = it_list;
  }

  return dummy.next;
}

---

Oh, Ok.
What I did was to create BST from linked list, and then create a complete new linked list. I kwas wondering about efficiency. I'll try to implement this using doubly linked list

>What I did was to create BST from linked list, and then create a complete new linked list.
There's no reason to do this because not only will you be creating new nodes, you will also need to destroy the old nodes to avoid memory leaks. By reusing back and forward links as left and right links, you can avoid a lot of overhead. The key is noticing that it doesn't really matter what the links do as long as both data structures use the same number of them.

>I kwas wondering about efficiency.
See if you can think of any ways to do this without an explicit binary search tree so that an efficient array based sort is possible. :)

I've done it. According to your advice Prelude I used doubly linked list. Now I completely realise why is better to use:

Code:

---

struct node {
  int data;
  struct node *link[2];
};

---

and not

Code:

---

struct node {
  int data;
  struct node *next;/* or left*/
struct node* prev;/* or right*/
};

---

I think that everything works fine now. And for you to see that your posts and advices aren't gone with the wind, here's complete code (maybe someone will find it useful):
header:

Code:

---

#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

enum {FAIL,SUCCES};

typedef struct Node
{
        int data;
        struct Node* next;
        struct Node* prev;
}node;

int InsertHead(node**,int);
int InsertEnd(node**,int);
int InsertNext(node*,int);
int RemoveHead(node**);
int RemoveEnd(node**);
int RemoveNext(node*);
int RemoveAll(node**);
int Length(node*);
void Show(node*);
//BST
void InsertBST(node **,node*);
void BSTList (node *,node**);
node* BSTSort(node*);
#endif

---

implementation:

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include "DoublyLinkedList.h"

int InsertHead(node** head,int data)
{
        node* current=(node*)malloc(sizeof(node));

        if(!current)
        {
                return FAIL;
        }
        current->data=data;
        current->prev=current->next=NULL;
        if(!*head)
        {
                *head=current;
                return SUCCES;
        }
        current->next=*head;
        *head=current;

        return SUCCES;
}

int InsertEnd(node** head,int data)
{
        node* current=(node*)malloc(sizeof(node));
        node* walk=*head;
        if(!current)
        {
                return FAIL;
        }
        current->data=data;
        current->prev=current->next=NULL;
        if(!*head)
        {
                *head=current;
                return SUCCES;
        }
        for(;walk->next;walk=walk->next);
        walk->next=current;
        current->prev=walk;
        return SUCCES;
}

int InsertNext(node* prev,int data)
{
        node* current=(node*)malloc(sizeof(node));
        if(!current || !prev)
        {
                return FAIL;
        }
        current->data=data;
        current->next=prev->next;
        prev->next=current;
        current->prev=prev;
        current->next->prev=current;
        return SUCCES;
}

int RemoveHead(node** head)
{
        node* helper;
        if(!*head)
        {
                printf("\nNothing to remove!");
                return FAIL;
        }
        helper=*head;
        *head=(*head)->next;
        (*head)->prev=NULL;
        free(helper);
        return SUCCES;
}

int RemoveEnd(node** head)
{
        node* helper;
        if(!*head)
        {
                printf("\nNothing to remove!");
                return FAIL;
        }
        if(!(*head)->next)
        {
                free(*head);
                *head=NULL;
                return SUCCES;
        }
        for(helper=*head;helper->next->next;helper=helper->next);
        free(helper->next);
        helper->next=NULL;
        return SUCCES;
}

int RemoveNext(node* previous)
{
        node* helper;
        if(!previous)
        {
                return FAIL;
        }
        helper=previous->next;
        helper->next->prev=previous;
        previous->next=previous->next->next;
        free(helper);
        return SUCCES;
}

int RemoveAll(node** head)
{
        node* save;
        if(!*head)
        {
                return FAIL;
        }
        while(*head)
        {
                save=(*head)->next;
                free(*head);
                *head=save;
        }
        return SUCCES;
}

int Length(node* walk)
{
        int len=1;
        if(!walk)
        {
                return FAIL;
        }
        while(walk=walk->next)
        {
                len++;
        }
        return len;
}

node* Find(node*walk,int data)
{
        if(!walk)
        {
                return NULL;
        }
        for(;walk;walk=walk->next)
        {
                if(walk->data==data)
                        return walk;
        }
        return NULL;
}

void Show(node* head)
{
        if(!head)
        {
                printf("\nThere are no elements in the list!\n");
                return;
        }
        printf("\n");
        while(head)
        {
                printf("%d ",head->data);
                head=head->next;
        }
}

void InsertBST(node **tree, node* element)
{
        if (*tree == NULL)
        {
                *tree = element;
                (*tree)->next=(*tree)->prev=NULL;
                return;
        }

        if(element->data<=(*tree)->data)
                InsertBST(&(*tree)->prev,element);
        else
                InsertBST(&(*tree)->next,element);
}

void BSTList (node* tree,node** list)
{
        node* save;
        if(!tree)
        {
                return;
        }
        BSTList(tree->next,list);

        save=tree->prev;
        tree->next=tree->prev=NULL;
        InsertHead(list, tree->data);

        BSTList(save,list);
}

node* BSTSort(node* list)
{
        node* tree=NULL, *save;

        while(list)
        {
                save=list->next;
                list->prev=list->next=NULL;
                InsertBST(&tree,list);
                list=save;
        }
        BSTList(tree,&list);
        return list;
}

---

And finally test program

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include "DoublyLinkedList.h"
#include <crtdbg.h>


int main()
{
        node* head=NULL;
        int i;
        for(i=0;i<10;i++)
                InsertHead(&head,rand()%10);
               
        Show(head);
        head=BSTSort(head);       
        Show(head);

}

---

I would also like if you can examine parts of this code, especially functions RemoveEnd nad RemoveHead. I think that is correct, but for me it looks like a little bulky. If you can do that and give your opinion I would greatly appreciate it.
Thanks!

Remove end could be simply:

Code:

---

int re( node **list )
{
    node *p = NULL;
    for( p = *list; p && p->next; p = p->next );
    if( p )
    {
        if( p == *list )
            *list = NULL;
        if( p->prev )
            p->prev->next = NULL;
        free( p );
        return ENDNODEDELETED;
    }
    return STOPPASSINGMEANULLLIST;
}

---

Assuming you're using this as a double linked list, that should suffice.

You have a problem in your beheading code. If you only have one node in the list, and you try to remove the head, when you assign this:

Code:

---

        *head=(*head)->next;
        (*head)->prev=NULL;

---

You'll likely end up crashing your program. Or some other BadThing(tm). You'll want to add a check in there. Something like:

Code:

---

int RemoveHead(node** head)
{
        node* helper;

        if( (helper = *head) )
        {
                if( (*head = helper->next) )
                        helper->next->prev = NULL;

                free( helper );

                return QUEENOFHEARTS;
        }
        return RUNICHABODRUN;
}

---

That looks about right. If you don't like the squished if checks, just seperate each into two seperate tasks.

Quzah.

Yes, you're right quzah, thanks!
I've fixed what you said!
I assume the rest of the code is OK