1. Lab 08 part 3 intro
2. Traversing
3. Searching
4. Inserting
5. Better insert
6. Deleting
Grading

[All of lab 08]
[All labs]
[Course home page]

Searching a linked list in C

Now, write code to search the linked list. Start with the file /u/csc209h/summer/pub/lab/08/3.c , which contains appropriate calls to search(); your task is to write the search() function itself.

This will be a linear search over the linked list, and looks somewhat similar to printall() in how it goes through the list with "p = p−>next".

Since the list is in sorted order by the key, stop searching once either the key is found, or the end of the list is reached, OR the key value in the list item is greater than the search key. This early termination does not affect the big-O running time of your search algorithm, but it arguably decreases the running time by about half on average. It also simplifies your code a bit.

search() returns either −1 if the value is not found, or the data value for that key if the key is found.

Please work on this in a file named "3.c", and submit this file in the usual way, specifically

	submit -c csc209h -a lab08 3.c
(Again, it needs to compile with no errors or warnings for full credit.)

Again, please work on it yourself before looking at my solution in /u/csc209h/summer/pub/lab/08/3s.c , but please do examine my solution before proceeding even if yours is working. The loop control I use there is terse but is a style worth getting used to, because it is a less error-prone style than more verbosely-written loops.

Next, we will write code to insert into the linked list.