Course content

[code] KWLinkedList.java

/**
///////////////////////////////////////////
Prepared by: OL Academy
Whatsapp: 66939059
Instagram: olearninga
Website: www.olearninga.com
Last Update: 10 NOV 2023
///////////////////////////////////////////
*/

import java.util.AbstractSequentialList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;


public class KWLinkedList<E> extends AbstractSequentialList<E> {
// Data Fields

private Node<E> head = null;
/**
* A reference to the end of the list.
*/
private Node<E> tail = null;
/**
* The size of the list.
*/
private int size = 0;

/**
* Insert an object at the beginning of the list.
*
* @param item - the item to be added
*/
public void addFirst(E item) {
Node<E> newNode = new Node(item);
if (head == null)
head = tail = newNode;
else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}

/**
* Insert an object at the end of the list.
*
* @param item - the item to be added
*/
public void addLast(E item) {
Node<E> newNode = new Node(item);
if (head == null)
head = tail = newNode;

else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
size++;
}

/**
* Get the first element in the list.
*
* @return The first element in the list.
*/
public E getFirst() {
if (head == null)
throw new NoSuchElementException();
return head.data;
}

/**
* Get the last element in the list.
*
* @return The last element in the list.
*/
public E getLast() {
if (head == null)
throw new NoSuchElementException();
return tail.data;
}


/**
* Return an Iterator to the list
*
* @return an Itertor to the list
*/
public Iterator<E> iterator() {
KWListIter iterator = new KWListIter(0);
return iterator;
}

/**
* Return a ListIterator to the list
*
* @return a ListItertor to the list
*/
public ListIterator<E> listIterator() {
KWListIter iterator = new KWListIter(0);
return iterator;
}

/**
* Return a ListIterator that begins at index
*
* @param index - The position the iteration is to begin
* @return a ListIterator that begins at index
*/
public ListIterator<E> listIterator(int index) {
KWListIter iterator = new KWListIter(index);
return iterator;
}

/**
* Return a ListIterator that begins at the same
* place as an existing ListIterator
*
* @param iter - The other ListIterator
* @return a ListIterator that is a copy of iter
*/
public ListIterator<E> listIterator(ListIterator<E> iter) {
KWListIter iterator = new KWListIter((KWListIter) iter);
return iterator;
}

/**
* Add an item at the specified index.
*
* @param index The index at which the object is to be
* inserted
* @param obj The object to be inserted
* @throws IndexOutOfBoundsException if the index is out
* of range (i < 0 || i > size())
*/
@Override
public void add(int index, E obj) {
listIterator(index).add(obj);
}

/**
* Get the element at position index.
*
* @param index Position of item to be retrieved
* @return The item at index
*/
@Override
public E get(int index) {
return listIterator(index).next();
}

/**
* Return the size of the list
*
* @return the size of the list
*/
@Override
public int size() {
return size;
}

// Inner Classes

/**
* A Node is the building block for a double-linked list.
*/
private static class Node<E> {

/**
* The data value.
*/
public E data;
/**
* The link to the next node.
*/
public Node<E> next = null;
/**
* The link to the previous node.
*/
public Node<E> prev = null;

/**
* Construct a node with the given data value.
*
* @param dataItem The data value
*/
private Node(E dataItem) {
data = dataItem;
}

public String getData() {
if (data == null)
return "null";
else
return (String) data;
}
} //end class Node

/**
* Inner class to implement the ListIterator interface.
*/
private class KWListIter implements ListIterator<E> {

/**
* A reference to the next item.
*/
private Node<E> nextItem;
/**
* A reference to the last item returned.
*/
private Node<E> lastItemReturned;
/**
* The index of the current item.
*/
private int index = 0;

/**
* Construct a KWListIter that will reference the ith item.
*
* @param i The index of the item to be referenced
*/
public KWListIter(int i) {
// Validate i parameter.
if (i < 0 || i > size) {
throw new IndexOutOfBoundsException(
"Invalid index " + i);
}
lastItemReturned = null; // No item returned yet.
// Special case of last item.
if (i == size) {
index = size;
nextItem = null;
} else { // Start at the beginning
nextItem = head;
for (index = 0; index < i; index++) {
nextItem = nextItem.next;
}
}
}

/**
* Construct a KWListIter that is a copy of another KWListIter
*
* @param other The other KWListIter
*/
public KWListIter(KWListIter other) {
KWListIter itr = new KWListIter(0);
itr.index = other.index;
itr.lastItemReturned = other.lastItemReturned;
itr.nextItem = other.nextItem;
}

/**
* Indicate whether movement forward is defined.
*
* @return true if call to next will not throw an exception
*/
@Override
public boolean hasNext() {
return nextItem != null;
}

/**
* Move the iterator forward and return the next item.
*
* @return The next item in the list
* @throws NoSuchElementException if there is no such object
*/
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
lastItemReturned = nextItem;
nextItem = nextItem.next;
index++;
return lastItemReturned.data;
}

/**
* Indicate whether movement backward is defined.
*
* @return true if call to previous will not throw an exception
*/
@Override
public boolean hasPrevious() {
return (nextItem == null && size != 0)
|| (nextItem.prev != null);
}

/**
* Return the index of the next item to be returned by next
*
* @return the index of the next item to be returned by next
*/
@Override
public int nextIndex() {
return index;
}

/**
* Return the index of the next item to be returned by previous
*
* @return the index of the next item to be returned by previous
*/
@Override
public int previousIndex() {
return index - 1;
}

/**
* Move the iterator backward and return the previous item.
*
* @return The previous item in the list
* @throws NoSuchElementException if there is no such object
*/
@Override
public E previous() {
if (!hasPrevious())
throw new NoSuchElementException();

else if (nextItem == null) // Iterator past the last element
nextItem = tail;

else {
nextItem = nextItem.prev;
}
lastItemReturned = nextItem;
index--;
return lastItemReturned.data;
}

/**
* Add a new item between the item that will be returned
* by next and the item that will be returned by previous.
* If previous is called after add, the element added is
* returned.
*
* @param obj The item to be inserted
*/
@Override
public void add(E item) {
Node<E> newNode = new Node<>(item);
if (head == null)
head = tail = newNode;

// Insert at head.
else if (nextItem == head) {

newNode.next = nextItem;
nextItem.prev = newNode;
head = newNode;
}

// Insert at tail.
else if (nextItem == null) {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
// Insert into the middle.
else {
newNode.prev = nextItem.prev;
nextItem.prev.next = newNode;
newNode.next = nextItem;
nextItem.prev = newNode;
}

// Increase size and index and set lastItemReturned.
size++;
index++;
lastItemReturned = null;
} // End of method add.


/**
* Remove the last item returned. This can only be
* done once per call to next or previous.
*
* @throws IllegalStateException if next or previous
* was not called prior to calling this method
*/
@Override
public void remove() {
//case1: lastItemReturned null
if (lastItemReturned == null)
throw new IllegalStateException();

//case2: lastItemReturned in the first node
else if (lastItemReturned == head) {
head = head.next;
if (head == null)
tail = null;
else
head.prev = null;
size--;
}

//case3: lastItemReturned in the last node
else if (lastItemReturned == tail) {
tail = tail.prev;
tail.next = null;
size--;
}

//case4: lastItemReturned in the middle
else {
lastItemReturned.prev.next = lastItemReturned.next;
lastItemReturned.next.prev = lastItemReturned.prev;
lastItemReturned = null;
}
}


/**
* Replace the last item returned with a new value
*
* @param item The new value
* @throws IllegalStateException if next or previous
* was not called prior to calling this method
*/
@Override
public void set(E item) {

lastItemReturned.data = item;
}


/**
* Method to find the index of the first occurence of an item in the list
*
* @param target The item being sought
* @return The index of the first occurence of the tartet item
* or -1 if the item is not found.
*/
//@Override
public int indexOf(Object target) {

return -1;
}


/**
* Method to find the index of the last occurence of an item in the list
*
* @param target The item being sought
* @return The index of the last occurence of the tartet item
* or -1 if the item is not found.
*/
// @Override
public int lastIndexOf(Object target) {

return -1;
}

/**
* Method to return the index of the minimum item in the list
* It is assumed that each item in the list implements Comparable
*
* @return Index of the minimum item in the list
* or -1 if the list is empty
* @throws ClassCastExcepition if the list elements do not implement Comparable
*/
public int indexOfMin() {

return 0;
}

}
}
Rating
0 0

There are no comments for now.