INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56 (992 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB #10 Dynamic Memory Allocation II – Linked List

Instructor: Bashir M. Ghandi

Objective: Learn how to implement Ordered linked-list.

What is a linked list?

· Linked list, like stack and queue is a homogeneous linear list consisting of nodes in which each node is linked to the next.

· However, unlike stack and queue, an item can be deleted at any location in the list, and can be added (inserted) at any location provided the order of the items in the list is maintained.

· The following figures shows the format of a linked list and how it behaves on insertion and deletion.

· If p is inserted, the list becomes:

· If n is deleted, the list becomes:

· Thus, a linked-list is very useful in applications that require data to be in some order at all times.

· Some of the basic operations of a linked list are: CreateList, ClearList, EmptyList, FullList, SearchList, Traverse, Insert and Delete.

User Interface:

· The file list.h defines the structures and function prototypes necessary for the implementation of linked list. Open it and study it.

· Notice that KeyType and ItemType depends on the application and one of the fields of ItemType must be the key field.

Implementation.

· One way of implementing linked list is to make use of a dummy header node so that the actual data is inserted from the second node. This greatly reduces the complexity of the algorithm. This method adopted in the implementation contained in list.c.

· The next point to note is that deletion and insertion both require searching. Thus, we use the helper function FindNode in both cases.

· For Delete, FindNode returns two pointers; the address of the node to be deleted (current) and the address of the node that precedes it (previous). The following diagram shows how deletion may be achieved.

· We can also use FindNode to find a place to insert a node. However, in this case, we are not interested in the second pointer, so we called it ignore. The following figure illustrates the process.

· Note that the function Traverse depends on the application. Example is printing each node that is visited.

· Finally, note that if the key field is a string, we must use strcmp in FindNode for comparison.

Programming Exercises:

1. Copy the files list.h, list.c and lab10_1.c from my home page. Study them, create a project containing lab10_1.c and list.c and test run it. Notice that even if you type your values randomly, they are always displayed in correct order.

2. Implements the Search and Delete options. The search option should scan a target key from the user, search the list and print an appropriate message depending as a node with that key exist in the list or not. Delete option should also scan a target key from the user, delete the key if it exists in the list and print an appropriate message.

3. Modify the your program (and the list ADT ) to work with a list of words. i.e the key field is now a string (of maximum size 40 say).

4. Modify your program to work with KeyType as long and with additional fields added to ItemType as shown below:

typedef char STRING[50];

typedef long KeyType;

typedef struct { long key;

STRING name;

int exam1,exam2,exam3;

float average;

} ItemType;

You can still use your functions get_record, get_average and print_record, but you need to modify them to accept ItemType and replace id_no with key.

Home Work.

Modify Program 4 above to have two additional options:

Create from file: that creates the list from the records in file exams2.dat.

Copy to file: overwrites the content of the file exams2.dat with the content of the list.