Goal : Linked Lists Do Now: 1. List the operations ArrayLists have that are O(1) 2. List the operations ArrayLists have that are O(N) Java Lists: https://docs.oracle.com/javase/8/docs/api/java/util/List.html The list interface does not require that you store the data in any particular way! Java linked lists: Scheme lists were linked lists. Remember Box Diagrams? Linked Lists are different in runtime from array based lists. add / remove at the end in the middle in the front List is a series of Nodes, each node has data, and a reference to the next (and possibly previous) Node. This is possible because the node doesn't store an entire node inside of it! Since objects are stored as references, you do not have an object inside of an object inside of an object. Instead you have an object with a reference to another object. That other object happens to be the same type as this object. MyNode: data next previous (optionally for double-linked lists) MyLinkedList: Starting Node Ending Node Size Get Started with the following portions of linked list in a repo MKS21X-LinkedList class Node{ private int data; private Node next,prev;}class MyLinkedList{ private int size; private Node start,end; public int size(); public boolean add(int value); public String toString();} |
|
|