Lab 2

To reinforce our understanding of linked lists, today we will implement a doubly-linked list. For now this list will contain integers, and next week we will work on making it generic (so that it can hold objects of any type). You should create a directory called lab2 where you will save your work, and gsubmit this directory when you are done with the lab.

We start with an incomplete implementation given in This class contains an inner Node class, which holds an int and a reference to the previous and next Node. Note that this implementation used two "dummy" nodes: one for the head of the list and the other one for the tail, which are linked to each other in the constructor. Thus there are no special cases to consider when the list is empty.

Your job is to implement the following methods:

public void add(int index, int x)

public int get(int index)

public int set(int index, int newVal)

public int remove(int index)

See the comments in the code for an exact description of what each method does. Assume that the list is indexed starting at 0, so get(0) should return the first item in the list. To simplify your implementation, you can use several "helper" methods. These methods are private, so they are not available to the client. The helper methods are:

private void addBefore(Node p, int x)

private int remove(Node p)

private Node getNode(int idx)

The getNode method has already been implemented for you, but you will need to fill in the other ones.

Once you finish adding functionality to, you should be able to run The amount of code you need to write is very small, so think carefully about what is going on :)