Binary search in linkedlist

aali's Avatar, Join Date: Jul 2008
Go4Expert Member
Hi guys

when I tried to search in kinked listby binary search
it's written in the output

"Segmenationfault"

I want to solv this problem
/**************************/
The code
Code:
#include<iostream>
#include <iostream>
#include <cstring>
using namespace std;

struct Node
{
	char * data;
	Node * prev;
	Node * next;

	Node( char * newData = NULL , Node * newPrev=NULL, Node * newNext=NULL)
	{
		data=NULL;
		updateData(newData);
		prev=newPrev;
		next=newNext;
	}

	~Node()
	{
		if(data!=NULL) delete data;
	}

	void updateData(char *newData)
	{
		if(newData!=NULL)
		{
			if(data!=NULL) 
				delete [] data;
			
			data=new char[strlen(newData)+1];
			strcpy(data,newData);
		}
		else 
			data=NULL;
	}
};

class DoubleLinkedList
{
private:
	Node * first;
	
	void destroy();
public:
	
	DoubleLinkedList(const DoubleLinkedList & copy)
	{
		Node * last_ptr, * current_Copy = copy.first , *newPtr;
		first=NULL;
		while(current_Copy!=NULL)
		{
			newPtr = new Node(current_Copy->data );
			if (first == NULL)
			{
				first = newPtr;
				last_ptr = newPtr;
			}
			else
			{
				last_ptr->next = newPtr;
				newPtr->prev=last_ptr;
				last_ptr = newPtr;
			}
			current_Copy=current_Copy->next;
		}
	}

	DoubleLinkedList();
	
	~DoubleLinkedList();

	void BuildList(char * stringArray[],int ArrayLength); 

	void addBeforeNode(char * newData,char * searchData);

	void deleteNode(char * searchData);

	int deleteOccurance(char * searchData);

	void printList();

	void reverse();

	void doublicte();
	int length()
	{
		int counter=0;
		Node* current=first;
		if(first==NULL)
			return 0;

		while(current!=NULL)
		{
			counter++;
			current=current->next;
		}	
		return counter;
	}
	
