Write a program that maintains a list of items using a generic singly linked lis

Question

Write a program that maintains a list of items using a generic singly linked list as the backing store.

Specification

HERE IS THE CODE TO USE

public class SinglyLinkedList<E> {
   private int length; // # elements in the linked list
   private SLNode<E> head; // access point to the linked list
   private SLNode<E> tail;

   public SinglyLinkedList() {
       this.length = 0;
       this.tail = new SLNode<E>(); // the tail dummy node
       this.head = new SLNode<E>(null, this.tail); // the head dummy node
   }

   public int getLength() {
       return this.length;
   }

   public void add(E e) {
       SLNode<E> newnode = new SLNode<E>(e, null);
       newnode.setSuccessor(this.head.getSuccessor());
       this.head.setSuccessor(newnode);
       this.length++;
   }

   public void add(E e, int p) {
       // verify that index p is valid
       if ((p < 0) || (p > this.length)) {
           throw new IndexOutOfBoundsException("index " + p
                   + " is out of range: 0 to " + this.length);
       }
       SLNode<E> newnode = new SLNode<E>(e, null);
       SLNode<E> cursor = this.head;
       for (int i = 0; i < p; i++) {
           cursor = cursor.getSuccessor();
       }
       addAfter(cursor, newnode);
       this.length++;
   }

   public E remove(int p) {
       if ((p < 0) || (p >= this.length)) {
           throw new IndexOutOfBoundsException("index " + p
                   + " is out of range: 0 to " + (this.length - 1));
       }
       SLNode<E> cursor = head; // good for p == 0
       if (p > 0) {
           cursor = find(p - 1); // get target's predecessor
       }

       SLNode<E> target = cursor.getSuccessor(); // get the node to remove

       // link target to cursor's successor
       cursor.setSuccessor(target.getSuccessor());
       target.setSuccessor(null);
       this.length--;
       return target.getElement();
   }

   public E getElementAt(int p) {
       SLNode<E> node = this.find(p);
       return node.getElement();
   }

   private void addAfter(SLNode<E> p, SLNode<E> newnode) {
       newnode.setSuccessor(p.getSuccessor());
       p.setSuccessor(newnode);
   }

   private SLNode<E> find(E target) {
       SLNode<E> cursor = head.getSuccessor();

       while (cursor != tail) {
           if (cursor.getElement().equals(target)) {
               return cursor; // success
           } else {
               cursor = cursor.getSuccessor();
           }
       }
       return null; // failure
   }

   private SLNode<E> find(int p) {
       if ((p < 0) || (p >= this.length)) {
           throw new IndexOutOfBoundsException();
       }

       SLNode<E> cursor = head.getSuccessor();
       int i = 0;

       while (i != p) {
           cursor = cursor.getSuccessor();
           i++;
       }

       return cursor;
   }
}

public class SLNode<E> {
   private E element; // the data field
   private SLNode<E> successor; // the link to this node's successor

   public SLNode() {
       this.element = null;
       this.successor = null;
   }

   public SLNode(E theElement, SLNode<E> theSuccessor) {
       this.element = theElement;
       this.successor = theSuccessor;
   }

   public E getElement() {
       return this.element;
   }

   public void setElement(E newElement) {
       this.element = newElement;
   }

   public SLNode<E> getSuccessor() {
       return this.successor;
   }

   public void setSuccessor(SLNode<E> newSuccessor) {
       this.successor = newSuccessor;
   }
}

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');   
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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