Reputation:
I need to write a Java program (class LinkedList) that should do all the stuff without using import List and I have tried but I am not sure from if they are working or not.
Can someone please help me? Especially getFirstElement and getLastElement methods.
Here are my classes:
package main.java.a3;
public interface List<E> {
public void add(E e);
public void add(int index, E e);
public int size();
public E get(int index);
public boolean isEmpty();
}
package main.java.a3;
import java.util.NoSuchElementException;
public class LinkedList<E> implements List<E>{
private ListNode head;
@Override
public void add(E e) {
if(e == null){
throw new NullPointerException("Element was null");
}
if(head == null){
head = new ListNode(e,null);
}else{
ListNode temp = head;
while(temp.next!=null){
temp=temp.next;
}
temp.setNext(new ListNode(e,null));
}
}
@Override
public void add(int index, E e) {
if(e == null) {
throw new NullPointerException("Element was null!");
}
else if(index<0){
throw new IndexOutOfBoundsException("Index was negative");
}
else if(index>=size() + 1){
throw new IndexOutOfBoundsException("Index was bigger than size");
} else {
ListNode temp = head;
while(temp.next != null) {
temp = temp.next;
}
temp.setNext(new ListNode(e, null));
}
}
@Override
public int size() {
int size = 0;
ListNode temp = head;
while(temp != null) {
size++;
temp = temp.getNext();
}
return size;
}
@Override
public E get(int index) {
if(index<0){
throw new IndexOutOfBoundsException("Index was negative");
}
if(index>=size()){
throw new IndexOutOfBoundsException("Index was bigger than size");
}
ListNode temp = head;
for (int i = 0; i<index;i++){
temp = temp.next;
}
return temp.data;
}
@Override
public boolean isEmpty() {
if(head == null) {
return true;
} else {
return false;
}
}
// innere Klasse
private class ListNode{
E data;
ListNode next;
public ListNode(E data, ListNode next){
setData(data);
setNext(next);
}
public void setData(E data){
this.data = data;
}
public void setNext(ListNode next){
this.next = next;
}
public E getData() {
return data;
}
public ListNode getNext() {
return next;
}
}
// innere Klasse
public String toString() {
return head.toString();
}
public void addFirst(E elem) {
if(elem == null) {
throw new NullPointerException("Element was null!");
} else {
ListNode temp = new ListNode(elem, head);
if(head != null) {
temp.setNext(head);
}
head = temp;
}
}
public void addLast(E elem) {
if(elem == null) {
throw new NullPointerException("Element was null!");
} else {
ListNode tail = new ListNode(elem, null);
while(head != null) {
tail.getNext();
if(tail.getNext() == null) {
tail.setNext(head);
}
}
}
}
public E getFirst() {
if(head == null) {
throw new NoSuchElementException("Element was null!");
}else {
return (E) head;
}
}
public E getLast(){
E elem = null;
ListNode tail = new ListNode(elem, null);
if(tail == null) {
throw new NoSuchElementException("Element was null!");
}
return (E) tail;
}
}
Upvotes: 1
Views: 276
Reputation: 92
getFirstElement() and getLastElement()
/* supposing the elements in your link list are stored in a variable data of the Node class */
public E getFirst() {
if(head == null) {
throw new NoSuchElementException("Element was null!");
}else {
return (E) head.data;
}
}
public E getLast(){
if(head == null) {
throw new NoSuchElementException("Element was null!");
}
else{
for(Node iterate=head; iterate!=null; iterate=iterate.next){
return (E) iterate.data;
}
}
}
Upvotes: 0
Reputation: 409
There are two options, the iterative one and the constant-time option.
In the Iterative you have a head pointing to the first node, so getting first element is just to call the head.data(), but for the last element you must iterate with a while/for loop until currentNode.next()!=null
In the Constant-time option, you have two pointers, one for head, other for last element. For getting the first element it's the same than the iterative way, but for getting the last one, you must use the last pointer to return the value. The complex thing here is to have the control about adding/removing elements to update de last node.
A very basic example could be:
public class LinkedList<E> implements List<E>{
private ListNode<E> head;
private ListNode<E> last;
private int size;
public E getFirst(){
if(head!=null)
return head.data();
else
return null;
}
public E getIterativeLast(){
if(head!=null){
ListNode<E> last = head;
for(;last.next()!=null; last=last.next());
return last.data(());
}else{
return null;
}
}
public E getConstantLast(){
if(last != null){
return last.data();
}else{
return null;
}
}
public void add(E elem){
LastNode<E> newElem = new LastNode(elem);
if(head == null){
head = last = newElem;
}else{
last.setNext(newElem);
last = newElem:
}
size++;
}
}
"Graphically" could be like:
head ---> n1|->n2|->null
/
last ---------/
head ---> n1|->n2|->n3->null
/
last --------------/
Upvotes: 0
Reputation: 5566
In getFirst
you are casting head
element to E
and head
is of type ListNode
. You need to return head.data
, not head
itself. That is if you actually want the value, not the element, if you want the element then just return head
and change return type to ListNode
.
I don't understand your getLast
tho, you are making a new element, then checking if it's null (?) and then again casting it to E
when it's ListNode
. You need to iterate your whole list to get to the last element, and then return it, something like:
ListNode temp = head;
while(temp.next != null)
temp = temp.next;
return temp.data;
Then like I wrote before, you can return either element or the value. Ofcourse you need to take care of possible nullpointers, like head
being null etc., but you know that.
Upvotes: 0