(1) Implement the countKey(T element) method, which should return a count of the number of times that the given key (the element) is found in the list.
(2) Implement the indexOf(T element) method, which is similar as the indexOf method in the String class. It returns the index (the position starting from the head node) of the first occurrence of the given element, or -1, if the element does not occur in the list. You will need to track the index as you traverse the linked list.
(3) Implement the printList() method simply prints the contents of the list to the terminal. For example, if the list is empty, it should print [ ], and if the list contains the elements 1, 2, 3, then it should print [1 -> 2 -> 3].
4) Implement the moveLastToFirst() method, which moves the last element to the front of the list. For example, if the list is 1->2->3->4, then the method should change the list to 4->1->2->3. There is a tail attribute in the given LinkedList class which point to the last node in the list. Dont forget to change the previous node of the tail node as the new tail node.
Java Code:
LinkedList.java
package lab1; /** * LinkedList represents a linked implementation of a list. public class LinkedList { protected int count; protected LinearNode head, tail; /** * Creates an empty list. */ public LinkedList() { count = 0; head = tail = null; } /** * Add the element to the front in this list * * @param elem the element that needs to be added to the front in the list */ public void addToFirst(T elem) { LinearNode newNode = new LinearNode(elem); if(isEmpty()) { head = newNode; tail = newNode; } else { newNode.setNext(head); head = newNode; newNode = null; } count++; } /** * Add the element to the back in this list * * @param elem the element that needs to be added to the back in the list */ public void addToLast(T elem) { LinearNode newNode = new LinearNode(elem); if(isEmpty()) { head = newNode; tail = newNode; } else { tail.setNext(newNode); tail = newNode; newNode = null; } count++; } /** * Removes the first element in this list and returns a reference * to it. Throws an EmptyCollectionException if the list is empty. * * @return a reference to the first element of this list * @throws EmptyCollectionException if the list is empty */ public T removeFirst() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("LinkedList"); T result = head.getElement(); head = head.getNext(); count--; return result; } /** * Removes the last element in this list and returns a reference * to it. Throws an EmptyCollectionException if the list is empty. * * @return the last element in this list * @throws EmptyCollectionException if the list is empty */ public T removeLast() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("LinkedList");
T result = tail.getElement(); LinearNode current = head; while(current.getNext() != tail) current = current.getNext(); current.setNext(null); tail = current; count--; return result; } /** * Returns the first element in this list without removing it. * * @return the first element in this list * @throws EmptyCollectionException if the list is empty */ public T first() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("LinkedList"); return head.getElement(); } /** * Returns the last element in this list without removing it. * * @return the last element in this list * @throws EmptyCollectionException if the list is empty */ public T last() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("LinkedList"); return tail.getElement(); } public LinearNode findFirstKey(T element){ if (isEmpty()) throw new EmptyCollectionException("LinkedList"); LinearNode current = head; while(current != null && current.getElement() != element) { current = current.getNext(); } return current; } public void deleteNode(T element) { if (isEmpty()) throw new EmptyCollectionException("LinkedList"); LinearNode current = head, prev = null; // If head node holds the key to be deleted if(current != null && current.getElement() == element) { head = current.getNext(); current.setNext(null); return; } //Search for the key to be deleted, track the previous node while(current != null && current.getElement() != element) { prev = current; current = current.getNext(); } //If key was not present in the list if(current == null) return; prev.setNext(current.getNext()); current.setNext(null); } /** * Returns true if this list is empty and false otherwise. * * @return true if the list is empty, false otherwise */ public boolean isEmpty() { return (count == 0); }
/** * Returns the number of elements in this list. * * @return the number of elements in the list */ public int size() { return count; }
/** * Returns a string representation of this list. * * @return a string representation of the list */ public String toString() { LinearNode current = head; String result = "";
while (current != null) { result = result + current.getElement() + " "; current = current.getNext(); }
return result; } /*Question 1*/ public int countKey(T element) { if (isEmpty()) throw new EmptyCollectionException("LinkedList is empty");
int counter = 0; /* write your code here */ return counter; } /* Question 2 */ public int indexOf(T element) { if (isEmpty()) throw new EmptyCollectionException("LinkedList is empty"); /* write your code here */ return -1; } /* Question 3 */ public void printList() { /* write your code here*/ } /* Question 4 */ public void movelastToFirst() { if (isEmpty()) throw new EmptyCollectionException("LinkedList is empty");
/* write your code here*/ } }