# java help

• 04-24-2006, 06:10 PM
emasha
java help
Hi everyone! :WAVE:

I'm a beginner learner to Java (currently taking an introduction course) and I have a really tough professor. He's moving way too fast. I've been staying after school to get help for hours, but its all so time consuming.

Today he gave us 2 assignments:

1. A string is a palindrome if you obtain the same string when reading it backward. For example, "DAD", "ada", etc. are palindrome. But "abc" and "english" are not. Please use stack and queue to write a program which will check an inputted sting if it is a palindrome.

2. Describe a good algorithm for concatenating two singly linked list L and M, with header sentinels, into a single list L' (L prime) that contains all the nodes of L followed by all the nodes of M.
HINT: This concatenation operation need not search all of L and M.

I have to write a program for both of these assignments. Can someone help me get started?
• 04-24-2006, 07:07 PM
srekcus
Are you sure you're in a beginner's course? I didn't learn stacks, queues, or linked lists until my third semester.

Have you started the programs? What have you got done so far?
• 04-24-2006, 08:11 PM
emasha
I have no clue how to do the first assignment.
Last semester I took intro to CS and now I'm taking CS II, both of which are really introductory courses. It's my professor who decided to 'jump' ahead with learning more about java.

So far this is what I have for the second assignment:

import java.lang.*;
import java.util.*;

public static void main(String[] a){
SLinkedList s1 = new SLinkedList(); //sl containes no nodes at this moment
//how toadd new node into it.

System.out.println(""+sl);

}

}

class Node{
private String element;
private Node next;
public Node (String s, Node n) {
element = s;
next = n;

}

public String getElement(){
return element;

}

public Node getNext(){
return next;

}

public void setElement (String newElem){
element = newElem;

}

public void setNext(Node newNext){
next = newNext;

}

}

protected Node size;

size = 0;

}

size++;

}

void removeFirst(){
Node temp;
temp.setNext(null);
size--;

}

}

public String toString(){
String convertion = "";
for (int i=0; i<size; i++){
convertions += temp.getElement();
temp = temp.getNext();

}

return convertion;

}

}

When I run the program I keep getting an error. I'm having a problem with putting L and M into L'. :(
• 04-24-2006, 08:21 PM
nspils
It is best to have an idea of where you are going before you start your trip. Develop a map of how you plan to get there. This is your "algorithm".

So, what is your algorithm for attacking each problem?

As to the code you listed - what error messages are you seeing?
• 04-26-2006, 03:43 AM
graviton
your node class looks pretty good. i love it to see getters and setters for private members.

but the SLinkedList is not that proper.
bug: protected Node size;
this should be int not Node.

then your list has the followin methods:
void removeFirst()

that's not that pretty. you shouldn't operate on the first node. a list grows at the tail.
usually a list should have the following methods:
this will internally generate a node with the given value and attach it to the tail (end) of the linked list. to optimize you also can keep track of the tail of your list like you do with the head. so adding new values will increase in speed to O(1) instead of O(n).
-void remove(String value)
this will iterate through the list to find a node with the given value using equals to determine if two values are equal). if found, it will remove it properly by linking the previous node to the next one. also think of the size of the list to be corrected.
this will remove the first occurence of the value in the list (since lists can contain a value twice or more times). this method is not needed for your assignment.
-void remove(int i)
the same as get(i), but removing the node at the index.
-int size()
returns the amount of nodes in the list
-boolean isEmpty()
optional, since size() will be enough. but it's easy: return size()==0.
-String get(int i)
will return the value at position i, if i<size (since i starts at 0). to find the correct value, you will have to iterate through the list until you reach the given position.
-void clear()
this will remove all nodes from the list by just setting size=0 and head=null. then the nodes will be garbagecollected.

having done this class, it's really easy to append one list to another:
list a, list b // assume you have to filled lists
for (int i=0; i<b.size(); i++){
}
b.clear(); // only if you want b to be discarded

and the non plus ultra: you decided to use Strings as values.
lists usually are more general and thus use Object as their values.
• 04-26-2006, 03:55 AM
graviton
for the palindromes the easier way is using a stack. you will put the first half of the string as characters to the stack. then compare the secound half of the string with the (reversed order of the ) characters in the stack.
eg.:
abcba ->
1. 1st half=ab, c is discarded since it doesn't change the palindrome property
2. put it on the stack
push(char(0))
push(char(1))
3. the stack now contains b(top), a (bottom)
4. compare the second half (ba) with the stack:
char(3)==pop() (pop will give b)
char(4)==pop() (pop will give a)
5. if all chars from 2nd half and stack are equal, you have a palindrome
6. instead of iterating the second half by hand, use a queue for it:
push(char(3))
push(char(4))
7. the queue has now b (first), a (last)
8. compare stack with queue:
queue.pop()(pop will give b)==stack.pop() (pop will give b)
queue.pop()(pop will give a)==stack.pop() (pop will give a)
that's it.
• 04-26-2006, 03:41 PM
emasha
I have the palindrome assignment completed and running Thanks a lot graviton. :)

I'm currently working on the code above. Thanks all!