WUSTL CSE 131 - sp14_9 (16 pages)

Previewing pages 1, 2, 3, 4, 5 of 16 page document View the full content.
View Full Document

sp14_9



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
View Full Document

sp14_9

137 views


Pages:
16
School:
Washington University in St. Louis
Course:
Cse 131 - Computer Science I
Computer Science I Documents

Unformatted text preview:

CSE 131 Computer Science 1 Module 9 Linked Lists Using references to link objects Basic operations on linked lists Implementing a linked list of integers Storing a sequence of records Oftentimes we need to store a sequence of data records E g The list of students ID names grades etc All the emails sorted by arrival time Finishing times of marathon runners Bank transactions Storing a sequence of records Need to support these operations get the i th record delete the i th record insert a record to the i th place Using an array to store such data records Pros and cons Fast random access get the i th record Slow insert delete Need to know the maximum size beforehand Overflow risk vs waste of storage A new data structure Linked Lists List of integers 2 3 5 2 16 4 2 Key 3 5 2 16 4 differences to array Array random access directly goes to i th record List sequential access follows the references Inserting and Deleting Inserting a record 2 3 5 2 16 4 2 16 4 7 Removing 2 a record 3 5 Reference in Java A must read http stackoverflow com questions 40480 is java pass by reference Study all the examples there Linked Lists List of integers 2 3 5 2 16 4 2 3 5 2 16 4 public class ListItem public int number public ListItem next public ListItem int value ListItem p number value next p p Building lists with the constructor q 3 7 ListItem p new ListItem 3 null ListItem q new ListItem 7 p r 2 ListItem r new ListItem 2 new ListItem 5 null What happens when q p when ListItem d r next 5 toString for the ListItem class public class ListItem public int number public ListItem next public ListItem int value ListItem p number value next p public String toString if next null return number else return number next toString Traversing a List Pass over list by advancing object reference Task get the sum of all ListItem values reachable from a ListItem p p 2 3 5 2 16 recursive traversal int sum ListItem p if p null return 0 else return p number sum p next 4 iterative traversal int sum ListItem p int



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view sp14_9 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 sp14_9 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?