Compsci 201 Linked Lists From A-Z

2y ago
15 Views
2 Downloads
1.59 MB
46 Pages
Last View : 10d ago
Last Download : 2m ago
Upload by : Kaden Thurman
Transcription

Compsci 201Linked Lists from A-ZOwen AstrachanJeff ForbesOctober 20, 201710/20/17Compsci 201, Fall 2017, Linked Lists &More1

O is for Object Oriented Programming with inheritance and classes Open Source Copyright meets the Creative Commons Overflow From arithmetic to stacks: ouch! Occam’s Razor Not just compsci: simple is good10/20/17Compsci 201, Fall 2017, Linked Lists &More2

Plan for the Day Midterm and APT Quiz explained What you learn individually from results What we learn in creating class, assessments What the class collectively learns Linked Lists Re-examined Quick review and concentrate on low-levelimplementations Toward APT-3 and DNA-Linked assignment10/20/17Compsci 201, Fall 2017, Linked Lists &More3

Exam We will provide a pathway to help studentssucceed in 201 Lessons from midterm for students Lessons for midterm for professors Working toward a path to success, measuresuccess in some way that works10/20/17Compsci 201, Fall 2017, Linked Lists &More4

APT Quiz Very few technical issues on server side, but one Some issues on student side We have scores from nearly every student Still need to track timing, will be done Monday We still need to run similarity checks on solutions As a group you did very well10/20/17Compsci 201, Fall 2017, Linked Lists &More5

Highlights from Wednesday How do you remove all occurrences of “simple”from a list of Strings? How do you remove the first element of a list? How do you remove a middle element? How do you remove the last element? Does the kind of list matter? List , LinkedList , ArrayList 10/20/17Compsci 201, Fall 2017, Linked Lists &More6

Removing One or All Last class: removing list.get(0) N times Is O(N) for a LinkedList Is O(N2) for an ArrayList What about removing all occurrences of target? There is list.remove() in Java API, but g/blob/master/src/ListRemove.java10/20/17Compsci 201, Fall 2017, Linked Lists &More7

Aside: Using The Right Tool What is a ConcurrentModificationException? How does the enhanced for-loop work? Object iterated over implements Iterable Can’t remove while iterating using loop Idea: something will be missed when shifting g/blob/master/src/ListRemove.java10/20/17Compsci 201, Fall 2017, Linked Lists &More8

First Try at RemoveAll If we remove “ant” from [“ant”, “bat”, “cat”] ? OK! What about [“ant”, “ant”, “bat”, “cat”], Oh NO! What does .remove do?public List String removeAllWrong(String target,List String list) {for(int k 0; k list.size(); k ) {String w list.get(k);if (w.equals(target)) {list.remove(k);}}return list;}10/20/17Compsci 201, Fall 2017, Linked Lists &More9

Second Try at RemoveAll Adjust loop control variable when shifting This fixes the problem, it works, but .public List String removeAllGack(String target,List String list) {for(int k 0; k list.size(); k ) {String w list.get(k);if (w.equals(target)) {list.remove(k);k - 1;}}return list;}10/20/17Compsci 201, Fall 2017, Linked Lists &More10

LastTry at RemoveAll Use java.util.Iterator, lists have one Unfortunately, some operations are “optional” Idiom similar to Scanner, why? Interface!public List String removeAllIterator(String target,List String list) {Iterator String iter list.iterator();while (iter.hasNext()) {String w iter.next();if (w.equals(target)) {iter.remove();}}return list;}10/20/17Compsci 201, Fall 2017, Linked Lists &More11

Linear Reminder LIFO LIFO, Stack l/Stack.html Abomination from some perspectives, but getover it?10/20/17Compsci 201, Fall 2017, Linked Lists &More12

Linear Reminder FIFO FIFO, Queue l/Queue.htmlQueue String q new LinkedList ();10/20/17Compsci 201, Fall 2017, Linked Lists &More13

Random Reminder GIGO10/20/17Compsci 201, Fall 2017, Linked Lists &More14

