CPT 102_LEC 13-14

1. List using linked nodes with header

• LinkedList extends AbstractList
• Has fields for linked list of Nodes and count
• Has an inner class: Node, with public fields
• get(index), set(index, item)
  • loop to index’th node, then get or set value
• add(index, item), remove(index)
  • deal with special case of index == 0
  • loop along list to node one before index’th node then add or remove
  • check if go past end of list
• remove(item)
  • deal with special case of item in first node (i.e. conversion into empty set after removal)
  • loop along list to node one before node containing item then remove
  • check if go past end of list

2. Code

• import java.util.AbstractList;
  
  public class LINKLIST {
  }
  class LinkedList<E> extends AbstractList<E>{
      private Node<E> data;
      private int count;
      public LinkedList(){
          this.data = null;
          this.count = 0;
      }
      private static class Node<E>{
          public E value;
          public Node<E> next;
          public Node(E val, Node<E> node){
              value = val;
              next = node;
          }
      }
  
      //Get
      public E get(int index){
          if (index < 0) {
              throw new IndexOutOfBoundsException();
          }
          Node<E> node=data;
          int i = 0; // position of node
          while (node!=null && i++ < index) {
              node=node.next;
          }
          if (node==null) {
              throw new IndexOutOfBoundsException();
          }
          return node.value;
      }
      //Set
      public E set(int index, E value){
          if (index < 0) {
              throw new IndexOutOfBoundsException();
          }
          Node<E> node=data;
          int i = 0; // position of node
          while (node!=null && i++ < index) {
              node=node.next;
          }
          if (node==null) {
              throw new IndexOutOfBoundsException();
          }
          E ans = node.value;
          node.value = value;
          return ans;
      }
      public void add(int index, E item){
          if (item == null) {
              throw new IllegalArgumentException();
          }
          if (index==0){ // add at the front.
              data = new Node<E>(item, data);
              count++;
              return;
          }
          Node<E> node=data;
          int i = 1; // position of next node
          while (node!=null && i++ < index) {
              node=node.next;
          }
          if (node == null) {
              throw new IndexOutOfBoundsException();
          }
          node.next = new Node<>(item, node.next);
          count++;
      }
  
      public boolean remove (Object item){
          if (item==null || data==null) return false;
          if (item.equals(data.value)) {
              data = data.next;
          } else {
              Node<E> node = data;
              while (node.next!=null && !node.next.value.equals(item)) {
                  node=node.next;
              }
              if (node.next==null) {
                  return false;
              }
              node.next = node.next.next;
          }
          count--;
          return true;
      }
          @Override
      public int size() {
          return count;
      }
  }