You are to implement a dynamic single Linked List structure. This List will be b

Question

You are to implement a dynamic single Linked List structure. This List will be based on the node definition given on the next page. Since you already know how to create classes, this should be a logical extension. Your goal is to create a Linked List class which contains %u201Cnode%u201D elements. Your program should contain the ability to:

1. Insert at head (new node at head)

2. Print (prints out the contents of the list in order)

3. Remove from head (remove first node) [watch empty case]

4. Remove from tail (remove last node) [watch empty case, or 1 node case]

5. Find a target value (an isThere routine) (tells you if the target is in the list)

6. Give total # of occurrences of a specified value (how many items of target are in the list)

7. Give 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 %u2013 code accordingly. See page 2 for more specificity on the methods.

Explanation / Answer

package demo;

import java.io.IOException;

public class LinkedList {

public static void main(String args[])throws IOException{

LinkedList l = new LinkedList(20);

printList(l);

LinkedList m = insertAtHead(l, 25);

printList(m);

LinkedList n = m.removeFirstNode();

printList(n);

m = n.removeFirstNode();

printList(m);

m = insertAtHead(m, 40);

printList(m);

m = insertAtHead(m, 50);

m = insertAtHead(m, 50);

printList(m);

System.out.println(getTargetValue(m, 40));

System.out.println(getNumberofNodes(m));

System.out.println(getNumberofOccurences(m, 50));

m = removeLastNode(m);

printList(m);

m = removeLastNode(m);

printList(m);

}

int value;

LinkedList next;

public LinkedList(int v, LinkedList n){

this.value = v;

this.next = n;

}

public LinkedList(int v){

this.value = v;

this.next = null;

}

public static LinkedList insertAtHead(LinkedList list, int v){

if(list==null){

return new LinkedList(v);

}

LinkedList head = new LinkedList(v, list);

return head;

}

public static void printList(LinkedList list){

while(list != null){

System.out.print(list.value+" -> ");

list = list.next;

}

System.out.print("NULL ");

}

public LinkedList removeFirstNode(){

if(this == null)

return null;

LinkedList nextHead = this;

nextHead = nextHead.next;

return nextHead;

}

public static LinkedList removeLastNode(LinkedList list){

if(list == null || getNumberofNodes(list)==1)

return null;

LinkedList prevHead = new LinkedList(list.value);

list = list.next;

LinkedList temp;

while(list.next != null){

temp = new LinkedList(list.value);

prevHead.next = temp;

list = list.next;

}

return prevHead;

}

public static boolean getTargetValue(LinkedList list, int value){

boolean isThere = false;

if(list == null)

return isThere;

while(list != null){

if(list.value == value)

isThere = true;

list = list.next;

}

return isThere;

}

public static int getNumberofOccurences(LinkedList list, int value){

int count = 0;

if(list == null)

return count;

while(list != null){

if(list.value == value)

count++;

list = list.next;

}

return count;

}

public static int getNumberofNodes(LinkedList list){

int count = 0;

if(list==null)

return count;

while(list != null){

count++;

list = list.next;

}

return count;

}

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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