Discussion 3: Linked Lists & Arrays Christine Zhou Agenda Administrivia Review of SLLists SLList problems (1.1, 1.2) Review of arrays Array problems (2.1, 2.2) Preface Lots of questions on the discussion today. These are for practice! We will not be able to get through all of them. Administrivia Project 1A due this Friday! Implementing deque interface, highly recommend to use Java Visualizer. Start early!! Office hours: pay special attention to the locations! CSM sign-ups will open tonight, 9pm, and is first come first served! Opportunity to get extra help in a small-group setting with a mentor. Pre-semester advising still available @414 (Email me!) Choose Mentor GSI’s and see the automated extension system at registration.datastructur.es Survey: tinyurl.com/cz-disc3-sp19 (please fill this out so I know what to focus on today!) Review: IntList public class IntList { public int first; public IntList rest; public IntList(int f, IntList r) { first = f; rest = r; } ... } Our IntList! What’s wrong with it? All the fields are public Calling each link an IntList does not seem entirely correct... Review: SLList Access modifiers changed to private Outside users cannot access fields directly public class SLList { Hides the internals using encapsulation private class IntNode { Hide the inner workings of the list from the private int item; user, store info about the list (ex. size) private IntNode next; private IntNode(int i, IntNode - n) User sees the list as a whole, not the { individual nodes of the list, and does not item = i; have to deal with logic of pointer next = n; manipulation } Analogy: You refer to a train as a whole, not as } individual cars. Instead of dealing with the raw private IntNode first; public SLList(int x) { links with first and next, you refer to it as a first = new IntNode(x, null); whole. } public int get(int position) { ... } Review: SLList Diagram We add a size variable so we don’t have to step through t