Fall 2004
Monday 3:00 - 4:00 Rm 343, Friday 2:00 - 4:00 Rm 343
This topic discusses three whole applications to demonstrate the benefits of linked lists. The first uses linked lists to implement a phone book with significantly more functionality than the previous example (that used a dynamically allocated array). The second uses linked lists to allow multiplication involving one number of arbitrary size. The third uses linked lists to compute counts of all distinct words in a text file.
The phone book example is similar to many real-world applications that allow users to store a list of objects. In this case, each object is an entry in a phone book, but an application that keeps track of a store inventory to buy or sell, for example, would be implemented with a very similar program. In a sense, this program just puts together all of the individual routines we have been discussing for a single application. The program allows the user to read a phone book from a specified file, save the current data to a specified file, display all entries, search for an entry, insert a new entry, or delete an entry. The implementation uses a simple text interface. If you understand this program in its entirety, you have a decent understanding of most of the major routines that operate on linked lists.
The multiplication example is interesting in that the linked list does not represent a list of objects, but a single object in which each node is a part. In this case, each node represents a single digit, and the list as a whole represents a number. A system with 32-bit integers (or any size integers) can not store numbers above a certain size, but some applications do not want to adhere to such a cutoff. Storing integers as a linked list of digits is probably the simplest way to avoid any such requirement. If you look at my CS 102 web page from Fall 2003, you will see a program that allows the user to add two integers of any size (solution to homework #5). This program allows the user to multiply a single integer of any size with a "small" integer (one that is at most one tenth of the size that an integer variable can store).
The final example uses linked lists to count the number of occurrences of all words in a specified text file. This is an example of a linked list that does not create a new node for every object, but rather increases the count (stored as a field of the node) when an object that has already been seen (in this case, a word) is seen again. Statistics such as these counts are often used in real-world text processing applications (e.g. web searching).