hi i have to write a java program involving link lists. i have a problem with th

Question

hi i have to write a java program involving link lists. i have a problem with the nodes, as it is posting errors with the nodes.

please help me with this problem. thank you.

public class LinkLists<T> {
/* only need to store a single pointer to the node at the head
* of the list.
* The pointer is null if the list is empty.
* Also record the size of the list.
*/
protected Node<T> head;
/* invariant: size is the number of nodes in the list pointed to by head */
protected int size;

/* no-arguments default constructor creates an empty list */
public LinkLists() {
head = null; // start with an empty list
size = 0;
}

/* accessor method */
public int size() {
return size;
}

/* value to add to the end of the list
*/
public void add(T value) {
head = addAtEnd(head, value);
size++;
}

/* node of the list to which the value should be added
* value to add to the end of the list
*/
private Node<T> addAtEnd(Node<T> node, T value) {
if (node == null) { // special case
return new Node<T>(value, null);
} else if (node.getNext() == null) { // other special case
node.setNext(new Node<T>(value, null));
} else {
addAtEnd(node.getNext(), value);
}
return node;
}

/* iterative implementation of the same method
* value to add to the end of the list
*/
public void add2(T value) {
if (head == null) {
head = new Node<T>(value, null);
} else {
Node<T> node = head; // guaranteed not to be null initially
while (node.getNext() != null) {
node = node.getNext(); // guaranteed not to be null here
}
// now, node.getNext() is guaranteed to be null
// similar to the second special case in addAtEnd
node.setNext(new Node<T>(value, null));
}
size++;
}

  
public void remove(int position) throws BadItemCountException {
if ((position < 1) || (position > size)) {
throw new
BadItemCountException("invalid position " + position +
", only 1.." + size + " available");
}
if (position == 1) {
head = head.getNext();
} else {
Node<T> node = head;
for (int i = 2; i < position; i++) {
node = node.getNext();
}
node.setNext(node.getNext().getNext());
}
size--; // one less item
}

public String toString() {
return toString(head);
}
private String toString(Node<T> node) {
if (node == null) {
return "";
} else {
return node.getValue() + " " + toString(node.getNext());
}
}

public static void main(String[] args) {
/* create two empty lists, make sure they print out correctly */
LinkLists<String> list1 = new LinkLists<String>();
LinkLists<String> list2 = new LinkLists<String>();
System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
System.out.println("list1.size() = " + list1.size() +
", list2.size() = " + list2.size());

/* insert some items, keep checking */
list1.add("hello");
list1.add("world");
list2.add("foo");
list2.add("bar");
list2.add("baz");
System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
System.out.println("list1.size() = " + list1.size() +
", list2.size() = " + list2.size());

/* remove an item at an invalid position */
boolean caught = false;
try {
list2.remove(4);
} catch (BadItemCountException e) {
caught = true;
}
if (! caught) {
System.out.println("error: no exception for invalid remove");
System.out.println("list1 = '" + list1 +
"', list2 = '" + list2 + "'");
}
System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");

/* remove some items at valid positions */
try {
list1.remove(1);
System.out.println("list1 = '" + list1 +
"', list2 = '" + list2 + "'");
list2.remove(2);
System.out.println("list1 = '" + list1 +
"', list2 = '" + list2 + "'");
list2.remove(2);
System.out.println("list1 = '" + list1 +
"', list2 = '" + list2 + "'");
} catch (Exception e) {
System.out.println("caught unexpected exception " + e +
", list1 = '" + list1 + ", list2 = " + list2);
}
System.out.println("list1.size() = " + list1.size() +
", list2.size() = " + list2.size());
}
}
class BadItemCountException extends Exception {
/* @param   error, describes the reason the exception is being thrown
*/
BadItemCountException(String error) {
   super(error);
}
}

Explanation / Answer

/*
* Java Program to Implement Singly Linked List
*/

import java.util.Scanner;

/* Class Node */
class Node
{
protected int data;
protected Node link;

/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}

/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size ;

/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
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;
}
}
/* Function to insert an element at end */
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;
}
}
/* Function to insert an element at position */
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++ ;
}
/* Function to delete an element at position */
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-- ;
}
/* Function to display elements */
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()+ " ");
}
}

/* Class SinglyLinkedList */
public class SinglyLinkedList
{
public static void main(String[] args)
{   
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
linkedList list = new linkedList();
System.out.println("Singly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Singly 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");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );   
break;
case 2 :
System.out.println("Enter integer element to insert");
list.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 > 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 (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');   
}
}

output:

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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