This program let user to input a series of integer type inputs and they are stored in a Linked List based data structure. And there are several number of operations that user can use to access, maintain and manipulate the data in this data structure. Actually this data structure is a two dimensional Linked List. That means in this data structure we are using a Linked List in a Linked List concept. There are many horizontal Linked Lists which are stored in a one main vertical Linked List. Because of that the user can store any number of inputs in this data structure.
We can use an array as the main vertical Linked List. But it
reduces the efficiency of the data structure. Using a Linked List in a Linked
List concept we can store any number of data items because this data structure
can be grow in both vertically and horizontally.
In this program first of all let user to input a series of
integers and user can decide the place where they should be stored in this data
structure. Then it provides seven main command that user can use to maintain
those data. They are,
- Print - Prints a full structure of given data structure. We can use this command to find how those inputs are stored in the data structure.
- Size - This command gives the number of data items in this data structure.
- Insert - User can insert a given number to any sub list. Have to provide the index of the place that he wishes to insert the number. {Main Index, Sub Index}
- Delete - User can delete a given number from any sub list. Have to provide the index of the place of the number that he wishes to remove from the list. {Main Index, Sub Index}
- Search - Searching a particular number on the data structure and returns the Index of that number where it found in first.
- Delete List - Delete a particular linked list on this data structure.
- Insert List - Insert a particular linked list to this data structure.
The building box of this program is linked list. What is a
linked list? Linked List is a very
common way of storing arrays of data. The major benefit of linked list is that
you do not specify a fixed size for your list. The more elements you add to the
chain, the bigger the chain gets.
When I designing this program first of
all I have create a one Linked List. Then I stored that type of linked lists in
a one main list. Following diagram will help you to understand the main
attitudes of a linked list.
In
my basic linked list there are three classes. They are Node, List and Main.
This is the implementation of my basic linked list.
Implementation
of the Basic Linked List
Class
Node
package
linkedlists;
class Node {
int value;
Node next;
public
Node(){//constructor for a head
value=0;
next=null;
}
public
Node(int x){ //constructor for a normal node
value=x;
next=null;
}
}
Class
List
package
linkedlists;
class List {
Node
head;
public
List(){
head=null;
}
public
boolean isEmpty(){
return
head==null;
}
public
void delete(int index){
Node
curr=head;
Node
prev=null;
if(index>size()||index<1||isEmpty()==true){
if(isEmpty()==true){
System.out.println("Empty
list…");
}
else{
System.out.println("Index
should between 1 and list size.");
}
}
else
if(index==1){
deleteHead();//delete
index 1 = delete head
}
else{
for(int
x=1;x<index;x++){
prev=curr;
curr=curr.next;
}
prev.next=curr.next;
}
}
public
void insert(int index,int value){
Node
newPtr=new Node(value);
Node
curr=head;
Node
prev=null;
if(index>size()+1||index<1){//can insert
to index size()+1 means insert value to end
System.out.println("Index
should between 1 and list size.");
}
else
if(index==1){
insertHead(value);//insert
index 1 = insert head
}
else{
for(int x=1;x<index;x++){
prev=curr;
curr=curr.next;
}
newPtr.next=curr;
prev.next=newPtr;
}
}
public
void makeEmpty() {
head= null;
System.out.println("Empty
List....");
}
public
int size(){
int listSize=0;
Node
a=head;
while(a!=null){
a=a.next;
listSize++;
}
return listSize;
}
public void insertHead(int x){
Node
NewLink=new Node(x);
if(head==null){
head=NewLink;
}
else{
NewLink.next=head;
head=NewLink;
}
}
public
void deleteHead(){
if(head==null){
System.out.println("Empty
List....");
}
else
{
head=head.next;
}
}
public
void search(int y){
Node
curr=head;
int index=0;
boolean
isFound = false;
while(curr!=null){
index+=1;
if(curr.value==y){
isFound=true;
System.out.println(y+"
Found in index "+index);
curr=null;
}
else{
curr=curr.next;
}
}
if(isFound==false){
System.out.println("Not
Found...");
}
}
public
void printNode(){
if(head==null){
System.out.print("Empty
List....");
}
for(Node
a=head; a!=null; a=a.next){
System.out.print("
"+a.value);
}
}
}
Class
Main
package
linkedlists;
import
java.util.Scanner;
public class
Main {
public static void main(String[] args) {
List
newList=new List();
Scanner
scan = new Scanner(System.in);
Scanner
cmd = new Scanner(System.in);
int key=0;
System.out.println("Please
input your integer type input series. After input enter any letter.");
while
(scan.hasNextInt()) {
newList.insertHead(scan.nextInt());
}
do{
System.out.println("1.Print");
System.out.println("2.Size");
System.out.println("3.Insert");
System.out.println("4.Delete");
System.out.println("5.Search");
System.out.println("6.Emptey
list");
System.out.println("7.Exit");
System.out.println("Please
enter your command.");
try{
key=cmd.nextInt();//nextInt() throws exception
}catch(Exception Ex){
System.out.println("Please
input an integer.");
key=0;
cmd = new Scanner(System.in);//creat new scanner
object
}
switch (key) {
case
1://print
newList.printNode();
break;
case
2://get size
System.out.println("Size is
"+newList.size());
break;
case
3://insert
Scanner insertIndexInt = new
Scanner(System.in);
Scanner
insertValInt = new Scanner(System.in);
try{
System.out.println("Index
for insert : ");
int a=insertIndexInt.nextInt();
System.out.println("Value
for insert : ");
int
b=insertValInt.nextInt();
newList.insert(a,
b);
}catch(Exception ExInsertIndex){
System.out.println("Please
input an integer.");
}
break;
case
4://delete
System.out.println("Index for
delete : ");
Scanner deleteInt = new
Scanner(System.in);
try{
int y=deleteInt.nextInt();
newList.delete(y);
}catch(Exception ExDelete){
System.out.println("Please
input an integer.");
}
break;
case
5://search
System.out.println("Integer for
search : ");
Scanner searchInt = new Scanner(System.in);
try{
int x=searchInt.nextInt();
newList.search(x);
}catch(Exception
ExSearch){
System.out.println("Please
input an integer.");
}
break;
case 6://empty list
newList.makeEmpty();
break;
case
7://exit
System.out.println("END");
break;
default:
System.out.println("Please input
a integer between 1 - 7. ");
break;
}
}while(key!=7)
}
}
After the implementation
of the basic linked list, I have tried to store a linked list in another linked
list. To that I have to insert a List type variable to my class Node. Also I
have added a special constructor to construct that type of Nodes. Each node in
my vertical linked list contains a horizontal linked list.
No comments:
Post a Comment