Linked Lists CS 161 Assignment 9 (due Nov. 19th at 5pm) Linked list assignment v
ID: 3908334 • Letter: L
Question
Linked Lists
CS 161
Assignment 9 (due Nov. 19th at 5pm)
Linked list assignment
variant has a dummy node pointed to by the head link as shown in the following figure:
In this assignment you will write a program that implements a variant of a linked list. This
Linked list with a dummy first node:
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).
Linked list with a dummy first node: item next item next item next head = -3 17 size2Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// LinkedList.java
public class LinkedList implements List {
// attributes
private Node head;
private int size;
/**
* constructor
*/
public LinkedList() {
head = new Node(null);
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public void add(Object item) {
// creating a node
Node newNode = new Node(item);
Node temp = head;
// finding last node
while (temp.next != null) {
temp = temp.next;
}
// appending to the end
temp.next = newNode;
size++;
}
@Override
public void add(int index, Object item) {
Node newNode = new Node(item);
/**
* validating the index are within range (note that this is not a check
* for testing if the index is equal to 0)
*/
if (index >= 0 && index <= size) {
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
// adding to the specified index
Node nxt = temp.next;
temp.next = newNode;
newNode.next = nxt;
size++;
}
}
@Override
public void remove(int index) {
if (index >= 0 && index < size) {
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
// removing the node in between (if exists)
temp.next = temp.next.next;
size--;
}
}
@Override
public void remove(Object item) {
Node temp = head.next;
int index = 0;
// finding the index
while (temp != null) {
if (temp.data.equals(item)) {
// removing by index
remove(index);
break;
}
temp = temp.next;
index++;
}
}
@Override
public List duplicate() {
// creating a list
LinkedList list = new LinkedList();
Node temp = head;
// adding all elements of this list into the new list
for (int i = 0; i < size; i++) {
list.add(temp.next.data);
temp = temp.next;
}
return list;
}
@Override
public List duplicateReversed() {
// creating a list
LinkedList list = new LinkedList();
Node temp = head;
// adding all elements of this list into the new list in reverse order
for (int i = 0; i < size; i++) {
/**
* adding to index 0 will make sure that the objects are arranged in
* reverse order
*/
list.add(0, temp.next.data);
temp = temp.next;
}
return list;
}
@Override
public String toString() {
// returning a String which is in the format [size: <size>
// <item1>,<item2>..]
String data = "[size: " + size + " ";
Node temp = head;
for (int i = 0; i < size; i++) {
temp = temp.next;
data += temp.data;
if (i != size - 1) {
data += ", ";
}
}
data += "]";
return data;
}
/**
* an inner class to represent a single node
*/
private class Node {
Object data;
Node next;
public Node(Object data) {
this.data = data;
}
}
}
// Test.java
public class Test {
public static void main(String[] args) {
/**
* creating and testing LinkedList objects and methods thoroughly
*/
LinkedList list = new LinkedList();
System.out.println("list1: " + list);
list.add("Felicity");
list.add("Oliver");
list.add("Henry");
list.add("Ralph");
list.add("Catelyn");
System.out.println("list1: " + list);
System.out.println("Adding an element at index 0");
list.add(0, "Barry");
System.out.println("list1: " + list);
System.out.println("Duplicating the list");
LinkedList list2 = (LinkedList) list.duplicate();
System.out.println("list2: " + list2);
System.out.println("Duplicating the list in reverse order");
LinkedList list3 = (LinkedList) list.duplicateReversed();
System.out.println("list3: " + list3);
System.out.println("Removing object at index 4 from list 3");
list3.remove(4);
System.out.println("list3: " + list3);
System.out.println("Removing 'Catelyn' from list 3");
list3.remove("Catelyn");
System.out.println("list3: " + list3);
}
}
/*OUTPUT*/
list1: [size: 0 ]
list1: [size: 5 Felicity, Oliver, Henry, Ralph, Catelyn]
Adding an element at index 0
list1: [size: 6 Barry, Felicity, Oliver, Henry, Ralph, Catelyn]
Duplicating the list
list2: [size: 6 Barry, Felicity, Oliver, Henry, Ralph, Catelyn]
Duplicating the list in reverse order
list3: [size: 6 Catelyn, Ralph, Henry, Oliver, Felicity, Barry]
Removing object at index 4 from list 3
list3: [size: 5 Catelyn, Ralph, Henry, Oliver, Barry]
Removing 'Catelyn' from list 3
list3: [size: 4 Ralph, Henry, Oliver, Barry]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.