## Description

Introduction

Recall the implementation of the ADT List using singly linked list discussed in class. In this implementation,

the class LList.java contains only two instance variables, firstNode of type Node,

and numberOfEntries of type int. Recall that when we implementation the method getEntry(),

we use the method getNodeAt(). Every time the method getEntry() is called, the method

getNodeAt() has to traverse the link chain from the first node to the node associated with the given

position. Imagine if our list contains 100,000 entries and we call the method getEntry() 10,000

times, this will take a while because of the method getNodeAt(). To improve the performance in

this situation, there are various solutions.

• Solution 1: We can improve the performance of our original implementation by using doubly

linked list instead of singly linked list, and adding another instance variable named lastNode

of type Node which always refer to the last node of the link chain. In doing so, it allows us

to traverse the link chain from the first node as well as the last node. Imagine if the method

getEntry() is called with a given position less than the number of entries divided by 2, the

method getNodeAt() should traverse the link chain from the first node. But if the method

getEntry() is called with a given position greater than the number of entries divided by 2,

the method getNodeAt() should traverse the link chain from the last node. In doing so, the

total length that the method getNodeAt() has to traverse the link chain should be cut in

half (in theory). As a result, faster performance compare to the original implementation.

• Solution 2: We can further improve the performance of the previous solution by adding

two more instance variables to solution 1. The first added instance variable is the instance

variable named middleNode of type Node which always refer to the node in the middle of the

link chain. But how do we know which position this middle node is associated to? That is

why we need another instance variable. The second added instance variable is the instance

variable named middlePosition of type int which always indicate the position of the node

middleNode in our list. This solution allows us to traverse the link chain in four ways.

1. From the first node forward when the given position is less than the number of entries

divided by 4.

2. From the middle node backward when the given position is less than the number of

entries divided by 2 but greater than the number of entries divided by 4.

3. From the middle node forward when the given position is greater than or equal to the

number of entries divided by 2 but less than the number of entries times 3 and divided

by 4.

4. From the last node backward when the given position is greater than the number of

entries times 3 and divided by 4.

CS/COE 0445 — Data Structure Page 1

Lab 3: Doubly Linked List with Performance

What to do

For this lab, you are going to implement solution 1 and solution 2 explained in previous section.

From the starter code (see the code DLinkedList.java), this is a very strip down version

of our LList.java discussed in class. It consists of five instance variables, firstNode,

lastNode, middleNode, numberOfEntries, and middlePosition. It contains only methods add()

and three methods for getting an entry from a given position named, getEntry(), getEntry1(),

and getEntry2(). Read carefully. The method getEntry() uses the method getNodeAt()

which is exactly the same implementation in our LList.java discussed in class. The method

getEntry1() uses the method getNodeAt1() and the method getEntry2() uses the method

getNodeAt2(). Note that the methods getNodeAt1() and the method getNodeAt2() simply use

the method getNodeAt().

What you need to do is to modify the method getNodeAt1() and the method getNodeAt2()

using the solution 1 and solution 2 discussed in previous section, respectively. Do not modify any

other methods or insert any other instance variables. Note that you do not have to worry about

setting the value of instance variables firstNode, numberOfEntries, lastNode, middleNode, and

middlePosition. They have been taken care of by the method add(). You simply use them to

develop solution 1 and solution 2.

Test Class

A test class (DLinkedListTester.java) is provided. Simply compile and run this test class. This

program will test your DLinkedList.java and show how long it takes for each method to complete

its task. An example of the output if the program DLinkedListTester is shown below:

Adding data into the list: DONE

Dry run for the method getEntry(): DONE

Time the method getEntry(): DONE

Dry run for the method getEntry1(): DONE

Time the method getEntry1(): DONE

Dry run for the method getEntry2(): DONE

Time the method getEntry2(): Done

The method getEntry() took 2942.0 millisecond.

The method getEntry1() took 1182.0 millisecond.

The method getEntry2() took 593.0 millisecond.

If getEntry1() took roughly about half the time of getEntry(), you get 5 points.

If getEntry2() took roughly about a quarter the time of getEntry(), you get 5 points.

If you implement the method getEntry1() and getEntry2() correctly, getEntry1() should take

roughly about half the time of the method getEntry() and getEntry2() should take roughly

about a quarter the time of the method getEntry().

Due Date and Submission

For the due date, please check the lab in the CourseWeb. Submit your DLinkedList.java to the

CourseWeb under this lab by the due date. No late submission will be accepted.

CS/COE 0445 — Data Structure Page 2