ArrayList aka Vector How do you implement ArrayList and what iscomplexity of calling .add N times? Array instance variable: String[] myData When it’s full? Double size, copy, continue Suppose initially size 1 1 2 4 8 256 1024 That’s 2047, which is 2*1024-1 Grow to size N? Totall allocated 2*N - 110/20/17Compsci 201, Fall 2017, Linked Lists &More15

WOTO ci 201, Fall 2017, Linked Lists &More16

Lynn ConwaySee Wikipedia and lynnconway.com Joined Xerox Parc in 1973 Revolutionized VLSI design withCarver Mead Joined U. Michigan 1985 Professor and Dean, retired '98 NAE '89, IEEE Pioneer '09 Helped invent dynamic schedulingearly '60s IBM Transgender, fired in '68

LinkedList Internals Create an inner Node class Abstractly: two fields: info and pointer to Node Concretely: see next slide In practice: LinkedList uses doubly-linked list Can iterate forward and backwards Overhead for storage: two pointers: prev/next Tradeoff in performance: memory and speed .java?av f10/20/17Compsci 201, Fall 2017, Linked Lists &More18

A Node By Any Other Name Could be an inner class: implementation only Could be public class in a package Often simply a POJO: Plain Old Java Object Has no methods, does have constructor10/20/17public class Node {String value;Node next;Node(String s, Node link){value s;next link;}}Compsci 201, Fall 2017, Linked Lists &More19

Building linked lists Read file: the big dog, create list: dog big the Add new nodes to front of list// Scanner declarations hereNode list null;while (scanner.hasNext()) {list new Node(scanner.next(), list);} Where is the assignment to a .next field? Let’s rewrite with more code to explore10/20/17Compsci 201, Fall 2017, Linked Lists &More20

Building linked lists Read file the big dog, create list: dog big the Add new nodes to front of list// Scanner declarations hereNode list null;while (scanner.hasNext()) {String s scanner.next();Node temp new Node(s,null);temp.next list;list temp;} Unpacking the single line version can be helpful10/20/17Compsci 201, Fall 2017, Linked Lists &More21

Dissection of add-to-front List initially empty First node has first wordlistlistAlist new Node(word,list);Node(String s, Node link){ info s; next link;}B Read word, create node New node added to front Evaluate RHS of Then assign to LHS

Standard list processing (iterative) Visit all nodes once, e.g., count them or process thempublic int size(Node list){int count 0;while (list ! null) {count 1;list list.next;}return count;} What changes if we generalize meaning of process? Print nodes? Append “s” to all info fields Standard idiom: loop until null, list list.next10/20/17Compsci 201, Fall 2017, Linked Lists &More23

listRemoving first "cat""dog""cat""pig"public Node remove(Node list, String s){Node start list;while (list.next ! null) {if (list.next.value.equals(s)) {list.next list.next.next;break;}list list.next;}return start;}10/20/17Compsci 201, Fall 2017, Linked Lists &More24

Why Header -timing/blob/master/src/RawLinked.java Want every node to have a predecessor Otherwise first node is a special casepublic ListNode removeAll(String target, ListNode list) {ListNode dummy new ListNode("",list);ListNode first dummy;while (dummy.next ! null) {if (dummy.next.info.equals(target)) {dummydummy.next dummy.next.next;}""else {dummy dummy.next;}list"dog""cat""pig"}return first.next;}10/20/17Compsci 201, Fall 2017, Linked Lists &More25

Standard list processing (recursive) Visit all nodes once, e.g., count thempublic int recsize(Node list) {if (list null) return 0;return 1 recsize(list.next);} Base case is almost always empty list: null pointer Must return correct value, perform correct action Recursive calls use this value/state to anchor recursion Recursive calls make progress towards base case Almost always using list.next as argument10/20/17Compsci 201, Fall 2017, Linked Lists &More26

Recursion with pictures Counting recursivelyint recsize(Node list){if (list null)return 0;return 1 recsize(list.next);}ptrint result de list)return 1 recsize(list.next)recsize(Node list)return 1 recsize(list.next)recsize(Node list)return 1 recsize(list.next)recsize(Node list)return 1 recsize(list.next)

Linked list Practice: Copy What is a list? Empty or not: mirrored in codepublic Node copy(Node list) {if (null list) return null;Node first new Node(list.info,null);first.next copy(list.next);return first;} Examine code: .next field assigned? Can do this iteratively too, more variables/code Adding at back requires 10/20/17Compsci 201, Fall 2017, Linked Lists &More28

