- It is a collection of similar components (e.g., names, telephone numbers, addresses, etc.)
- The number of elements in the list is the length of the list
- One way is using arrays (size >= length)
- Create a list
- Add an item to a list
- Delete an item from a list
- Search a list for a particular value
- Sort a list (alphabetically or numerically)
- Idea: Scan the list from left to right, swapping entries whenever a pair of adjacent elements is found to be out of order
- Make n passes over the list (n: number of elements)
void Bubblesort(int list[], int length) { int pass, i; int temp; for (pass = 1; pass < length; pass++) for(i = 0; i < length - 1; i++) if(list[i] > list[i+1]) { temp = list[i]; list[i] = list[i+1]; list[i+1] = temp; } }
- An item is missing if we pass its correct place in the list !!
void BinarySearch(int list[], int item, int length, int& index) { int first = 0; int last = length - 1; int middle, found; found=0; while( (last >= first) && (!found) ) { middle = (first + last)/2; // integer division !! if(item < list[middle]) // reject lower part of the list last = middle - 1; else if(item > list[middle]) // reject upper part of the list first = middle + 1; else found = 1; if(found) index = middle; else index = length; } }