Assignment 9

In this assignment, you are asked to implement a list ADT to support the following operations.

L = init()

Initialize L to an empty list.

L = insert(L,n)

Insert the integer n in L.

L = delete(L)

Delete the median(s) from the list L. If L contains an odd number of items, the central one is deleted. If L contains an even number of items, then the two central elements are deleted.

empty(L)

Returns true if and only if L is empty.

print(L)

Print the items stored in the list L.

Make a linked-list-based implementation of this ADT. It is useful to keep the list sorted. While inserting n, the exact location of n is first determined so as to keep the list sorted after the insertion. During deletion, the center of the list is first located. In order to locate the center, it may be useful to store the size (number of elements) in the list. In view of this, define the list data type as follows.

   typedef struct _node {
      int data;
      struct _node *next;
   } node;

   typedef struct {
      int size;
      node *head;
   } list;

Write the ADT functions as described above. Maintaining a dummy node at the beginning of the list is expected to simplify your implementation.

Your functions should be compatible with the following main() function.

   #include <stdio.h>
   #include <stdlib.h>
   #include <time.h>

   #define N 25

   int main ()
   {
      list L;
      int i;

      srand((unsigned int)time(NULL));

      L = init();

      for (i=0; i<N; ++i) {
         L = insert(L, 100 + rand() % 900);
         print(L);
      }

      while (!empty(L)) {
         L = delete(L);
         print(L);
      }

      exit(0);
   }

Lab Home

Submission Site

My Home