HL Task: Arrays vs Linked Lists

Task 1: Complete your website notes about the advantages and disadvantages of arrays and linked lists. Make sure you explain why these advantages and disadvantages exist. Use MS drawing objects in PowerPoint to make diagrams of each data structure. Remember all this stuff — it’s important — but don’t get too much into the code required for accessing or adding/removing stuff from linked lists. We’ll do that next week.

Task 2: Java provides two implementations of the List interface, one that is a wrapper class for an array and one that is a wrapper class for a linked list. Watch this video about ArrayLists (there’s a bit about generics in there too, which is useful to know but not on your syllabus directly) and then read the Java API on LinkedLists.

Task 3: You can time your code by making a call to System.currentTimeMillis() before your time-consuming operation and making another call to System.currentTimeMillis() afterwards, and subtracting one from the other. Create an ArrayList with a thousand integers in it and test the time take to do basic operations like accessing a value in the middle of the list and adding/removing values at the beginning/middle/end of the list. How does this compare with a LinkedList of the same size? What happens when you have a million numbers? How big does the list have to be before your computer falls over? (Save your work before finding out.)

Task 4: Wrap your code up in a nice class that has a main method that runs various tests and produces nicely formatted results.

Task 5: Put your code on your website and document your findings.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s