You are to implement a dynamic single Linked List structure. This List will be b
ID: 3765447 • Letter: Y
Question
You are to implement a dynamic single Linked List structure. This List will be based on the node definition given down below. Since you already know how to create classes, this should be a logical extenson. Your goal is to create a Linked List class which contains “node” elements. Your program should contain the ability to:
MAKE SURE TO HAVE A METHOD FOR EACH OF THE 7 THINGS BELOW
1.) A method InsertAtHead(): (new node at head)
2.) A method print(): (prints out the contents of the list in order)
3.) A method removeFromHead(): (remove first node) [watch empty case]
4.) A method removeFromTail(): (remove last node) [watch empty case, or 1 node case]
5.) A method findValue(): (an isThere routine) (tells you if the target is in the list)
6.) A method that gives total # of occurrences of a specified value (how many items of target are in the list)
7.) A method that gives a total # of nodes (total items in list)
This program will track integers from the user. Be aware that some of these methods above will force you to create other routines/methods. You are coding dynamic structures – code accordingly.
Specifics:
1.) Start with the node class definitions first. Make sure they work before you move onto the Linked List class. Remember, when you designing this class, think about how it will be accessed by the Linked list class.
2.) The linked list class is a simple extension of the node class; essentially just a head pointer. Remember, when you design this class, think about how the main (driver) program will access this class, and how this class will access the node methods.
3.) Don’t duplicate work done by the node class in the linked list class! In many cases, the linked list could simply call the Node methods and pass data. Use common sense constructors and methods – include an empty case constructor as well as a 1 variable constructor.
4.) Class construction – my suggestion is to use something similar to the following:
public class Node { public class Linked_list {
private int data; private Node head;
private Node next; }
}
Things to think about:
1.) Remember that your program should be interactive - you don't have to use graphics, a txt window is fine. but you need to create a menu (basically a giant loop) that will wait for user input..so if the user want to "add" (menu item 1 for example), a method should be called to get the data from the user, then you simply send the data and call the linked list add method which you already put in the linked list class. "delete" (menu item 2 for example), would work similarly..
OK - so work bottom up - get your linked list class working smooth first, you can use a simple driver to slam data into in for testing, but the I/O should be interactive... OK, one last hint...consider the impact of the user trying to delete from an empty list.... where should it be handled? My hint - remember that the linked list class (if you already read your notes) can be "reused" later on for other ADTs.... so you really don't want I/O occurring in the lowest level right? i.e. you don't want your linked list methods to interface directly with the user - they should interface with your driver... the driver should handle I/O... everything is encapsulated so it can be reused... BUT, the linked list/node class should not allow this to happen.. if you don't catch it, and the user tries it, your program will crash..
2.) Once you start thinking about this class definition, you can see that a common method (not listed above) is needed – namely, a bool IsEmpty() . You do not ever want a “remove”, “print”, or even “IsThere” being called if the list is empty. Clearly, this simple method would be very useful and would likely be called by many other class methods.
3.)
- Build & test in steps !
- Think about the best place to put error checking ! Encapsulation is the key. Initialize your variables, especially adding NULL values to the pointers (don’t trust the system).
- Get used to the following loop routine – it is the basis for moving through the linked list.
for ( x = head; x != null; x = x.link)
Explanation / Answer
import java.util.Scanner;
class Node
{
protected int data;
protected Node link;
public Node()//* Constructor *//
{
link = null;
data = 0;
}
public Node(int d,Node n) //* Constructor *//
{
data = d;
link = n;
}
/* To arrange linke to next node */
public void setLink(Node n)
{
link = n;
}
/* to arrange data to current Node */
public void setData(int d)
{
data = d;
}
/* to get link to next node */
public Node getLink()
{
return link;
}
/* to get data from current Node */
public int getData()
{
return data;
}
}
/* Class or the linkedList */
class linkedList
{
protected Node head;
protected Node end ;
public int size ;
public linkedList()
{
head = null;
end = null;
size = 0;
}
/* to verify list is empty */
public boolean isEmpty()
{
return head == null;
}
/* to get size of list */
public int getSize()
{
return size;
}
/* to insert an element at begining */
public void insertAtHead(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(head == null)
{
head = nptr;
end = head;
}
else
{
nptr.setLink(head);
head = nptr;
}
}
/* to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(head == null)
{
head = nptr;
end = head;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr =head;
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++ ;
}
/* to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
head = head.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = head;
Node t = head;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = head;
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-- ;
}
//* to display elements *//
public void display()
{
System.out.print(" Singly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (head.getLink() == null)
{
System.out.println(head.getData() );
return;
}
Node ptr = head;
System.out.print(head.getData()+ "->");
ptr = head.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}
/* single linked list class */
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
linkedList list = new linkedList();
System.out.println("Singly Linked List Test ");
char ch;
/* list of operations */
do
{
System.out.println(" Singly Linked List Operations ");
System.out.println("1. insert at head");
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.insertAtHead( 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;
}
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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.