FOR FREE CONTENT

Sub-list Searching

Back to Programming

Description

Sub-list Searching is used to search a list of elements within another list of elements. Here the program is done using a linked list data structure, but it can also be implemented using an array data structure also. This searching technique is different than linear search or binary search as in the case of the linear or binary search only a single element is searched whether it is present or not in the list, but in the case of sub-list search a group of elements i.e. a list is searched within another list.

EXAMPLE:

Suppose we have a linked list as

Now if the searched list is

At the first step the two pointers are taken which are pointing to the first element of each list as:

And

The first element of the searched list is 54 which will be first compared with the first element of the original list i.e. 34 here. As they are not matched, the pointer ‘ptr’ will be pointing to the next element of the original list and the same element (i.e. the first element of the searched list) will be compared with the second element of the original list.

And

As they are matched, both pointers will be moved to the next element.

And,

then the 2nd element of the searched list (here, 63) will be compared with the next element of the original list (63 here). As these two elements are also matched and there is no more element in the searched list so it will be printed that the sub list is present in the original list. Now, if the element of the searched list will not get matched with any element of the original list or if the first element is matched but the second or other elements do not appear in the same sequence in the original list then it will be printed that the sub list is not present in the original list.

Algorithm

INPUT: the elements of a list and a list to be searched
OUTPUT: the message after checking whether it is present in the list or not
PROCESS:
Step 1: [defining the function ‘createlist()’]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read x [the element to be inserted]
		Set p<-new node()
		data[p]<-x
		next[p]<-null
		if head=null then
			Set head<-p
		Else
			Set next[ptr]=p
		[End of ‘if’]
		Set ptr<-p
	[End of ‘for’ loop]
[End of function ‘createlist()’]
Step 2: [defining the function ‘displaylist()’]
	Set ptr<-head
	While ptr≠null repeat
		Print data[ptr]
		Set ptr<-next[ptr]
	[End of ‘while’ loop]
[End of function ‘displaylist()’]
Step 3: [defining the function ‘search()’]
	Set ptr<-head
	Set ptr1<-head1
	While ptr≠NULL and ptr1≠NULL repeat
		If data[ptr]=data[ptr1] then
			Set ptr<-next[ptr]
			Set ptr1<-next[ptr1]
			While ptr≠NULL and ptr1≠NULL repeat
				If data[ptr]≠data[ptr1] then
					Print "The sublist is not present"
					return
				[End of ‘if’]
				Set ptr<-next[ptr]
				Set ptr1<-next[ptr1]]
				If ptr1=NULL then
					Print "The sublist is present in the list"
				[End of ‘if’]
			[End of ‘while’]
		else
			Set ptr<-next[ptr]
		[End of ‘if’]
	[End of ‘while’]
	If ptr=NULL and ptr1≠NULL then
		Print "The sublist is not present"
	[End of ‘if’]
Step 4: Take the sublist from the user and call the functions to search the elements
Step 5: Stop.

Code

ADVANTAGES:

1. It helps us to detect whether a list is present in another list or not. It helps to search for a group of elements in a list of elements.

DISADVANTAGES:

1. It is a little complicated than the linear search or binary search.

TIME COMPLEXITY:

while(ptr!=NULL&&ptr1!=NULL)------------------ O(n)

{ if(ptr->data==ptr1->data)-------------- O(c1)

{ ptr=ptr->next;

ptr1=ptr1->next;

while(ptr!=NULL&&ptr1!=NULL)--------- O(n)

{ if(ptr->data!=ptr1->data)-------- O(c2)

{ printf("\nThe sublist is not present");

return; }

ptr=ptr->next;

ptr1=ptr1->next;

if(ptr1==NULL)--------------- O(c3)

printf("\nThe sublist is present in the list"); }

}

else-------------- O(c4)

ptr=ptr->next;

Please Login to Bookmark