Linked Lists, Arrays

Exam Prep 03

CS 61B // Fall 2020

Announcements

Week 3

• Project 1A has been released
• We have exam prep sections now! (And video walkthroughs for them)
• Lab 2 checkoff due this Friday
• Gitbugs
• No more debugging help in OH :(

CS 61B // Fall 2020

Content Review

CS 61B // Fall 2020

More on Arrays

Arrays are objects that are:

1. Immutable in size, or unexpandable once they’ve been initialized
2. Strict in what type they take - all items in an int array must be ints, all items in String arrays must be Strings, etc.

​

Why do we use Arrays?

Arrays are fast - unlike python arrays or linked lists, Java knows exactly where each element is, so running arr[100] is way faster than running list.get(100).

Arrays are safe - because the size and type of the array is predetermined, Java can catch more errors during compilation (ex. If you try to put a String into an int array, Java will catch it before anything runs)

​

CS 61B // Fall 2020

More on Linked Lists

Singly Linked Lists contain pointers to the item after the current item.

Now that we have a LinkedList object, we are don’t have to concern ourselves with individual IntNodes - that’s now abstracted away.

​

Doubly Linked Lists contain pointers to both the item before and the item after the current item.

For DLLists, we use a sentinel node which contains no value to link to the first and last node so that people can’t edit our IntNodes without going through the List object.

​

Why do we use Linked Lists?

Linked Lists are fast - you can easily insert items into a Linked List a lot faster than arrays

Linked Lists are flexible - you can change the size of a Linked List without much work because its a sequence of nodes connected via pointers

CS 61B // Fall 2020

Destructive vs. Nondestructive Methods

Destructive methods modify the object that was passed in.

Often (but not always), for destructive methods, the return type is void because their purpose is to change the object passed in.

​

Nondestructive methods don’t modify the object that was passed in.

Often (but not always), for nondestructive methods, the return type is not void because they can’t change any of the inputs.

​

CS 61B // Fall 2020

Worksheet

CS 61B // Fall 2020

1 Flatten

1. public static int[] flatten(int[][] x) {
2. int totalLength = 0;
4. for(___________________________________) {
5. __________________________________________________
6. }
7. ​
8. Int[] a = new int[totalLength];
9. int aIndex = 0;
10. for(___________________________________) {
11. __________________________________________________
12. __________________________________________________
13. __________________________________________________
14. __________________________________________________
15. }
16. ​
17. return a;
18. }

CS 61B // Fall 2020

2 Skippify

• public class IntList {
• public int first;
• public IntList rest;
• @Override
• public boolean equals(Object o) {...}
• public static IntList list(int... args) {...}
• public void skippify() {
• IntList p = this;
• int n = 1;
• while (p != null) {
• IntList next = ___________________________________;
• for (___________________________________) {
• if (___________________________________) {
• ___________________________________;
• }
• ___________________________________;
• }
• ___________________________________
• ___________________________________
• ___________________________________
• }}}

CS 61B // Fall 2020

3 Even Odd

• public class IntList {
• public int first;
• public IntList rest;
• public IntList(int f, IntList r) {...}
• public static void evenOdd(IntList lst) {
• if(________________________________) { return; }
• IntList second = ___________________________________;
• int index = ___________________________________;
• while (___________________________________) {
• ___________________________________
• ___________________________________
• ___________________________________
• ___________________________________
• }
• ___________________________________
• }
• }

CS 61B // Fall 2020