Please help me to write the insert and remove code. public class DList2 { /** *
ID: 3746719 • Letter: P
Question
Please help me to write the insert and remove code.
public class DList2 {
/**
* head references the sentinel node.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
protected DListNode2 head;
protected long size;
/* DList2 invariants:
* 1) head != null.
* 2) For any DListNode2 x in a DList2, x.next != null.
* 3) For any DListNode2 x in a DList2, x.prev != null.
* 4) For any DListNode2 x in a DList2, if x.next == y, then y.prev == x.
* 5) For any DListNode2 x in a DList2, if x.prev == y, then y.next == x.
* 6) size is the number of DListNode2s, NOT COUNTING the sentinel
* (denoted by "head"), that can be accessed from the sentinel by
* a sequence of "next" references.
*/
/**
* DList2() constructor for an empty DList2.
*/
public DList2() {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = head;
head.prev = head;
size = 0;
}
/**
* DList2() constructor for a one-node DList2.
*/
public DList2(int a) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = head.next;
head.next.prev = head;
head.prev.next = head;
size = 1;
}
/**
* DList2() constructor for a two-node DList2.
*/
public DList2(int a, int b) {
head = new DListNode2();
head.item = Integer.MIN_VALUE;
head.next = new DListNode2();
head.next.item = a;
head.prev = new DListNode2();
head.prev.item = b;
head.next.prev = head;
head.next.next = head.prev;
head.prev.next = head;
head.prev.prev = head.next;
size = 2;
}
/**
* insertFront() inserts an item at the front of a DList2.
*/
public void insertFront(int i) {
// Your solution here.
}
/**
* removeFront() removes the first item (and first non-sentinel node) from
* a DList2. If the list is empty, do nothing.
*/
public void removeFront() {
// Your solution here.
}
/**
* toString() returns a String representation of this DList.
*
* DO NOT CHANGE THIS METHOD.
*
* @return a String representation of this DList.
*/
public String toString() {
String result = "[ ";
DListNode2 current = head.next;
while (current != head) {
result = result + current.item + " ";
current = current.next;
}
return result + "]";
}
public static void main(String[] args) {
// DO NOT CHANGE THE FOLLOWING CODE.
DList2 l = new DList2();
System.out.println("### TESTING insertFront ### Empty list is " + l);
l.insertFront(9);
System.out.println(" Inserting 9 at front. List with 9 is " + l);
if (l.head.next.item != 9) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.insertFront(8);
System.out.println(" Inserting 8 at front. List with 8 and 9 is " + l);
if (l.head.next.item != 8) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 9) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.head.next.next != l.head.prev) {
System.out.println("l.head.next.next != l.head.prev.");
}
if (l.head.prev.prev != l.head.next) {
System.out.println("l.head.prev.prev != l.head.next.");
}
if (l.size != 2) {
System.out.println("size is wrong.");
}
l = new DList2(1, 2);
System.out.println(" ### TESTING removeFront ### List with 1 and 2 is "
+ l);
l.removeFront();
System.out.println(" List with 2 is " + l);
if (l.head.next.item != 2) {
System.out.println("head.next.item is wrong.");
}
if (l.head.next.prev != l.head) {
System.out.println("head.next.prev is wrong.");
}
if (l.head.prev.item != 2) {
System.out.println("head.prev.item is wrong.");
}
if (l.head.prev.next != l.head) {
System.out.println("head.prev.next is wrong.");
}
if (l.size != 1) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
l.removeFront();
System.out.println(" Empty list is " + l);
if (l.head.next != l.head) {
System.out.println("head.next is wrong.");
}
if (l.head.prev != l.head) {
System.out.println("head.prev is wrong.");
}
if (l.size != 0) {
System.out.println("size is wrong.");
}
}
}
Explanation / Answer
INSERT LIST CODE
/* Function insert element at beginning */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
REMOVE LIST CODE
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}