CptS 122 – Data Structures                                                                                             

 

Programming Assignment 3: Doubly Linked Lists

 

Assigned: Friday, September 14, 2012

Due: Friday, September 21, 2012 by midnight

 

I. Learner Objectives:

 

At the conclusion of this programming assignment, participants should be able to:

 

II. Prerequisites:

 

Before starting this programming assignment, participants should be able to:

 

III. Overview & Requirements:

 

In the linked lists that we have used so far each node provides information about where is the next node in the list. It has no knowledge about where the previous node lies in memory. If we are at say 15th node in the list, then to reach the 14th node we have to traverse the list right from the first node. To avoid this we can store in each node not only the address of next node but also the address of the previous node in linked list. This arrangement is often known as 'Doubly Linked List' and is shown in the following figure.

DLL

As you can see from the illustration a doubly linked list has a pointer to the next node and the previous node in the list. The first node’s previous node pointer is always NULL and the last node’s next pointer is always NULL. When you insert and delete nodes from a doubly linked list, you must always carefully link the previous and next pointers. 

Write a C program to implement this Doubly Linked List (DLL). First declare a structure representing a node of the doubly linked list.

    struct dnode{

      struct dnode *prev;

      int data;

      struct dnode  *next;

      }

You can have the following function prototypes to implement this. 

/*adds a new node at the end of the doubly linked list*/
d_append(struct dnode **s, int num)

/*adds a new node at the beginning of the doubly linked list*/
d_addatbeg(struct dnode **s, int num)

/*adds a new node after the specified number of nodes*/
d_addafter(struct dnode *q, int loc, int num) //loc is not equal to 0

/*displays the contents of the linked list*/
d_display (struct dnode *q)

/*counts the number of nodes present in the linked list*/
d_count (struct dnode *q)

/*deletes the specified node from the doubly linked list*/
d_delete(struct dnode **s, int num)

2. In the same project, create one source file main.c.  In main.c you should have the following codes to test your implementation.

Initialize an empty doubly linked list pointed by p;

Call d_append() function to add elements at the end of the doubly linked list (DLL) ;

d_display (p); 

printf ("\n No. of Elements in the DLL: %d\n", d_count(p));

Call d_addatbeg() function to add elements at the beginning of the DLL;

d_display (p); 

printf ("\n No. of Elements in the DLL: %d\n", d_count(p));

Call d_addafter() function to add elements after the specified number of nodes in the DLL;

d_display (p); 

printf ("\n No. of Elements in the DLL: %d\n", d_count(p));

Call d_delete() function to delete elements from the DLL;

d_display (p); 

printf ("\n No. of Elements in the DLL after deletion: %d\n", d_count(p));

    Have your code print out a menu that looks like this: 

    ***PA3 Menu - (your name) *** 

    *** The list currently has (n) items *** 

    1 = Append a new integer value to the end of the list 

    2 = Append a new integer value to the beginning of the list 

    3 = Insert a new integer value after a specific number of nodes 

    4 = Delete a node with a specific integer value 

    5 = Display the contents of the list 

    Enter selection: 

Show this menu when your program starts and get the option from the user. After an option is selected, get any additional input values from the user that are relevant for the task they have selected. Then perform the task on the list and return to the menu. Note that the menu display requires you to show how many items are currently in the list (second line of menu output). Thus, your menu display code is expected to call the d_count() function.  

 

V. Submitting Assignments:

 

  1. Using the Angel tool https://lms.wsu.edu submit your assignment to your TA. You will "drop" your solution into the provided "Homework Submissions" Drop Box under the "Lessons" tab. You must upload your solutions as <your last name>_pa3.zip by the due date and time.
  2. Your .zip file should contain a project workspace. Your project folder must have at least one header file (a .h file), two C source files (which must be .c files), and project workspace. Delete the debug folder before you zip your project folders.
  3. Your project must build properly. The most points an assignment can receive if it does not build properly is 50 out of 100.

 

VI. Grading Guidelines:

 

This assignment is worth 100 points. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria: