Đang tạo bản xem trước...
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 { - Our IntList! What’s wrong with it? public int first; - All the fields are public public IntList rest; - Calling each link an IntList does not public IntList(int f, IntList r) { seem entirely correct... first = f; rest = r; } ... }
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; private IntNode next; user, store info about the list (ex. size) 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 private IntNode first; individual cars. Instead of dealing with the raw 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 the entire linked list every time we want the size x “First” is a pointer to the first link in the linked list. addFirst() size first getFirst() 3 addLast() We add these methods to abstract away size() the mechanics of adding items to, and getting items from, our list 5 10 15 item next
Review: SLList - How do we represent an empty linked list? - Set first to null? - This leads ugly code, as we will have to add a bunch of null checks to code that handles the list. - For example, addLast would need a special case for if the list is null - What can we do instead? - sentinel: a “dummy” node that doesn’t hold any important info, just a placeholder to help us avoid null checks - Goal of sentinel: make code as simple and generic as possible so no special cases
Review: Sentinel Node Diagram addFirst() size first getFirst() Instead of pointing to null, first points to addLast() 0 the sentinel node. size() ?? item next The sentinel is not included in the size addFirst() size first getFirst() 3 addLast() size() ?? 5 10 15 item next
1.1) SLList.insert - Think about what types of things/cases we need to check for - How do we get to the specified position? - When we get there, how to we reassign the pointers?
1.2) SLList.reverse - Drawing an IntList to work with is really helpful for this one - We cannot use new, so we have to use the nodes that already exist - Pointer manipulation - We can only move forward in an SLList, so what does that say about how we are constructing our end product? In what way are we making the end list? - The first element in the original list will become what element in the ending list? - Think about the cases: - Empty list? - List with single element? - List with two, three, four, etc. elements?
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 Say we want to remove this node
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 1. We need to jump to that link
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 2.Save a reference to this node (If we don’t, we will lose it forever! We need it later)
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 3.Remove its “next” pointer
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 4.Jump to the node before
Review: DLLists - Lists should have a method where you can remove an element in a certain position - Let’s do this with our SLLists + sentinel! . . . 5 10 15 5.Reassign next to the node after
Review: DLLists - Had to traverse the list twice to remove! - We can make this a lot faster by adding previous pointers in addition to next pointers. . . . 5 10 15
Review: ALists - Long time to traverse the DLList (have to traverse the whole structure) - What about arrays? - Constant time access! - Can’t resize easily - Let’s try this instead: AList - Underlying structure is an array - Create a resize function so we can support adding/removing - Utilize geometric resizing - Copy all items from the old array into new array - Basically Project 1A: ArrayDeques!
Hiển thị 19 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!