2018-12-12

posted Dec 12, 2018, 5:38 AM by Konstantinovich Samuel   [ updated Dec 12, 2018, 12:58 PM ]
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();
}



Comments