- 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 27 times
public class LListWithTail<T> implementsListInterface<T> { private Node firstNode; // Head reference tofirst node private Node lastNode; // Tail reference to lastnode private int numberOfEntries; // Number ofentries in list
public LListWithTail() { initializeDataFields(); } // end default constructor
@Override public void clear() { initializeDataFields(); } // end clear
@Override public void add(T newEntry) { Node newNode = newNode(newEntry);
if (isEmpty()) firstNode= newNode; else lastNode.setNextNode(newNode);
lastNode = newNode; numberOfEntries++; } // end add
@Override public void add(int givenPosition, T newEntry){ if ((givenPosition >= 1)&& (givenPosition <= numberOfEntries + 1)) { NodenewNode = new Node(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); } // endif numberOfEntries++; } else throw newIndexOutOfBoundsException("Illegal position given to addoperation."); } // end add
public void addAll(T[] items) {
for (int i = 0; i <items.length; i++) { NodenewNode = new Node(items); NodelastNode = getNodeAt(numberOfEntries); lastNode.setNextNode(newNode); // Make last node referencenew node numberOfEntries++; }
}
@Override public T remove(int givenPosition) { T result = null; // Returnvalue if ((givenPosition >= 1)&& (givenPosition <= numberOfEntries)) { //Assertion: !isEmpty() if(givenPosition == 1) // Case 1: Remove first entry { result = firstNode.getData(); // Saveentry to be removed 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 node was removed } // endif numberOfEntries--; } else throw newIndexOutOfBoundsException("Illegal position given to removeoperation.");
return result; // Returnremoved entry } // end remove
@Override public T replace(int givenPosition, T newEntry){ if ((givenPosition >= 1)&& (givenPosition <= numberOfEntries)) { assert!isEmpty();
NodedesiredNode = getNodeAt(givenPosition); ToriginalEntry = desiredNode.getData(); desiredNode.setData(newEntry); returnoriginalEntry; } else throw newIndexOutOfBoundsException("Illegal position given to replaceoperation."); } // end replace
@Override 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
@Override public T[] toArray() { // The cast is safe becausethe new array contains 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
@Override 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
@Override public int getLength() { return numberOfEntries; } // end getLength
@Override public boolean isEmpty() { boolean result;
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 toindicate an empty 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) { assertgivenPosition < numberOfEntries; //Traverse the chain to locate the desired node for (intcounter = 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 tonext node
private Node(TdataPortion) { data =dataPortion; next =null; } // end constructor
private Node(TdataPortion, Node nextNode) { data =dataPortion; next =nextNode; } // end constructor
private T getData(){ returndata; } // end getData
private void setData(TnewData) { data =newData; } // end setData
private Node getNextNode(){ returnnext; } // end getNextNode
private voidsetNextNode(Node nextNode) { next =nextNode; } // end setNextNode } // end Node
} // end LListWithTail
start of driver code below
- 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 2 (38.73 KiB) Viewed 27 times
public class Driver public static void main(String[] args) { testStringList(); System.out.println("\n\nDone."); } // end main public static void testStringList() { ListInterface myList = new LListWithTail<>();| } // end testStringList public static void displayList (ListInterface list) { System.out.println("The list contains " + list.getLength() + " string(s), as follows:"); Object[] listArray = list.toArray(); for (int index = 0; index < listArray.length; index++) { System.out.print(listArray[index] + "); } // end for System.out.println(); } // end displayList } // end Driver