CSc 335

Project 0 -- C++ Warm up
Due Dates:
Part 1: Wednesday, April 1, 2009 (no foolin'!)
Part 2: Monday, April 6, 2009



C++ is our primary language in this course, and the ability to independently learn new computer languages is a skill every computer scientist and computer engineer needs. In this project, you'll start getting comfortable with C++ by implementing an old friend -- a doubly-linked list.

Your Mission

In Part 1, you'll implement a doubly-linked list in Java. In Part 2, you'll translate it to C++.

Part 1: Java

The following starter code should be used to implement your doubly-linked list in Java. This is not meant to be a generalized list, but just a limited one with a few specific behaviors. Each node in the list will contain two elements: a key (an int) and a data item (an Object). You should keep this list in sorted order by key.

public class DLList
    private DLLElement first;  //pointer to first node
    private DLLElement last;   //pointer to last node

     * Creates an empty sorted doubly-linked list.
    public DLList()

     * Add item to the head of the list, setting the key for the new
     * head element to min_key - 1, where min_key is the smallest key
     * in the list (which should be located in the first node.)
     * If no nodes exist yet, the key will be zero.
    public void prepend(Object item)

     * Removes the head of the list and returns the data item stored in
     * it.  Returns null if no nodes exist.
    public Object removeHead()

     * Returns true if the list is empty.  Otherwise, false.
    public boolean isEmpty()

     * Inserts item into the list in sorted order according to sortKey.
    public void insert(Object item, Integer sortKey)

     * Print the list for debugging only.  The "which" parameter is
     * just a label you should print before the list so you know
     * which printing this is.  Example: 
     * PRINTING #1:
    public void printList(int which)

    // the node class (inner class)
    private class DLLElement
        private DLLElement next; 
        private DLLElement prev;
        private int key;
        private Object data;

        public DLLElement(Object item, int sortKey)


  1. Do NOT import any classes or packages. You are taking care of all the pointer manipulation yourself.

  2. You'll notice something in the code that you may not have seen before in Java: a private inner class. This lets DLList objects access the private DLLElement (node) instance variables as if they were public. So in DLList, you can say and that would be ok.

  3. You will need to create a separate class for your main() method which should test the methods above. I recommend using Strings as your data items. Watch out for special cases!

  4. You may use any development environment you wish.

Part 2: C++

Redo Part 1 in C++. All C++ programs in this entire course should be done in your account on the antipasto server. You should create three files:
  1. DLList.h for your declarations
  2. for the list implementation
  3. for your main() function, which will simply test your list functions

To help you out, here is starter code for DLList.h:

#ifndef DLLIST_H
#define DLLIST_H

class DLLElement 
    DLLElement(void *item, int sortKey);
    DLLElement *next; 
    DLLElement *prev;

    int key;
    void *data;

class DLList
    DLList();     // constructor
    ~DLList();    // destructor

    // Add item to the head of the list, setting the key for the new
    // head element to min_key - 1, where min_key is the smallest key
    // in the list (which should be located in the first node.)
    // If no nodes exist yet, the key will be zero.
    void Prepend(void *item);

    // Sets sortKey to the key of the head element and removes the head
    // of the list.
    // Returns the data stored at the head of the list.  If no nodes 
    // exist, returns null and sortKey will be left undefined.
    void *RemoveHead(int *sortKey);

    // Returns true if the list is empty.  Otherwise, false.
    bool IsEmpty();

    // Inserts item into the list in sorted order according to sortKey.
    void Insert(void *item, int sortKey);

    // Print the list for debugging only.  The "which" parameter should be
    // printed before the list so you know which printing this is.
    void PrintList(int which);

    DLLElement *first;
    DLLElement *last;



Compiling and Running programs on antipasto

You'll use g++ to compile your programs on antipasto. In the end, you won't be using it directly (because I'm requiring you to use a makefile -- see below), but if you want to compile it directly, do this:
g++ <file1> <file2> ...

where the files are all of your *.cc files. To make your compiled code traceable by the gdb debugger, use the -g option:

g++ -g <file1> <file2> ...

Remember that a link to the gdb debugger manual can be found on our web page.

Once you have removed all compiler errors, a file named a.out will be produced. This is the binary executable. To run it, just type


You may have to type ./a.out if your path variable does not include the current directory.


As I said previously, by the end of this project you won't have to compile your code directly in the way described above. That's because I'm requiring you to create a makefile to compile your program. Basically, a makefile is just a small script that tells which source files need to be (re)compiled and linked together. It makes recompiling efficient since it only compiles those files that need it. It also ends up saving you quite a bit of typing. Read this makefile tutorial to see how to make one. For your own makefile please: When complete, you should be able to just type:
make DLL
to compile your program and create the executable DLL ready to run. And, of course, please ask me if you get confused or stuck.

For this small project, a makefile is really overkill, but (1) they're lifesavers for really big projects and (2) Nachos is big enough that it uses makefiles. So understanding them now will help you understand what Nachos is doing in the future.


After getting your DLList class and your makefile to work, create one more file named This will contain two functions: Add calls to AddN() and RemoveN() to your file. Alter your makefile to include the new file in the compilation. Debug until it works.

How to turn this in

Part 1 should be zipped up and submitted to the dropbox on Blackboard. (This is probably the only time we'll be using the dropbox in this course.) Part 2 will be submitted using a script I have set up on the antipasto server. Be sure all of the files you want to turn in are in a single directory and then type

/home/csc335pub/submit csc335 <full path to directory>

where <full path to directory> is the complete path to the directory you want to submit. (Use the "pwd" command to find out the full path to your current directory). So, for example, if I kept all of my relevant files in a directory named proj0, I would submit it with

/home/csc335pub/submit csc335 /home/fernandc/proj0

You should also turn in your code on paper (for both parts). Include your output tests with your paper copy.


This project is worth 25 points: 10 points for Part 1 and 15 points for Part 2. I'll be grading on correct output, having all of the required elements in your makefile, and the quality of your testing. Be sure to check for boundary conditions (empty list, inserting at the start of the list, etc.)

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Administrative statement

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.
Return to Project Index