Linked list Practice: Copy II What is a list? Empty or not: mirrored in codepublic Node copy(Node list) {if (null list) return null;return new Node(list.info,copy(list.next));} Examine code, did we assign to .next field?10/20/17Compsci 201, Fall 2017, Linked Lists &More29

Two, two, two ways to reverse a list! We want to turn list ['A', 'B', 'C'] into rev ['C', 'B', 'A'] We will move one node at a time, no new nodes! Iteratively and recursivelyrevlist10/20/17ABCCompsci 201, Fall 2017, Linked Lists &More30

Iteration Step One A We moved ['A'] from list to the front of rev rev ['A'] and list ['B', 'C'] What's the next step? Invariant: rev points to reversed of nodes visitedso farArevlist10/20/17BCCompsci 201, Fall 2017, Linked Lists &More31

Iteration Step One B How do we make progress and maintaininvariant? Invariant: rev points to reversed of nodesvisited so far What should ['B'] or list.next point to? What happens if we write list.next rev What should rev point to? And list point to ?rev10/20/17AlistBCompsci 201, Fall 2017, Linked Lists &MoreC32

Iteration Step One C Making progress and maintain invariant? temp list.next (so we don't lose ['C']) list.next rev (add to front point to ['A']) rev list(rev points to front, ['B']) list temp(list updated)rev10/20/17AlistCompsci 201, Fall 2017, Linked Lists &MoreBC33

Loop and method finished Establish invariant before loop Update and re-establish within looprevAlistB10/20/17public void reverse(ListNode front){ListNode rev null;ListNode list front;while (list ! null) {ListNode temp list.next;list.next rev;rev list;Clist temp;}front rev; // update state!}Compsci 201, Fall 2017, Linked Lists &More34

Reverse Recursively This is harder to visualize, shorter to write Which method is preferred? Decide yourself Base case: zero or one node list, nothing to do Reversing a one node list: done Believe in the recursion Reverse after first, reconnect Pictures are important!CBAlist10/20/17Compsci 201, Fall 2017, Linked Lists &More35

First the whole thing, then dissect it This method returns the list it totally changed!private ListNode doRev(ListNode list){if (list null list.next null)return list;ListNode after doRev(list.next);list.next.next list;list.next null;return after;}10/20/17Compsci 201, Fall 2017, Linked Lists &More36

Establishing the base case Does the base case do the right thing? What if first null? Or a one node list?private ListNode doRev(ListNode list){if (list null list.next null)return list;ListNode after doRev(list.next);list.next.next list;list.next null;return after;}public void reverse(){front doRev(front);}10/20/17Compsci 201, Fall 2017, Linked Lists &More37

After recursive call, before listlistCBAA?CBafterprivate ListNode doRev(ListNode list){if (list null list.next null)return list;ListNode after doRev(list.next);list.next.next list;list.next null;return after;}10/20/17Compsci 201, Fall 2017, Linked Lists &More38

Programming with raw Linked Lists When adding or removing nodes Be sure you alter a .next field Typically via re-assignment or call to new Using iteration: keep pointer to first AND current Allow iteration over list, but must keep pointer to front Sometimes create dummy/header node, return dummy.next Recursion is sometimes simpler than iteration Code mirrors structure of data!10/20/17Compsci 201, Fall 2017, Linked Lists &More39

WOTO questionshttp://bit.ly/201fall17-oct20-2Sometimes recursion helps, sometimes not somuch, but practice is good10/20/17Compsci 201, Fall 2017, Linked Lists &More40

Wordladder Story Ladder from ‘white’ to ‘house’ white, while, whale, shale, I can do that optimally My brother was an English major My ladder is 16, his is 15, how? There's a ladder that's 14 words! The key is ‘sough’ Guarantee optimality! QUEUE10/20/17Compsci 201, Fall 2017, Linked Lists &More41

Queue for shortest pathpublic boolean findLadder(String[] words,String first, String last){Queue String qu new LinkedList ();Set String set new HashSet ();qu.add(first);while (qu.size() 0){String current qu.remove();if (oneAway(current,last)) return true;for(String s : words){if (! set.contains(s) && urn false;Compsci 201, Fall 2017, Linked Lists &More42

Shortest Path reprised How does Queue ensure we find shortest path? Where are words one away from first? Where are words two away from first? Why do we need to avoid revisiting a word, when? Why do we use a set for this? Why a HashSet? Alternatives? If we want the ladder, not just whether it exists What's path from white to house? We know thereis one.10/20/17Compsci 201, Fall 2017, Linked Lists &More43

Shortest path proof All words one away from start on queue first iteration What is first value of current when loop entered? All one-away words dequeued before two-away See previous assertion, property of queues Two-away before 3-away, Each 2-away word is one away from a 1-away word So all enqueued after one-away, before three-away Any w seen/dequeued that's n:away is: Seen before every n k:away word for k 1!10/20/17Compsci 201, Fall 2017, Linked Lists &More44

Keeping track of ladder Find w, a one-away word from current Enqueue w if not seen Call map.put(w,current) Remember keys are unique! Put word on queue once! map.put("lot", "hot") map.put("dot", "hot") map.put("hat", "hot")10/20/17Compsci 201, Fall 2017, Linked Lists &More45

Reconstructing Word Ladder Run WordLaddersFull rs/blob/master/src/WordLaddersFull.java See map and call to map.put(word,current) What about when returning the ladder, why isthe returned ladder in reverse order? What do we know about code when statementadding (key,value) to map runs?10/20/17Compsci 201, Fall 2017, Linked Lists &More46

LastTryat RemoveAll Use java.util.Iterator, lists have one Unfortunately, some operations are “optional” Idiom similar to Scanner, why? Interface! 10/20/17 Compsci 201, Fall 2017, Linked Lists &

Related Documents:

2/25/2021 Compsci 101, Spring 2021 10 Compsci 101 Pancakes, While loops, Parallel Lists Part 2 of 3 2/25/2021 Compsci 101, Spring 2021 11 Susan Rodger Nikki Washington February 25, 2021 while BOOL_CONDITION: LOOP_BODY # modify variables, affect expression Collatz Code 2/25/2021 Compsci 101, Spring 2021 12

9/5/22 Compsci 201, Fall 2022, OOP 3. Recapping some Java Themes 9/5/22 Compsci 201, Fall 2022, OOP 4. Comments on Java Style Code blocks: Opening {ends first line of if, for, while, or method . Aside: Python uses objects too 9/5/22 Compsci 201, Fall 2022, OOP 15 Split is a methodwe are calling on this String object, not a

Linked List Basics Linked lists and arrays are similar since they both store collections of data. The array's features all follow from its strategy of allocating the memory for all its elements in one block of memory. Linked lists use an entirely different strategy: linked lists allocate memory for each element

Implementasi ADT: Linked -List. SUR –HMM AA Fasilkom UI IKI20100/IKI80110P 2009/2010 Ganjil Minggu 6 2 Outline Linked Lists vs. Array Linked Lists dan Iterators Variasi Linked Lists: Doubly Linked Lists . List iterator (ListItr) menyediakan method-method

Singly-Linked Lists and Doubly-Linked Lists The ArrayListaddand removemethods are O(n) Because they need to shift the underlying array Linked list overcomes this: Add/remove items anywhere in constant time: O(1) Each element (node) in a linked list stores: The element information, of type E Alink to the next node

How the Dictionary is made Using a dictionary is reasonably straight -forward We will be clients, not implementers Efficiency not a large concern in 101 Our goal is to just get stuff done 10/8/2020 Compsci 101, Fall 2020 4 This Photo by Unknown Author is licensed under CC B

Introduction to Computer Graphics COMPSCI 464 Image credits: Pixar, Dreamworks, Ravi Ramamoorthi, . –Game design and development It is about –Learning the fundamentals of computer graphics –Implementing algorithms that are at the core of computer graphics . Fundamentals of Computer Graphics

The Adventure Tourism Development Index (ATDI) is a joint initiative of The George Washington University and The Adventure Travel Trade Association (ATTA). The ATDI offers a ranking of countries around the world based on principles of sustainable adventure tourism