Lesson 17: Lists and more Generics

The List Interface:

• List Interface: Declares methods that can be used on lists
  • Implemented by the ArrayList and LinkedList Classes
• Lists can add, remove, and contain data
  • Can search through a list for a specific piece of data
• Some methods of the List Interface:
  • add(): Appends a element to the end of a list
  • clear(): Removes all elements from a list
  • contains(): Returns if an element is in a list
  • remove(): Deletes an element from a list
  • size(): returns the number of elements in a list

ArrayLists:

ArrayList Basics:

• A high-level way to work with arrays as lists

  • An implementation of the list interface with an array being the underlying data structure
  • Internally declares an object array called elementData
    • All methods are done on elementData
    • Creates a new array object when elementData is too large

• Works similarly to an array

  • Can call methods on the ArrayList
  • Can be traversed using a for-each loop

• Sized is not fixed and can increase/decrease

• Autoboxing: Converting a primitive type to its object counterpart

  • Ex. int converts to an Integer object
  • Happens automatically
  • Allows primitives to be used in ArrayLists

Creating an ArrayList:

• ArrayList is a Generic class
  • Can be created with or without constraints
• A specified initial length can be declared for both ArrayList types:
  • Initial length is 10 if not defined

ArrayList arrayListName = new ArrayList(length);

• Creating a raw type ArrayList:
  • Created without constraints or parameters
  • Can refer to any Java object
  • Each initial reference is null

  ArrayList arrayListName = new ArrayList();

• Creating a parameterized type ArrayList:
  • Created with a specific type declared
  • Internal array is still an object array
  • Simply restricts what parameters List methods can have

  //Two legal ways:
  ArrayList<elementType> arrayListName = new ArrayList<elementType>();
  ArrayList<elementType> arrayListName = new ArrayList<>();

LinkedLists:

Basics of Generic Classes:

• Used to avoid type issues at runtime
• Don’t need to cast before calling methods
• To turn a class into a generic, add a Type parameter to the end of the class header
  • Can have multiple type parameters

  //Single type parameter
  public class className<T> {
  }
  //Multiple type parameters
  public class className<X,Y,Z> {
  }

• Types can be bounded using extends
  • Used for both inheritance and interfaces
  • Can have multiple restrictions

  //Only objects that are a subclass of otherClassName can be input
  public class className<T extends otherClassName> {
  }
  //Only objects that implement Comparable can be input
  public class className<T extends Comparable> {
  }
  //Only objects that are a subclass of otherClassName and implement both Comparable and otherInterfaceName can be input
  public class className<T extends otherClassName & Comparable & otherInterfaceName> {
  }

• Example of non-generic vs generic:
  • Without generics:
  • With generics:

LinkedList Basics:

• Node: An element of a LinkedList
  • A private class within the LinkedList Class
  • Located in random areas of memory (Unlike an ArrayList)
  • Contains both the data and a pointed to the next node in the list
• Head: A instance variable that is a reference to the first node in a LinkedList
  • Is null if the LinkedList is empty
• LinkedList Class: Contains the Head, Private Node Class, and all the methods that can be called on the LinkedList

Node Class:

private class Node<E> {
  E data;
  Node<E> next;
 
  Node(E, data, Node<E> next) {
    this.data = data;
    this.next = next;
  }
}

Adding Data to the Front:

//Creates new node that points to the old head while making head point to the newly created node
head = new Node<E>(data, head);

Traversal:

//Moving through the entire list
Node current = head;
while (current != null) {
  current = current.next;
}

Adding data to the Rear:

//Creating new end node
Node<E> node = new Node<E>(newData, null);
//Creating current placeholder for traversal
Node<E> current = head;
//Making the node the head if the LinkedList is empty
if (head == null) {
  head = node;
}
//If LinkedList isn't empty
else {
  while (current.next != null) {
    current = current.next;
  }
}
//Adding the data to the rear
current.next = node;

Removing Data:

• To delete data, you must take the pointer from the previous node and point it to the next one after the deleted node
• Delete the pointer from the previous node to the deleted node

Remove From Front:

//Checks if LinkedList is empty
if (isEmpty()) {
  return null;
}
E removedData = head.data;
head = head.next;
return removedData;

Remove From Rear:

E removedData;
 
if (isEmpty()) {
  removedData = null;
} 
else if (head.next == null) {
  removedData = head.data;
  head = null;
} 
else {
  Node<E> current = head;
  while (current.next.next != null) {
      current = current.next;
  }
  removedData = current.next.data;
  current.next = null;
}
 
return removedData;

ArrayList vs LinkedList:

• ArrayLists are limited by Arrays
  • Must create a new array when resizing
  • Has an inital size
  • Needs to shift elements when adding anywhere other than the end of a list
• ArrayLists can get data faster than a LinkedList