Ch2.pdf

ArrayList complexity java.util.ArrayList Worst Average Best int size() O(1) E get(int index)...

ArrayList complexity java.util.ArrayList Worst Average Best int size() O(1) E get(int index) O(1) E set(int index, E obj) O(1) boolean add(E obj) O(1)* void add(int index, E obj) O(n) O(n) O(1)* E remove(int index) O(n) O(n) O(1) boolean remove(Object obj) O(n) boolean contains(Object obj) O(n) O(n) O(1) int indexOf(Object obj) O(n) O(n) O(1) *amortized Fall 2020 15-121 (Reid-Miller) 7 Java Software Structures, 4th Edition, Lewis/Chase 4-1  ArrayLists Advantages: Time to access/set element 0 is the same as element 9000, referred to as “random access.” Space efficient. Disadvantages: Need to shift data to insert or delete values. Fixed size. Need to copy and expand the array to store more values. All data in the array must be store sequentially in memory. It can be hard to find a really big piece of contiguous memory. Fall 2020 15-121 (Reid-Miller) 10 Java Software Structures, 4th Edition, Lewis/Chase 4-2  My morning Wake up Get dressed Shower Brush teeth Loading… Eat breakfast Get backpack Ride bike to work Fall 2020 15-121 (Reid-Miller) 12 Java Software Structures, 4th Edition, Lewis/Chase 4-3  My morning Wake up Get dressed Shower Eat breakfast Brush teeth Get backpack Ride bike to work Fall 2020 15-121 (Reid-Miller) 13 Java Software Structures, 4th Edition, Lewis/Chase 4-4  A linked list is a linear data structure where each element is a separate object. Each data entry is stored in its own node object. Each node also has a reference to the node that is the next data entry. A reference, usually called the head, points to the node with the first data entry. In last node in the list the reference to the next nodes is n u l l to signify the end of the list. Fall 2020 15-121 (Reid-Miller) 14 Java Software Structures, 4th Edition, Lewis/Chase 4-6  Linked Lists Advantages: Don’t need large blocks of contiguous memory. Breaks up an array into little pieces Can grow and shrink without copying data. Disadvantages: Access is sequential. Slow to access the middle of the list. Analogy: video tapes vs DVDs What arrays/ArrayLists do well, linked list do poorly and vice versa. Fall 2020 15-121 (Reid-Miller) 15 Java Software Structures, 4th Edition, Lewis/Chase 4-7  Node class: Node n = new Node(“first”, anotherNode); String n Node "first" data next Node anotherNode What should getNext return for the last node in a linked list? Fall 2020 15-121 (Reid-Miller) 17 Java Software Structures, 4th Edition, Lewis/Chase 4-8  Linked Structures An alternative to array-based implementations are linked structures A linked structure uses object references to create links between objects Recall that an object reference variable holds the address of an object Java Software Structures, 4th Edition, Lewis/Chase 4-9  Linked Structures A Person object, for instance, could contain a reference to another Person object A series of Person objects would make up a linked list: Java Software Structures, 4th Edition, Lewis/Chase 4 - 10  Linked Structures Links could also be used to form more complicated, non-linear structures Loading… Java Software Structures, 4th Edition, Lewis/Chase 4 - 11  Linked Lists There are no index values built into linked lists To access each node in the list you must follow the references from one node to the next Person current = first; while (current != null) { System.out.println(current); current = current.next; } Java Software Structures, 4th Edition, Lewis/Chase 4 - 12  Linked Lists Care must be taken to maintain the integrity of the links To insert a node at the front of the list, first point the new node to the front node, then reassign the front reference Java Software Structures, 4th Edition, Lewis/Chase 4 - 13  Linked Lists To delete the first node, reassign the front reference accordingly If the deleted node is needed elsewhere, a reference to it must be established before reassigning the front pointer Java Software Structures, 4th Edition, Lewis/Chase 4 - 14  Linked Lists So far we've assumed that the list contains nodes that are self-referential (Person points to a Person) But often we'll want to make lists of objects that don't contain such references Solution: have a separate Node class that forms the list and holds a reference to the objects being stored Java Software Structures, 4th Edition, Lewis/Chase 4 - 15  Implementing a Stack using Links Let's now implement our own version of a stack that uses a linked list to hold the elements Our LinkedStack class stores a generic type T and implements the same StackADT interface used previously A separate LinearNode class forms the list and hold a reference to the element stored An integer count will store how many elements are currently in the stack Java Software Structures, 4th Edition, Lewis/Chase 4 - 16  Implementing a Stack using Links Since all activity on a stack happens on one end, a single reference to the front of the list will represent the top of the stack Java Software Structures, 4th Edition, Lewis/Chase 4 - 17  Implementing a Stack using Links The stack after A, B, C, and D are pushed, in that order: Java Software Structures, 4th Edition, Lewis/Chase 4 - 18  Implementing a Stack using Links After E is pushed onto the stack: Java Software Structures, 4th Edition, Lewis/Chase 4 - 19  Stack Implementation Using LinkedList Please refer to code examples covered in the class – MyLinkedList.java – MyLinkedListStack.java Java Software Structures, 4th Edition, Lewis/Chase 4 - 20