Getting in frontArrayLists and linked lists as ADTsLinked list applicationsLinked list applications continuedLinked lists, CDT and ADTBuilding linked listsDissection of add-to-frontStandard list processing (iterative)Nancy Leveson: Software SafetySee Splice.javaTimings in Splice.javaNew task in Strand.javaBuilding linked lists continuedStandard list processing (recursive)Recursion with picturesRecursion and linked listsComplexity PracticeChanging a linked list recursivelyCPS 1009.1Getting in front Suppose we want to add a new elementAt 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 to grow at the front (and perhaps at the back)Think editing film clips and film splicingThink DNA and gene splicingSelf-referential data structures to the rescueReferences, reference problems, recursion, binkyCPS 1009.2ArrayLists and linked lists as ADTsAs an ADT (abstract data type) ArrayLists supportConstant-time or O(1) access to the k-th elementAmortized linear or O(n) storage/time with add•Total storage used in n-element vector is approx. 2n, spread over all accesses/additions (why?)Adding a new value in the middle of an ArrayList is expensive, linear or O(n) because shifting requiredLinked lists as ADTConstant-time or O(1) insertion/deletion anywhere, but…Linear or O(n) time to find where, sequential searchGood for sparse structures: when data are scarce, allocate exactly as many list elements as needed, no wasted space/copying (e.g., what happens when vector grows?)CPS 1009.3Linked list applicationsRemove element from middle of a collection, maintain order, no shifting. Add an element in the middle, no shiftingWhat’s the problem with a vector (array)?Emacs visits several files, internally keeps a linked-list of buffersNaively keep characters in a linked list, but in practice too much storage, need more esoteric data structuresWhat’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’t need random access, do need “splicing”What about (3x100 + 5) ?CPS 1009.4Linked list applications continuedIf programming in C, there are no “growable-arrays”, so typically linked lists used when # elements in a collection varies, isn’t known, can’t be fixed at compile timeCould grow array, potentially expensive/wasteful especially if # elements is small.Also need # elements in array, requires extra parameterWith linked list, one pointer used to access all the elements in a collectionSimulation/modelling of DNA gene-splicingGiven list of millions of CGTA… for DNA strand, find locations where new DNA/gene can be spliced in•Remove target sequence, insert new sequenceCPS 1009.5Linked lists, CDT and ADTAs an ADTA list is empty, or contains an element and a list( ) or (x, (y, ( ) ) )As a pictureAs a CDT (concrete data type)public class Node{ Node p = new Node(); String info; p.info = “hello”;Node next; p.next = null;};p0CPS 1009.6Building linked listsAdd words to the front of a list (draw a picture)Create new node with next pointing to list, reset start of list public class Node { String info; Node next; Node(String s, Node link){ info = s; next = link; } }; // … declarations here Node list = null; while (scanner.hasNext()) { list = new Node(scanner.nextString(), list); }What about adding to the end of the list?CPS 1009.7Dissection of add-to-frontList initially emptyFirst node has first wordEach new word causes new node to be createdNew node added to frontRhs of operator = completely evaluated before assignmentlistAlist = new Node(word,list);B Node(String s, Node link) { info = s; next = link;}listCPS 1009.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?CPS 1009.9Nancy Leveson: Software SafetyFounded the field Mathematical and engineering aspectsAir traffic controlMicrosoft word "C++ is not state-of-the-art, it's only state-of-the-practice, which in recent years has been going backwards"Software and steam engines: once extremely dangerous?http://sunnyday.mit.edu/steam.pdfTHERAC 25: Radiation machine that killed many peoplehttp://sunnyday.mit.edu/papers/therac.pdfCPS 1009.10See Splice.javaConsider 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?CPS 1009.11Timings in Splice.java methodlengthStringStrand LinkStrand4000 108,000 4.253 0.0015000 135,000 7.028 0.0016000 162,000 11.133 0.0017000 189,000 16.418 0.0018000 216,000 ?? ??CPS 1009.12New task in Strand.javaRather than simply prepending, what about splicing anywhere?We have s.insert(k,str) to add string at kth position, so prepending is s.insert(0,str)We want to mirror this behavior in all classesWhat do we do in base class?How do we implement in LinkStrand class?•What are issues?•How fast will it be?CPS 1009.13Building linked lists continuedWhat 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-node list? Why?Alternatively, keep pointers to first and last nodes of listIf we add node to end, which pointer changes?What about initially empty list: values of pointers?•Will lead to consideration of header node to avoid special cases in writing codeWhat about keeping list in order, adding nodes by splicing into list? Issues in writing code? When do we stop searching?CPS 1009.14Standard list processing (recursive)Visit all nodes once, e.g., count them public int recsize(Node list) { if (list == null) return 0; return 1 + recsize(list.next); }Base case is almost always empty list: null
View Full Document