What’s the Difference Here?Contrast LinkedList and ArrayListWhat about LinkedList?Linked list applications continuedLinked lists, CDT and ADTBuilding linked listsDissection of add-to-frontStandard list processing (iterative)Standard list processing (recursive)Recursion with picturesRecursion and linked listsBinary TreesFrom doubly-linked lists to binary treesBasic tree definitionsA TreeNode by any other name…Printing a search tree in orderTree traversalsTree functionsBalanced Trees and ComplexityWhat is complexity?CompSci 100e9.1What’s the Difference Here?How does find-a-track work? Fast forward?CompSci 100e9.2Contrast LinkedList and ArrayListSee ISimpleList, SimpleLinkedList, SimpleArrayListMeant to illustrate concepts, not industrial-strengthVery similar to industrial-strength, howeverArrayList --- why is access O(1) or constant time?Storage in memory is contiguous, all elements same sizeWhere is the 1st element? 40th? 360th?Doesn’t matter what’s in the ArrayList, everything is a pointer or a reference (what about null?)CompSci 100e9.3What about LinkedList?Why is access of Nth element linear time?Why is adding to front constant-time O(1)?frontCompSci 100e9.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/modeling 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 sequenceCompSci 100e9.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) pojo: plain old Java objectpublic class Node{ Node p = new Node(); String value; p.value = “hello”;Node next; p.next = null;};p0CompSci 100e9.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 value; Node next; Node(String s, Node link){ value = s; next = link; } }; // … declarations here Node list = null; while (scanner.hasNext()) { list = new Node(scanner.next(), list); }What about adding to the end of the list?CompSci 100e9.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;}listCompSci 100e9.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 if we generalize what process means?Print nodes?Append “s” to all strings in list?CompSci 100e9.9Standard 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 pointerMust return correct value, perform correct actionRecursive calls use this value/state to anchor recursionSometimes one node list also used, two “base” casesRecursive calls make progress towards base caseAlmost always using list.next as argumentCompSci 100e9.10Recursion with picturesCounting 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 100e9.11Recursion and linked listsPrint nodes in reverse orderPrint all but first node and…•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 100e9.12Binary TreesLinked lists: efficient insertion/deletion, inefficient searchArrayList: search can be efficient, insertion/deletion notBinary trees: efficient insertion, deletion, and searchtrees used in many contexts, not just for searching, e.g., expression treessearch in O(log n) like sorted arrayinsertion/deletion O(1) like list, once location found!binary trees are inherently recursive, difficult to process trees non-recursively, but possible •recursion never required, often makes coding simplerCompSci 100e9.13From doubly-linked lists to binary treesInstead of using prev and next to point to a linear arrangement, use them to divide the universe in halfSimilar to binary search, everything less goes left, everything greater goes rightHow do we search?How do we insert?“llama”“tiger”“monkey”“jaguar”“elephant”“giraffe”“pig”“hippo”“leopard”“koala”“koala”“koala”“koala”“koala”CompSci 100e9.14Basic tree definitionsBinary tree is a structure:emptyroot node with left and right subtreesterminology: parent, children, leaf node, internal node, depth, height, path•link from node N to M then N is parent of M–M is child of N•leaf node has no children–internal node has 1 or 2 children•path is sequence of nodes, N1, N2, … Nk–Ni is parent of Ni+1–sometimes edge instead of node•depth (level) of node: length of root-to-node path–level of root is 1 (measured in nodes)•height of node: length of longest node-to-leaf path–height of tree is height of rootTrees can have many shapes: short/bushy, long/stringyIf height is h , how many nodes in tree?ABEDFCGCompSci 100e9.15A TreeNode by any other name…What does this look like?What does the picture look like?public class TreeNode{ TreeNode left; TreeNode right; String info; TreeNode(String s, TreeNode llink, TreeNode rlink){ info = s; left = llink;
View Full Document
Unlocking...