CompSci 100E19.1Getting in frontÿ Suppose we want to add a new elementþ At the back of a string or an ArrayList or a …þ At the front of a string or an ArrayList or a …þ Is there a difference? Why? What's complexity?ÿ Suppose this is an important problem: we want togrow at the front (and perhaps at the back)þ Think editing film clips and film splicingþ Think DNA and gene splicingÿ Self-referential data structures to the rescueþ References, reference problems, recursionCompSci 100E19.2ArrayLists and linked lists as ADTsÿ As an ADT (abstract data type) ArrayLists supportþ Constant-time or O(1) access to the k-th elementþ Amortized linear or O(n) storage/time with addo Total storage used in n-element vector is approx. 2n, spreadover all accesses/additions (why?)þ Adding a new value in the middle of an ArrayList is expensive,linear or O(n) because shifting requiredÿ Linked lists as ADTþ Constant-time or O(1) insertion/deletion anywhere, but…þ Linear or O(n) time to find where: sequential searchÿ Good for sparse structures: when data are scarce, allocateexactly as many list elements as needed, no wastedspace/copying (e.g., what happens when vector grows?)CompSci 100E19.3Linked list applicationsÿ Remove element from middle of a collection, maintain order, noshifting. Add an element in the middle, no shiftingþ What’s the problem with a vector (array)?þ Naively keep characters in a linked list, but in practice toomuch storage, need more esoteric data structuresÿ What’s (3x5+2x3+x+5)+(2x4+5x3+x2+4x) ?þ As a vector (3,0,2,0,1,5)and (0,2,5,1,4,0)þ As a list ((3,5), (2,3), (1,1), (5,0)) and ________?þ Most polynomial operations sequentially visit terms, don’tneed random access, do need “splicing”ÿ What about (3x100+5)?CompSci 100E19.4Linked list applications continuedÿ If programming in C, there are no “growable-arrays”, sotypically linked lists used when # elements in a collectionvaries, isn’t known, can’t be fixed at compile timeþ Could grow array, potentially expensive/wasteful especially if #elements is small.þ Also need # elements in array, requires extra parameterþ With linked list, one pointer used to access all the elements in acollectionÿ Simulation/modeling of DNA gene-splicingþ Given list of millions of CGTA… for DNA strand, find locationswhere new DNA/gene can be spliced ino Remove target sequence, insert new sequenceCompSci 100E19.5Linked lists, CDT and ADTÿ As an ADTþ Alistisempty,orcontainsanelementandalistþ ()or (x,(y,()))ÿ As a pictureÿ As a CDT (concrete data type)public class Node{Nodep=new Node();String info; p.info = “hello”;Node next; p.next = null;}p0CompSci 100E19.6Building linked listsÿ Add words to the front of a list (draw a picture)þ Create new node with next pointing to list, reset start of listpublic class Node {String info;Node next;Node(String s, Node link){info = s;next = link;}}// … declarations hereNode list = null;while (scanner.hasNext()) {list = new Node(scanner.nextString(), list);}ÿ What about adding to the end of the list?CompSci 100E19.7Dissection of add-to-frontÿ List initially emptyÿ First node has first wordÿ Each new word causes newnode to be createdþ New node added to frontÿ Rhs of operator = completelyevaluated before assignmentlistAlist = new Node(word,list);BNode(String s, Node link){ info = s; next = link;}listCompSci 100E19.8Standard 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++;list = list.next;}return count;}ÿ What changes in code above if we change what “process” means?þ Print nodes?þ Append “s” to all strings in list?CompSci 100E19.9Splicingÿ Consider prepending (add to front) and two methods:public void prepend(String s) {myString = s + myString;}public void prepend(String s) {myFront = new Node(s,myFront);myCount += s.length();}ÿ What is hidden complexity of these operations? Why?CompSci 100E19.10Timings in Splice.java0.00116.4187000189,0000.00111.1336000162,0000.0017.0285000135,000????8000216,0000.0014.2534000108,000LinkStrandStringStrandmethodlengthCompSci 100E19.11New task in Strand.javaÿ Rather than simply prepending, what aboutsplicing anywhere?þ We have s.insert(k,str) to add string at kthposition,so prepending is s.insert(0,str)ÿ We want to mirror this behavior in all classesþ What do we do in base class?þ How do we implement in LinkStrand class?o What are issues?o How fast will it be?CompSci 100E19.12Building linked lists continuedÿ What about adding a node to the end of the list?þ Can we search and find the end?þ If we do this every time, what’s complexity of building an N-nodelist? Why?ÿ Alternatively, keep pointers to first and last nodes of listþ If we add node to end, which pointer changes?þ What about initially empty list: values of pointers?o Will lead to consideration of header node to avoid special casesin writing codeÿ What about keeping list in order, adding nodes by splicing intolist? Issues in writing code? When do we stop searching?CompSci 100E19.13Standard 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þ Sometimes one node list also used, two “base” casesÿ Recursive calls make progress towards base caseþ Almost always using list.next as argumentCompSci 100E19.14Recursionwithpicturesÿ Counting recursivelyint recsize(Node list){if (list == null)return 0;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)recsize(Node list)return 1+recsize(list.next)System.out.println(recsize(ptr));ptrCompSci 100E19.15Recursion and linked listsÿ Print nodes in reverse orderþ Print all but first node and…o Print first node before or after other printing?public void print(Node list) {if (list != null){}}print(list.next);System.out.println(list.info);System.out.println(list.info);print(list.next);CompSci 100E19.16Complexity Practiceÿ What is complexity of Build? (what does it do?)public Node build(int n) {if (n == 0) return null;Node first = new Node(n, build(n-1));for(int k = 0; k < n-1; k++) {first = new Node(n,first);}return
View Full Document
Unlocking...