LinkedLists

Question 1

Start

Answer 1

public class MyLinkedList<E> {
private Node<E> head,tail;</E></E>

public MyLinkedList(){
    head = null;
    tail = null;
}

Question 2

Node static class

Answer 2

private static class Node<E>{
E element;
Node<E> next;</E></E>

    public Node(E element){
        this.element = element;
        next = null;
    }
}

Question 3

append

Answer 3

public void append(E item){

    Node<E> newNode = new Node<E>(item);
    if(head == null){
        head = tail = newNode;
    }

    else {
        tail.next = newNode;
        tail = newNode;
    }
}

Question 4

toString

Answer 4

public String toString(){
String result = “[ “;

    Node<E> ptr = head;
    for(ptr=head;ptr!=null;ptr=ptr.next){
        result += ptr.element.toString();
        if(ptr.next!=null){
            result += ", ";
        }
        else {
            result += " ]";
        }
    }
    return result;
}

Question 5

getFirst

Answer 5

public E getFirst(){
if(head == null){
return null;
}

    else {
        return head.element;
    }
}

Question 6

getLast

Answer 6

public E getLast(){
if(tail == null){
return null;
}
else {
return tail.element;
}
}

Question 7

removeFirst

Answer 7

public E removeFirst(){
if(head == null){
return null;
}
else {
E temp = head.element;
head = head.next;

        if(head == null){
            tail =null;
        }
        return temp;
    }
    
}

Question 8

prepend

Answer 8

public void prepend(E object){
Node<E> newNode = new Node<E>(object);
newNode.next = head;
head = newNode;</E></E>

    if (tail==null){
        tail = head;
    }
}

Question 9

delete

Answer 9

public boolean delete(E item){
Node<E> ptr = head;
Node<E> prvPtr = null;</E></E>

    while(ptr!=null && ((Comparable)ptr.element).compareTo(item)!=0){ //traverses the linked list
        prvPtr = ptr;
        ptr = ptr.next;
    }

    if(ptr == null){
        return false; //element is not in the list
    }

    if(ptr==head){
        head = head.next; //item is the first element
    }
    else {
        //general case
        prvPtr.next = ptr.next;
    }
    if(ptr == tail){
        tail = prvPtr; //its the last element
    }
    return true;
}

Question 10

Merge List

Answer 10

public MyLinkedList<E> MergeList(MyLinkedList<E> param){
Node<E> ptrThis,ptrParam;
ptrThis = head;
ptrParam = param.head;</E></E></E>

    MyLinkedList returnList = new MyLinkedList<E>();

    if(head == null){
        while(ptrParam!=null){
            returnList.append(ptrParam.element);
            ptrParam = ptrParam.next;
        }
        return returnList;
    }

    if(param.head == null){
        while(ptrThis != null){
            returnList.append(ptrThis.element);
            ptrThis = ptrThis.next;
        }
        return returnList;
    }

    while(ptrThis != null && ptrParam != null){
        if (((Comparable)ptrThis.element).compareTo(ptrParam.element)<=0){
            returnList.append(ptrThis.element);
            ptrThis = ptrThis.next;
        }
        else {
            returnList.append(ptrParam.element);
            ptrParam = ptrParam.next;
        }
    }

    if(ptrThis == null){
        while(ptrParam!=null){
            returnList.append(ptrParam.element);
            ptrParam = ptrParam.next;
        }
    }//copy rest into the linkedlist list

    if(ptrParam == null){
        while(ptrThis!=null){
            returnList.append(ptrThis.element);
            ptrThis = ptrThis.next;
        }
    }//copy rest into the linkedlist list
    return returnList;
}

Question 11

linked list characteristics

Answer 11

Data elements are stored in fragmented
memory positions.

EACH ITEM NEEDS TO CONTAIN
INFORMATION on the memory position of
the next item!

The programmer needs to know where the
first NODE is – it also helps to know the
address of the last one.

Each NODE consists of:
1. data element
2. the address of the following node.

Question 12

Aspects of theory

Answer 12

The LinkedList<E> class is an outer class – we call it a container. Like a
bucket!
* It has two typical instance variables: head and tail
* It also contains objects of the inner class Node<E>.
* The inner class Node<E> has also 2 instance variables:
* element which holds the data of the node (see complete diagram)
* next which holds the address of the next node in the list</E></E></E>