Recording 19 & 20: LinkedLists

What’s the time complexity of accessing an array value at an index & why?

Constant time O(1)

• Arrays are memory types their size & type of the items are set at compile time

What is a LinkedList?

A data structure which specializes in inserting new values but, bad at accessing or updating values

When should you choose an array over LinkedList and vice versa?

ArrayList

• Program needs to look stuff up often

• program needs to overwrite items often

LinkedList

• Insert new items often

Explain time efficiency between LinkedList & Arrays

How are HashMaps implemented “under the hood”?

Using both arrays & linkedlists

How does this implementation explain the O(n) complexity of retrieving a value from a map but, O(1) in the average case?

It’s because of collisions as the hashmaps then become linkedlist

How can a programmer make this time complexity better?

Avoid collisions in general which you can do by

• making good hashing functions

• larger underlying array storage in HashMap

• Good average case —> well' distributed allowing it constant access time of arrays

What is the purpose of a mover Node?

a temporary variable that helps you move through a linkedList without changing the original head of a node

If you are provided only the same code that I have written up to minute 5:20 of this video, you should be able to construct a LinkedList in main from that code; and add, insert, and remove items from it; and also draw the related LinkedList in memory.  (I demonstrate all this from minute 6:04 - 30:40 of the video.)

//Add at beginning

Node<String> n0 = new Node<>("Avery");

n0.setNext(myLL.head);

myLL.head = n0;

//Add at position 3

Node<String> insert = new Node<>("Cooper");

Node<String> mover = myLL.head;

int num = 0;

while(num < 2) {

mover =  mover.getNext();

num++;

}

insert.setNext(mover.getNext());

mover.setNext(insert);

//Remove at position 3

mover = myLL.head;

num = 0;

while (num < 2) {

mover = mover.getNext();

num++;

}

mover.setNext(mover.getNext().getNext());

//Remover last item

mover = myLL.head;

num = 0;

while (num < 2) {

mover = mover.getNext();

num++;

}

mover.setNext(null);

myLL.last = mover;

Node<String> lastAdd = new Node<>("Daniela");

myLL.last.setNext(lastAdd);

myLL.last = lastAdd;

*/

Starting at minute 30:40 of the video to the end, I show how to write the LinkedList method add that makes the adding of new values to a LinkedList more convenient for the programmer.  You should also be able to implement LinkedList methods like add.  

public class MyLinkedList<E> {

Node<E> head;

Node<E> last;

int size;

public MyLinkedList() {

this.head = null;

this.last = null;

this.size = 0;

}

public void add(E data) {

Node<E> n = new Node<>(data);

if(size == 0) {

this.head = n;

this.last = n;

} else {

this.last.setNext(n);

this.last = n;

}

this.size++;

}

}