Scribd
Upload
9 views

Lec-23,24 Sets - Copy

Uploaded by

akyadav123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
9 views

Lec-23,24 Sets - Copy

Uploaded by

akyadav123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 8

Linked-List Implementation of Sets

 The Items of the linked-list are the


members of the set.

 Linked-list uses space proportional to the


size of the set represented, not the
universal set.

 Linked-List can represent the sets where


the universal set is infinite.
Intersection in Unsorted List
 An element is in the intersection of lists L1
and L2 if and only if it is on both lists.

 In unsorted lists, we must match each


element of L1 with each element on L2.

 The process will take O(n2) steps on lists


of length n.
Intersection in Sorted List
To Match an element e on one list L1 with
the elements of another list L2, look down
L2 until;

 Either find e, that is the match has been


found.
 Or, find an element greater than e, which
indicates the match does not exist.
Intersection in Sorted List

 If d is the element on L1 that immediately precedes


e.

 And the first element found on L2 is f, such that d


<= f, then to search L2 for an occurrence of e we
can begin with f.
 Thus, we can find matches for all the elements of
L1, if they exist, by scanning L1 and L2 once.
Assign in Sorted List
 A=B
 Copy all elements in B to A.

 Cannot be implemented by pointing the


header cell of A to the header cell of B.

 Subsequent, changes in B will result in


unexpected changes in A.
Union in Sorted List
 C=AB
 Attach all the elements from either A or B list to the C
list, in their proper, sorted order.
 Compare the elements of A with B.
 If the elements are equal add once to C.
 If the elements are unequal, add the elements from
the smaller element’s list until a larger element is
found.
 If one list exhausts, append the elements of the other
list as it is.
Difference in Sorted List
 C=A–B

 Do not add an element to the C list when equal


elements are found.

 Add the current A list element to the C list when it is


smaller than the current B list element; since the
former cannot be found on the B list.
 If B exhausts then append all the remaining
elements of A.
Other Operations
 MIN: Return the first element on the list.

 FIND: Search through the list and return when the


target element is found.
 DELETE: Same as FIND but dispose of the target
element.
 INSERTION: Find out the position of the element to
be inserted in order, and then change the pointers
appropriately.

You might also like