Linked list with a dummy first node: element 0 element 1 element 2 item next ite

Question

Linked list with a dummy first node:

element 0 element 1 element 2

item

next

item

next

item

next

head = size = 2

This trick will allow your code to be a little simpler, not requiring a special case for add or remove operations at index 0. Your constructor method will be:

}
You need to write a class called LinkedList that implements the following List interface:

Assignment 9

}
In addition to the interface, your LinkedList class needs to implement a toString() method

that prints the list in the format

Specifications, notes, and hints

Your program needs to meet the following specifications:

2

Assignment 9

Submit the file LinkedList.java. Your Node class should be an inner class within the LinkedList class. Make sure your class implements the interface as specified, i.e. your class should begin with public class LinkedList implements List.

None of your methods should contain a test for the index being equal to 0, as the point is to have a simpler implementation.

When commenting your code use Javadoc style comments at the beginning of each method.

Put comments at the top of the file with your name, EID, email address, date and course, and a short (one or two line) description of what the program does. We will be testing the code on the machines in the CS computer lab, so make sure your code runs on those machines.

Submit your source code files via the checkin program by the due date (read the course syllabus for the late policy).

Explanation / Answer

Given below is the code for the question.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you

List.java
------
// a list interface
public interface List {
public boolean isEmpty();
// returns true if the list is empty, false otherwise
public int size();
// returns the number of items in the list
public void add(Object item);
// adds an item to the list
// precondition: none
// postcondition: item is added at the end of the list
public void add(int index, Object item);
// adds an item to the list at the given index
// precondition: none
// postcondition: item is added at the given index;
// the indices of following items are increased by 1.
public void remove(int index);
// removes the item from the list that has the given index
// precondition: none
// postcondition: removes the first item in the list whose equl method
// matches that of the given item
public void remove(Object item);
// removes an item from the list
// precondition: none
// postcondition: removes the first item in the list whose equal method
// matches that of the given item; the indices of the following items are
// decreased by 1
public List duplicate();
// creates a duplicate of the list
// precondition: none
// postcondition: returns a copy of the linked list
public List duplicateReversed();
// creates a duplicate of the list with the nodes in reverse order
// precondition: none
// postcondition: returns a copy of the linked list with the nodes in
// reverse order
}

LinkedList.java
------

public class LinkedList implements List {
class Node{
Object data;
Node next;

Node(Object d){
data = d;
next = null;
}
}

private Node head;
private int size;

public LinkedList(){
head = new Node(null);
size = 0;
}

@Override
public boolean isEmpty() {
if(size == 0)
return true;
else
return false;
}

@Override
public int size() {
return size;
}

@Override
public void add(Object item) {
Node n = new Node(item);
Node tail = head;

// find last node
while(tail.next != null)
tail = tail.next;

tail.next = n;
size++;
}

@Override
public void add(int index, Object item) {

if(index < 0 || index > size) //invalid index
return;
Node current = head;
for(int i = 0 ; i < index; i++)
current = current.next;

Node n = new Node(item);
n.next = current.next;
current.next = n;
size++;
}

@Override
public void remove(int index) {
if(index < 0 || index >= size) //invalid index
return;
Node current = head;
for(int i = 0 ; i < index; i++)
current = current.next;

current.next = current.next.next;
size--;
}

@Override
public void remove(Object item) {
Node current = head.next;
Node previous = head;

while(current != null){
if(current.data.equals(item))
break;
previous = current;
current = current.next;
}

if(current == null)//not found
return;

previous.next = current.next;
size--;
}

@Override
public List duplicate() {
List copy = new LinkedList();
Node current = head.next;
while(current != null){
copy.add(current.data);
current = current.next;
}
return copy;
}

@Override
public List duplicateReversed() {
List rev = new LinkedList();
Node current = head.next;
while(current != null){
rev.add(0, current.data);
current = current.next;
}
return rev;

}

public String toString()
{
String s = "[ size: "+ size + " ";
Node n = head;
if(!isEmpty())
{
s += n.data;
n = n.next;
while(n != null)
{
s += ", " + n.data;
n = n.next;
}
}
s += " ]";
return s;
}
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.