- Suppose That You Want An Operation For The Adt List That Adds An Array Of Items To The End Of The List The Header Of Th 1 (30.34 KiB) Viewed 38 times
public class LListWithTail<T> implementsListInterface<T>{ private Node firstNode; //Head reference to first node private Node lastNode; // Tail reference to last node private int numberOfEntries; // Number ofentries in list
public LListWithTail() { initializeDataFields(); } // end default constructor
public void clear() { initializeDataFields(); } // end clear public void add(T newEntry) { Node newNode = new Node(newEntry); if (isEmpty()) firstNode = newNode; else lastNode.setNextNode(newNode); lastNode = newNode; numberOfEntries++; } // end add
public void add(int givenPosition, TnewEntry) { if ((givenPosition >= 1) &&(givenPosition <= numberOfEntries + 1)) { Node newNode = newNode(newEntry); if (isEmpty()) { firstNode =newNode; lastNode = newNode; } else if (givenPosition ==1) { newNode.setNextNode(firstNode); firstNode =newNode; } else if (givenPosition ==numberOfEntries + 1) { lastNode.setNextNode(newNode); lastNode = newNode; } else { Node nodeBefore =getNodeAt(givenPosition - 1); Node nodeAfter =nodeBefore.getNextNode(); newNode.setNextNode(nodeAfter); nodeBefore.setNextNode(newNode); } // end if numberOfEntries++; } else throw newIndexOutOfBoundsException( "Illegal position given to addoperation."); } // end add public T remove(int givenPosition) { T result = null; //Return value if ((givenPosition >= 1) &&(givenPosition <= numberOfEntries)) { // Assertion: !isEmpty() if (givenPosition == 1) // Case 1: Removefirst entry { result =firstNode.getData(); // Save entry to beremoved firstNode =firstNode.getNextNode(); if (numberOfEntries ==1) lastNode =null; // Solitary entry was removed } else // Case 2: Not first entry { Node nodeBefore =getNodeAt(givenPosition - 1); Node nodeToRemove =nodeBefore.getNextNode(); Node nodeAfter =nodeToRemove.getNextNode(); nodeBefore.setNextNode(nodeAfter); result =nodeToRemove.getData(); if (givenPosition ==numberOfEntries) lastNode =nodeBefore; // Last nodewas removed } // end if numberOfEntries--; } else throw newIndexOutOfBoundsException( "Illegal position given to removeoperation."); return result; // Return removed entry } // end remove
public T replace(int givenPosition, TnewEntry) { if ((givenPosition >= 1) &&(givenPosition <= numberOfEntries)) { assert !isEmpty();
NodedesiredNode = getNodeAt(givenPosition); T originalEntry =desiredNode.getData(); desiredNode.setData(newEntry); return originalEntry; } else throw newIndexOutOfBoundsException("Illegal position given to replaceoperation."); } // end replace
public T getEntry(int givenPosition) { if ((givenPosition >= 1)&& (givenPosition <= numberOfEntries)) { assert!isEmpty(); returngetNodeAt(givenPosition).getData(); } else throw newIndexOutOfBoundsException("Illegal position given to getEntryoperation."); } // end getEntry
public T[] toArray() { // The cast is safe because the new arraycontains null entries @SuppressWarnings("unchecked") T[] result = (T[])newObject[numberOfEntries]; int index = 0; Node currentNode = firstNode; while ((index < numberOfEntries) &&(currentNode != null)) { result[index] =currentNode.getData(); currentNode =currentNode.getNextNode(); index++; } // end while return result; } // end toArray public boolean contains(T anEntry) { boolean found = false; Node currentNode =firstNode; while (!found &&(currentNode != null)) { if(anEntry.equals(currentNode.getData())) found = true; else currentNode =currentNode.getNextNode(); } // end while return found; } // end contains
public int getLength() { return numberOfEntries; } // end getLength
public boolean isEmpty() { booleanresult; if (numberOfEntries == 0)// Or getLength() == 0 { assert(firstNode == null) && (lastNode == null); result =true; } else { assert(firstNode != null) && (lastNode != null); result =false; } // end if return result; } // end isEmpty // Initializes the class's data fields to indicate anempty list. private void initializeDataFields() { firstNode = null; lastNode = null; numberOfEntries = 0; } // end initializeDataFields // Returns a reference to the node at a givenposition. // Precondition: List is not empty; 1 <=givenPosition <= numberOfEntries. private Node getNodeAt(int givenPosition) { assert (firstNode != null)&& (1 <= givenPosition) && (givenPosition <=numberOfEntries); Node currentNode =firstNode; if (givenPosition == numberOfEntries) currentNode = lastNode; else if (givenPosition >1) { assert givenPosition <numberOfEntries; // Traverse the chain to locatethe desired node for (int counter = 1; counter< givenPosition; counter++) currentNode =currentNode.getNextNode(); } // end if assert currentNode !=null; return currentNode; } // end getNodeAt
private class Node { private T data; // Entry inlist private Node next; // Link to next node private Node(T dataPortion) { data = dataPortion; next = null; } // end constructor private Node(T dataPortion, NodenextNode) { data = dataPortion; next = nextNode; } // end constructor private T getData() { return data; } // end getData private void setData(T newData) { data = newData; } // end setData private Node getNextNode() { return next; } // end getNextNode private void setNextNode(Node nextNode) { next = nextNode; } // end setNextNode } // end Node} // end LListWithTail
Suppose that you want an operation for the ADT list that adds an array of items to the end of the list. The header of the method could be as follows: public void addAll(T[] items) Write an implementation of this method for the class LList.