import java.util.Scanner; public class SinglyLinkedList { public static void mai

ID: 3682279 • Letter: I

Question

import java.util.Scanner;
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
linkedList list = new linkedList();

   char ch;

do
{
   System.out.println(" 1. insert at begining");
System.out.println(" 2. insert at end");
   System.out.println(" 3. insert at position");
System.out.println(" 4. delete at position");
System.out.println(" 5. check empty");
System.out.println(" 6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println(" Enter integer :");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println(" Enter integer :");
list.insertAtEnd( scan.nextInt() );
break;
   case 3 :
System.out.println(" Enter integer :");
int num = scan.nextInt() ;
System.out.println(" Enter position :");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println(" Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println(" Enter position :");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println(" Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println(" Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println(" Size = "+ list.getSize() +" ");
break;
   default :
System.out.println(" Wrong Entry ");
break;
}
/* Display List */
list.display();
System.out.println(" Do you want to continue(y or n) ");
ch = scan.next().charAt(0);
}
while (ch == 'Y'|| ch == 'y');
}
}

------------------------

import java.util.Scanner;

public class Node
{
protected int data;
protected Node link;

public Node()
{
link = null;
data = 0;
}

public Node(int d,Node n)
{
data = d;
link = n;
}

public void setLink(Node n)
{
link = n;
}

public void setData(int d)
{
data = d;
}

public Node getLink()
{
return link;
}

public int getData()
{
return data;
}
}

---------------------

public class linkedList
{
private Node start;
private Node end ;
   int size ;

//Constructor
public linkedList()
{
start = null;
end = null;
size = 0;
}

public boolean isEmpty()
{
return start == null;
}

public int getSize()
   {
return size;
}

public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}

public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
   end.setLink(nptr);
end = nptr;
}
}

public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}

public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}

public void display()
{
System.out.print(" Singly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}

Edit your node class from last week to have the fields required for a doubly linked list. Edit your methods so that you can still insert and remove nodes Add a method to traverse the list backwards. In your main method, demonstrate that all of your original singly-linked-list methods still work and demonstrate that your new doubly-linked-list methods work.

Explanation / Answer

DoublyLinkedListTest.java

/*
* CHEGG Author
*/

import java.util.Scanner;

/* Class Node1 */
class Node1
{
protected int data;
protected Node1 next, prev;

/* Constructor */
public Node1()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node1(int d, Node1 n, Node1 p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next Node1 */
public void setLinkNext(Node1 n)
{
next = n;
}
/* Function to set link to previous Node1 */
public void setLinkPrev(Node1 p)
{
prev = p;
}
/* Funtion to get link to next Node1 */
public Node1 getLinkNext()
{
return next;
}
/* Function to get link to previous Node1 */
public Node1 getLinkPrev()
{
return prev;
}
/* Function to set data to Node1 */
public void setData(int d)
{
data = d;
}
/* Function to get data from Node1 */
public int getData()
{
return data;
}
}

/* Class linkedList */
class doublelinkedList
{
protected Node1 begin;
protected Node1 end ;
public int size;

/* Constructor */
public doublelinkedList()
{
begin = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return begin == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void insertAtbegin(int val)
{
Node1 nptr = new Node1(val, null, null);
if(begin == null)
{
begin = nptr;
end = begin;
}
else
{
begin.setLinkPrev(nptr);
nptr.setLinkNext(begin);
begin = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node1 nptr = new Node1(val, null, null);
if(begin == null)
{
begin = nptr;
end = begin;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node1 nptr = new Node1(val, null, null);
if (pos == 1)
{
insertAtbegin(val);
return;
}
Node1 ptr = begin;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node1 tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
/* Function to delete Node1 at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
begin = null;
end = null;
size = 0;
return;
}
begin = begin.getLinkNext();
begin.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node1 ptr = begin.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node1 p = ptr.getLinkPrev();
Node1 n = ptr.getLinkNext();

p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
/* Function to display status of list */
public int display()
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return 0;
}
if (begin.getLinkNext() == null)
{
System.out.println(begin.getData() );
return begin.getData();
}
Node1 ptr = begin;
System.out.print(begin.getData()+ " <-> ");
ptr = begin.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " ");
return begin.getData();
}
}

/* Class DoublyLinkedListTest */
public class DoublyLinkedListTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
doublelinkedList dll = new doublelinkedList();
System.out.println("Doubly Linked List operations ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Doubly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
System.out.println("7. Display");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
dll.insertAtbegin( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
dll.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > dll.getSize() )
System.out.println("Invalid position ");
else
dll.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int position = scan.nextInt() ;
if (position < 1 || position > dll.getSize() )
System.out.println("Invalid position ");
else
dll.deleteAtPos(position);
break;
case 5 :
System.out.println("Empty status of DLL = "+ dll.isEmpty());
break;
case 6 :
System.out.println("Size of DubleLinkedList = "+ dll.getSize() +" ");
break;
case 7:
System.out.println("Display elements : "+ dll.display());
break;
default :
System.out.println("Please enter correct choiceWrong Entry ");
break;
}
/* Display List */
dll.display();
System.out.println(" If you want to continue (Type S or S) or press any key to exit ");
ch = scan.next().charAt(0);

} while (ch == 'S'|| ch == 's');
}
}

output

run:
Doubly Linked List operations

Doubly Linked List Operations

1. insert at begining
2. insert at end
3. insert at position
4. delete at position
5. check empty
6. get size
7. Display
1
Enter integer element to insert
1

Doubly Linked List = 1