//***********************************************//
//*******Linked Lists - November 30th, 2016*****//
//*********************************************//
-We get Taylor today!
-About the homework: there's a general panic going around: TA lab is flooded, getting a ton of emails, etc. Yes, it's a lot, there's a lot of stuff to look through, it's DENSE, you have to understand code you haven't written, etc. BUT: The POINT of the homework is to handle the GUI and show a basic understanding of JavaFX. If I can hit "Start" and the map pops up, and there's some sort of menu showing, AND I can sort-of interact with the map, then that's already a pretty good grade!
-I haven't even written the rubric since I wasn't sure how hard this would be! Trust me, if most people are struggling, you won't get an "F" for getting a basic interactable map to show up (now, would it be a "B"?)
-The due date will NOT be extended, though; you had 2 weeks to do this. MORE IMPORTANTLY, we want to finish grading by the end of the semester
-MAKE SURE TO COMPILE HOMEWORK 6 CORRECTLY; there will most likely be NO REGRADE CHANCES due to how close to the end we are
-------------------------------------------------------
-So, we start with data structures now!
-In real life, data structures are really important. MORE IMPORTANTLY (kinda):
-Linked lists appear ALL THE TIME in job interviews. You're expected to know these things forwards and back, along with the rest of the major data structures; problems involving these will be a MAJOR way companies
-So, arrays are a list of spaces for objects all in one contiguous set of memory; the problem though, is that we can have gaps in these spaces, so the array indices themselves have NO IDEA where the next piece of data is
-A LINKED LIST is a collection of data where each piece of data has a reference (usually a pointer) to the next piece of data in the list
[data] -> [data] -> [data]
-So, in order to iterate through this, we just follow the data pieces to wherever each points next!
-These data pieces are each called NODES; the first node if called the HEAD
-Head is usually stored in a reference variable; if the head is null, then there are NO elements in the list
-The last element in the list is called the TAIL;
-If there's only one item in the list, it is both the head AND the tail
-Now, there is a tradeoff: if we want to just get, say, the 3rd piece of data, we can't just jump there like in an array; we'd have to iterate through the list until we find the piece of data
-There are many variations to the linked list; instead of having a TAIL variable, we can just check if the pointer to the next node is "null", in which case, we're at the end of the linked list!
-Head, though...you always need somewhere to start, so basically every implementation has a Head variable
-The one we've discussed is a "Singly Linked List", as there's only a single reference in each node to its neighbors
-There's also a "Doubly Linked List", each node has a reference to both the next AND previous node, allowing us to go both forward and backwards
-HEAD usually doesn't have a link to the TAIL, though (except in one, specific case...which you'll learn about in 1332 :) )
[HEAD] <-> [node] <-> [node] <-> [node] <-> [TAIL]
-So, as far as actually coding this thing:
-The data could be an object, a primitive, etc.; it could be ANYTHING
-In practice, it'll always technically be an object, if only due to wrapper classes
-So, it can be ANYTHING? Sounds like a job for...Generics!
public class Node<E> {...}
-So, we'll have TWO pieces of instance data (for a singly-linked list)- A reference to the next node ("private Node<E> next") and something to actually hold the data ("private E data")
-Along with that, we'll need getters and setters for the data, and a constructor to actually instantiate a node:
public Node(E data) {
this.data = data;
next = null;
}
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
//getters / setters self-explanatory
-Okay, so we've coded the Node class! Now, though, we have to make the actually class for the LinkedList itself (public class LinkedList<E>)
-The class itself should just NEED one piece of instance data: a reference to the head
"public class LinkedList<E> {
Node head = null;
public LinkedList(E head) { //just have to pass in a data; the user doesn't even have to know what a linked list is
this.head = new Node(head);
}
public LinkedList() {
this.head = null;
}"
-So, we've got the basic data structure; now we want to be able to add things to the LinkedList!
-To do this, we need to get to the end of the list, then add our piece of data as the next
"public void add(E data) {
Node curNode = head;
while(curNode.next() != null) { //starts at head, then goes to the end of the list
curNode = curNode.next();
}
curNode.setNext(new Node(data));
}"
-Great! We can make a new LinkedList, we can add stuff to it...but what if we want to remove something from the list?
"public void remove(E data) {
Node curNode = head;
while(!curNode.getData().equals(data) && curNode.next != null) { //keep going until we reach the node we're looking for, or the end of the list
curNode = curNode.next();
}
...
}"
-Now we have a problem, though: once we remove the node, the node before it, that used to be pointing at the node we removed, won't be pointing at anything; that'll break the list! So, we have to make the previous node point to the next node instead:
...[node] -> [node] -X *poof* [node] -> ...
...[node] -> [node] --------> [node] -> ...
-So, we need a 2nd pointer to keep track of the node we just looked at
-Don't have to worry about setting curNode to null, as in Java, any object with no references to it (no way of reaching it) will be automatically removed
-EDGE CASES: What if data isn't in the list?
-Program won't know what to do! Could do something like, "if (curNode.getData())"
-What if we remove the head? Then the list doesn't know where the head is!
-We'll just have an "if (curNode.equals(head))" and set the next node to be the new head
-ALWAYS consider the edge cases; in real life, you will ALWAYS have to deal with them, and in job interviews, catching the edge cases is what makes a good programmer stand out