	void insetSorted( char*newdata);

Node * BinarySearch_DLL ( char * searchData)
	{
	int n = length();
	Node * MyFirst=first;

	while(MyFirst!=NULL)
		MyFirst=MyFirst->next;
	//Node* prev;	
	Node* last_ptr=MyFirst;

	MyFirst=first;
		
	Node * MyLast=last_ptr;

	Node * midel;

	if( n == 0)
		return NULL;

	if( strcmp(searchData , MyFirst->data)>0 ||strcmp( searchData ,MyLast->data )<0)
			{
				cout<<"false";
				return NULL;
			}
		
	while (	MyFirst != MyLast->next)
	{
			cout<<"true2";

			midel=MyFirst;

			for (int i=0 ; i<(n/2) ; i++)

			midel=midel->next;

			if(strcmp(searchData,midel->data)==0 )
			{
			return midel;
			cout<<"true1";
			}
	else
	{
		if(strcmp(searchData,midel->data)>0)
		{
			n=n/2;
			MyFirst=midel->next;
			cout<<"true2";
		}
		else
		{
			n=(n-1)/2;
			MyLast=midel->prev;
			cout<<"true3";
		}

	}
}
}	
	
};
//----------------------------------Simlar to SLL-----------------------------------------
DoubleLinkedList::DoubleLinkedList()
{
	first=NULL;
}
//----------------------------------Simlar to SLL-----------------------------------------
DoubleLinkedList::~DoubleLinkedList()
{
	destroy();
}
//----------------------------------Simlar to SLL-----------------------------------------
void DoubleLinkedList::destroy()
{
	Node *current;
	while (first != NULL)
	{
		current = first;
		first = first->next;
		delete current;
	}
	first = NULL;
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::BuildList(char* stringarray[], int arraylength)
{
	destroy();
	Node *new_ptr, *last_ptr;
    for (int i=0; i<arraylength; i++)
	{
		new_ptr = new Node();
		new_ptr->updateData( stringarray[i] );
		if (first == NULL)
		{
			first = new_ptr;
			last_ptr = new_ptr;
		}
        else
        {
			last_ptr->next = new_ptr;
			new_ptr->prev=last_ptr;
			last_ptr = new_ptr;
         }
	
   }
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::addBeforeNode(char *newData,char *searchData)
{
	Node * current=first;
	while(current!=NULL && strcmp(current->data,searchData) != 0)
			current=current->next;

	if(current!=NULL)
	{
		Node * newNode=new Node(newData);
		if(current == first)
		{
			newNode->next=first;
			first->prev=newNode; //new line
			first=newNode;
		}
		else
		{
			newNode->next = current;
			newNode->prev=current->prev; //new line
			current->prev->next=newNode; //line modified form prev -> next = newNode;
			current->prev=newNode;       //new line	
		}
	}
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::deleteNode(char *searchData)
{
	Node * current;
	current=first;
	while(current!=NULL && strcmp(current->data,searchData)!=0)
			current=current->next;

	if(current!=NULL)
	{
		if(current==first)
		{
			first=first->next;
			if(first!=NULL)   first->prev=NULL;			//new line
		}
		else if(current->next == NULL)	//new line
			current->prev->next = NULL;	//new line
		else
		{
			current->prev->next=current->next;//line modified form prev -> next = current->next;
			current->next->prev=current->prev;//new line
		}
	
		delete current;	
	}
}

//---------------------------------------------------------------------------------------
void DoubleLinkedList::printList()
{
	Node *current=first;
	cout<<"List Contains : "<<endl;
	if(current==NULL)
		cout<<"Empty List"<<endl;
	else
	{
		while(current!=NULL)
		{
			if(current->data !=NULL)
			cout<<current->data<<endl;
			current=current->next;
		}
		cout<<endl;
	}
}

void DoubleLinkedList::reverse()
{
		Node * current=first,*temp;
		while(current!=NULL)
		{
			// swap Node pointers next , prev
			temp=current->next;
			current->next=current->prev;
			current->prev=temp;
			// set first at the last node in the list
			if(current->prev == NULL)
				first=current;
			// set current pointer to the next node in the list
			current=current->prev;
		}
}

void DoubleLinkedList::doublicte()
{
		Node * current = first , *newPtr ;
		while(current!=NULL)
		{
			newPtr= new Node (current ->data , current,current->next);
			/*
			newPtr= new Node;
			newPtr->updateData(current ->data);
			newPtr->next = current->next;
			newPtr->prev = current;
			*/
			if(current->next !=NULL)
				current->next ->prev =newPtr;
			current->next = newPtr;
			current = newPtr->next ;
		}
}



int DoubleLinkedList::deleteOccurance(char * searchData)
{
	Node * current=first;
	int count = 0;

	while(current!=NULL)
	{
		if( strcmp(current->data,searchData)==0 )
		{
			Node * nextNode=current->next;
			if(current == first)
			{
				first=first->next;
				if(first!=NULL)   first->prev=NULL;			//new line
			}
			else if(current->next == NULL)	//new line
				current->prev->next = NULL;	//new line
			else
			{
				current->prev->next=current->next;//line modified form prev -> next = current->next;
				current->next->prev=current->prev;//new line
			}
			delete current;	
			current = nextNode;
			count++;
		}
		else
			current=current->next;
	}
	return count;
}
//---------------------------------------------------------------------------------------
void DoubleLinkedList::insetSorted( char*newdata)
{
	Node* current=first;
	Node* temp;
	Node* newptr=new Node;
	newptr->updateData(newdata);
	
	if(first==NULL)
	{
		first=newptr;
	}
	while(current!=NULL)
	{
		if(strcmp(newdata,current->data)<0)
		{
			if(current==first)
			{
		
			newptr->next=first;
			first->prev=newptr;
			first=newptr;
			return;
			}
			else
			{	
			newptr->next=current;
			newptr->prev=current->prev;
			current->prev->next=newptr;
			current->prev=newptr;
			return;
			}
		}
			else	
			temp=current;		
			current=current->next;		
			
	}
	
}
int main()
{
	DoubleLinkedList obj1;
	char* strings[] = { "a", "b", "c", "d", "e" };

	obj1.BuildList( strings, 5 );
	DoubleLinkedList obj2 ;
	obj1.BinarySearch_DLL ("Bader" );
	obj1.printList();
	//obj2.doublicte();
	/*
	obj2.insetSorted("aali" );
	obj2.insetSorted("Bader" );
	obj2.insetSorted("careem" );
	obj2.insetSorted("Fahad" );
	obj2.insetSorted("Dema" );
	obj2.insetSorted("ali" );
	obj1.printList();
	obj2.printList();
		*/
	/*cout<<"Reverse"<<endl;
	obj2.reverse();
	obj2.printList();*/
	return 0;
}

/*
int main()
{
	DoubleLinkedList obj;
	char* strings[] = { "ahmed", "yousif", "salem", "hamed", "yousif" };

	obj.BuildList( strings, 5 );
	obj.printList();
	cout<<endl;

	cout<<"Add naser Befor ahmed :"<<endl;
	obj.addBeforeNode("naser","ahmed");
	obj.printList();
	
	obj.addBeforeNode("saad","hamed");
	obj.printList();

	cout<<"Delete salem from list :"<<endl;
	obj.deleteNode("salem");
	obj.printList();

	cout<<"Delete naser from list :"<<endl;
	obj.deleteNode("naser");
	obj.printList();

	obj.reverse();
	obj.printList();
	obj.doublicte();
	obj.printList();
	obj.deleteOccurance("yousif");
	obj.printList();
	return 0;
}
*/
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
What line does it crash on?

You can find this out (a) by stepping through the code in a debugger or (b) liberally sprinkling printf() statements throughout the code (also use fflush so that the output is displayed immediately after the printf, otherwise you'll get very confused). For example:
Code:
void DoubleLinkedList::BuildList(char* stringarray[], int arraylength)
{
printf("Entered DoubleLinkedList::BuildList()"\n");fflush(stdout);
	destroy();
printf("Back from destroy()\n");fflush(stdout);
	Node *new_ptr, *last_ptr;
    for (int i=0; i<arraylength; i++)
	{
printf("In loop, i=%d\n",i);fflush(stdout);
		new_ptr = new Node();
printf("Created new node at 0x%08x\n",new_ptr);fflush(stdout);
		new_ptr->updateData( stringarray[i] );
printf("Back from updateData()\n");fflush(stdout);

...and so on
Then if, say, it printed "Created new node at..." but not "Back from updateData" then you know it crashed somewhere in Node::updateData(); and more debug code will need adding along the same lines as above to determine where it went wrong.

This is a technique I use a lot when developing software; I find it helps a lot to see what is really going on, rather than relying on what I think is going on (because usually what I think wouldn't lead to a crash, but if it does crash then what I think *must* be wrong).
aali's Avatar, Join Date: Jul 2008
Go4Expert Member
Sorry
my code in c++
not in c
and my compiler is g++
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
And because of that you think you can't use printf?
abhishek_kulkarni's Avatar, Join Date: May 2011
Newbie Member
Try the following code....

Code:
#include<stdio.h>
#include<malloc.h>

typedef struct node
{
        int data;
        struct node *next;
}NODE;
NODE *CreateList()
{
        int total,num,flag=0,i;
        NODE *start,*new,*last;
        printf("\nHow many Nodes? : ");
        scanf("%d",&total);

        start = NULL;
        for (i=0; i<total; i++)
        {
                printf("\nEnter Data : ");
                scanf("%d",&num);

                new = (NODE *)malloc(sizeof(NODE));
                new->data = num;
                new->next = NULL;

                if(flag == 0)
                {
                        start = new;
                        last = start;
                        flag = 1;
                }
                else
                {
                        last->next = new;
                        last = new;
                }
        }
        return start;
}
Show(NODE *head)
{
        NODE *temp;
        temp = head;

        printf("\n");
        if(temp==NULL)
        {
                printf("\nThe list is empty");
                return;
        }
        while(temp != NULL)
        {
                printf(" %d ",temp->data);
                temp = temp->next;
        }
        printf("\n");
}
int Lookup(NODE *start,NODE *end,int num)
{
        NODE *head1,*head2,*mid,*b4mid;
        int found = 0;

        head1 = start;
        head2 = start;

        while( (head2 != end) && (head2->next != end) )
        {
                head2 = head2->next->next;
                b4mid = head1;
                head1 = head1->next;
        }

        mid = head1;
        printf("\nStart = %d, Mid = %d,End = %d, Data = %d",start->data,mid->data,end->data,num);

        if(mid->data < num)
        {
                if(end->data < num || num < start->data) /*Num is beyond range*/
                        found = 0;
                else
                        found += Lookup(mid->next,end,num);
        }
        else if(mid->data > num)
        {
                if(start->data > num)
                        found = 0;
                else
                        found += Lookup(start,b4mid,num);
        }
        else if(mid->data == num)
                found += 1;
        else
                found = 0;

        return found;
}
int BinarySearch(NODE *head,int num)
{
        NODE *start,*mid,*b4mid,*end,*head1,*head2;
        int found = 0;
        head1 = head;
        head2 = head;
        start = head;

        while( (head2!=NULL) && (head2->next != NULL) )
        {
                head2 = head2->next->next;
                b4mid = head;
                head  = head->next;
        }

        mid = head;
        end = head2;
        printf("\nStart = %d, Mid = %d,End = %d, Data = %d",start->data,mid->data,end->data,num);

        if(mid->data < num)
        {
                if(end->data < num) /*Num is beyond range*/
                        found = 0;
                else
                        found += Lookup(mid->next,end,num);
        }
        else if(mid->data > num)
        {
                if(start->data > num)
                        found = 0;
                else
                        found += Lookup(start,b4mid,num);
        }
        else if(mid->data == num)
                found += 1;
        else
                found = 0;

        return found;
}
main()
{
        int val;
        NODE *head;
        head = CreateList();
        Show(head);
        printf("\nTo be searched? ");
        scanf("%d",&val);
        val = BinarySearch(head,val);
        if(val == 1)
        {
                printf("\nData found in a given list\n");
        }
        else
        {
                printf("\nData does not exist in a given list\n");
        }
}