user6941415
user6941415

Reputation:

LinkedList getFirstElement and getLastElement Methods

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

Answers (3)

Arafe Zawad Sajid
Arafe Zawad Sajid

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

Edwin Miguel
Edwin Miguel

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

Shadov
Shadov

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

Related Questions