DOC PREVIEW
Duke CPS 100E - Getting in front

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 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 to grow 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, recursion, binkyCPS 1009.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 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 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, allocate exactly as many list elements as needed, no wasted space/copying (e.g., what happens when vector grows?)CPS 1009.3Linked list applicationsRemove element from middle of a collection, maintain order, no shifting. Add an element in the middle, no shiftingWhat’s the problem with a vector (array)?Emacs visits several files, internally keeps a linked-list of buffersNaively keep characters in a linked list, but in practice too much 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’t need random access, do need “splicing”What about (3x100 + 5) ?CPS 1009.4Linked list applications continuedIf 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 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 a collectionSimulation/modelling of DNA gene-splicingGiven 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 ADTAs an ADTA list is empty, or contains an element and a list( ) or (x, (y, ( ) ) )As a pictureAs 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 listsAdd 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-frontList initially emptyFirst node has first wordEach new word causes new node to be createdNew node added to frontRhs 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 aspectsAir traffic controlMicrosoft 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.pdfTHERAC 25: Radiation machine that killed many peoplehttp://sunnyday.mit.edu/papers/therac.pdfCPS 1009.10See Splice.java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?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.javaRather 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 classesWhat 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 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-node list? 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?•Will lead to consideration of header node to avoid special cases in writing codeWhat 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

Duke CPS 100E - Getting in front

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Getting in front
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Getting in front and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Getting in front 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?