New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Ryley Lang


Ryley Lang
GPA 3.8

Michael Scott

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Michael Scott
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 6 page Class Notes was uploaded by Ryley Lang on Sunday September 6, 2015. The Class Notes belongs to C S 307 at University of Texas at Austin taught by Michael Scott in Fall. Since its upload, it has received 33 views. For similar materials see /class/181663/c-s-307-university-of-texas-at-austin in ComputerScienence at University of Texas at Austin.

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/06/15
Topic 13 Abstract Data Types and Data Structures quotGet your data structures correct first and the rest of the program will write itselfquot David Jones CS 307 Fundamentals of Computer Science ADTs and Data Structures Abstract Data Types 39 An Abstract Data Type is quotA set of data values and associated operations that are precisely speci ed independent of any particular implementationquot 39 Our List example 7 new List returns an empty List e listadd a adds a to the end of the list originalielements a 7 get x returns the element at position x in the List 7 size returns the size of the List CS 307 Fundamentals of 2 Computer Science ADTs and Data Structures Abstract Data Types 39 Java interfaces are a form of Abstract Data Types list operations to be performed without any implementation details Java List interface jzirunil Interface ListltEgt TiwdeHWlTHRle i any i k Vector A C E B A CS 307 Fundamentals of Computer Science ADTs and Data Structures Data Structures 39 A Data Structure is an implementation of an abstract data type and quotAn organization of information usually in computer memoryquot for better algorithm ef ciencyquot aList size W1 12 3 4 5 6 7 8 910 ciEiBiAiiviiii 4 ADTs and Data Structures List Object CS 307 Fundamentals of Computer Science Data Structure Concepts 39 Data Structures are containers they hold other data arrays are a data structure so are lists 39 Other types of data structures stack queue tree binary search tree hash table dictionary or map set and on and on wwwnistgovdads enwikiQediaorgwikiList of data structures 39 Different types of data structures are optimized for certain types of operations Cs 307 Fundamentals or 5 Computer Sclence ADTs and Data structures Core Operations Data Structures will have 3 core operations a way to add things a way to remove things a way to access things Details of these operations depend on the data structure Example List add at the end access by location remove by location More operations added depending on what data structure is designed to do 5 307 Fundamentals or 6 Computer Sclence ADTs and Data structures ADTs and Data Structures in Programming Languages Modern programming languages usually have a library of data structures Java collections framework C standard template libra Net framework small portion of VERY large library Python lists and tuples Lisp lists cs 307 Fundamentals or 7 Computer Sclence ADTs and Data structures Data Structures in Java Part of the Java Standard Library is the Collections Framework In class we will create our own data structures and discuss the data structures that exist in Java A library of data structures Built on two interfaces Collection Iterator http avasuncom 25e150docsguidecoll ectionsindexhtml Cs 307 Fundamentals or 3 Computer Sclence ADTs and Data structures The Java Collection interface A generic collection Can hold any object data type Which type a particular collection will hold is specified when declaring an instance of a class that implements the Collection interface Helps guarantee type safety at compile time 307 Fundamentals of 9 Computer Science ADTs and Data Structures Methods in the Collection interface publlC 1nterfaCe ColleCtlonltEgt publlC boolean addE o publlC boolean addAllColleCt10nlt extends Egt C publlC v01d clear publlC boolean contains0bjeCt o publlC boolean containsAllColleCtlonltgt C publlC boolean equals0bjeCt o publlC 1m hashCode publlC boolean isEmpty public IteratorltEgt iterator publlC boolean remove0b3eCt o publlC boolean removeAllColleCt10nltgt C publlC boolean retainAllColleCt10nltgt C publlC 1m size publlC ObjeCtH toArray publlC ltTgt T toArrayT a CS 307 Fundamentals of 10 Computer Science ADTs and Data Structures Implementing Collection A class that implemented the Collection interface and did not add any more operations or requirements would be a Bag A Bag is a data structure Items in the Bag have no implied order from the users perspective ofthe Bag there is no rst item or second item or Duplicates allowed Can have multiple copies of equal objects in the Bag differentiates a Bag from a Set CS 307 Fundamentals of 11 Co ter Science ADTs and Data Structures Why Reinvent the Wheel Why study ADTs Why reimplement some of them How many of you will actually go out and create your own linked list data structure from scratch The goal is to learn howto use data structures and how to create them Knowledge of data structures sometimes used as a litmus test CS 307 Fundamentals of Computer Science wheel ADTs and Data Structures List Class Revisited quotHe39s making a list And checking it twice Gonna find out Who39s naughty and nice Santa Claus is coming to townquot Santa Claus is Coming to Town CS 307 Fundamentals of 1 3 Computer Science ADTs and Data Structures Our List Class Created a List class as an example of encapsulation and power of inheritance and polymorphism also known as a dynamic array Underlying storage container was an array Maintained extra capacity because it quotseemed like a good ideaquot CS 307 Fundamentals of 14 Computer Science ADTs and Data Structures add Method public class GenericList private Object theArray private int theSize public void add0bject value iftheArraylength theSize thisincreaseSize Best case Big 0 Worst case Big 0 Average case Big O theArraytheSize value theSize private void increaseSize Object newArray new ObjecttheSize 2 forint i O i lt theSize i newArrayi theArrayi theArray newArray CS 307 Fundamentals of 1 5 Computer Science ADTs and Data Structures Big O of the Default add Normal Big 0 analysis fails quotMostquot adds are inexpensive 01 A few adds are very expensive due to resnzmg 0N What is the average case To determine average case we39ll do an amortized analysis amortized is a term from accounting Spread the cost of something over time CS 307 Fundamentals of 16 Computer Science ADTs and Data Structures Simplified Amortized Analysis Add N items to the list always at end of list Assume internal container starts out at size 1 Assume if we resize container we double the size Item Size of Work to Work to Container Resize Add 1 1 O 1 2 1 gt 2 1 1 3 2 gt 4 2 1 4 O 1 5 4 gt 8 4 1 6 8 O 1 7 8 O 1 8 8 O 1 9 8 gt 16 8 1 N 1 N 1 O 1 N N 1 gt 2N 2 N 1 1 CS 307 Fundamentals of 17 Computer Science ADTs and Data Structures Total Work to Add N items N steps to add myConisize item size The work in resizing is the sum ofa geometric sequence 124816 N12N1 ana1 rn391 sum terms 1 through n rana1r 1 a11anN1r2 sum2N1121 2N3 CS 307 Fundamentals of 18 Computer Science ADTs and Data Structures Average Work Per Item TotalWorkisN2N33N3 Divide by the N items to amortize the cost 3N 3 N items 3 3N steps per item The average work per item is 3 3N The amortized Big O is 01 What would the amortized Big O of adding at the end of the list be if we resized the list by 50 elements every time we needed to resize CS 307 Fundamentals of 19 Computer Science ADTs and Data Structures insert Method public void insertint index Object value iftheArraylength thesize thisincreasesize l forint i thesize s l i gt index i theArrayi 1 theArrayi theArrayindex value thesize Best case worst case and average case Big 0 CS 307 Fundamentals of 20 Computer Science ADTs and Data Structures get Method public Object getint index assert index lt thesize quotList index out of bounds quot return theArrayindex index Best case worst case and average case Big 0 CS 307 Fundamentals of 21 Computer Science ADTs and Data Structures Other Methods Best Worst Average Case Big O for remove method insert all method toString equals size CS 307 Fundamentals of 22 Computer Science ADTs and Data Structures The Java ArrayList Class Implements the List interface and uses an array as its internal storage container It is a list not an array The array that actual stores the elements of the list is hidden not visible outside of the ArrayList class all actions on ArrayList objects are via the methods ArrayLists are generic They can hold objects of any type CS 307 Fundamentals of 23 Computer Science ADTs and Data Structures Some of the ArrayList Methods int size boolean addE x E getint index E setint index E X void addint index E x E removeint index teratorltEgt iterator ListteratorltEgt istterator NOT all of the methods of the ArrayList class CS 307 Fundamentals of 24 Computer Science ADTs and Data Structures


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.