Linked List

Question 1

Define link list

Answer 1

An abstraction of a list

Question 2

Arrays use ______ memory

Answer 2

Static memory
- Can’t grow/shrink (fixed)
- Contiguous Memory!

Question 3

What is the BEST aspect of Arrays/ArrayLists

Answer 3

Contiguous Memory! (direct access)

Question 4

What is the WORST aspect of Arrays/ArrayLists

Answer 4

Shifting cost! O(n)

Question 5

What is the BEST aspect(s) of Linked List

Answer 5

Dynamic & Shifting cost! O(1)

Question 6

What is the WORST aspect of Linked List

Answer 6

Not contiguous (no direct access)

Question 7

What is the ONE job of the head of the list?

Answer 7

to POINT to the first part of the linked list!! If we ever lose the head- we will lose the list.

Question 8

What does the class LinkedList do?

Answer 8

Controls the list via methods! And holds the head!

Question 9

What does the class LLnode do?

Answer 9

Creates the object to be stored (the data) and the next field that links the nodes (the next)

Question 10

QUICK! How do we traverse a linked list if we want to adjust/print every node?

Answer 10

LLnode helpPtr = head;
while(helpPtr != null){
System.out.println(helpPtr.getData());
helpPtr = helpPtr.getNext();
}

Question 11

How do we insert a new node into a linked list?

Answer 11

1. Make the new LLnode object you want to insert.
2. Determine the insertion point
   
   • helpPtr will point to the insertion points predecessor *
3. Point to the new nodes successor
4. Point to the new nodes predecessor

*This means helpPtr.next would access the successor!

Question 12

How do we delete a node from a linked list?

Answer 12

1. Identify what node you are looking to delete
2. if its the first node- we can just point head to head.next
3. else? helpPtr should stop at the PREDECESSOR! Meaning when we loop- check helpPtr.next.data!

Question 13

Describe the differences between a Linked list and a Doubly linked list:

Answer 13

Linked List:
- ONLY points to next
Doubly Linked List:
- Has access to PREVIOUS and NEXT!

Question 14

In a doubly linked list how would we insert the object Sharron between Harry and Sam?
<- <- helpPtr*
[Harry] -> -> [Sam]*
|
[Sharron]

IN ENGLISH!

Answer 14

1. Sharron -> Sam
2. Sharron -> Harry
3. Harry -> Sharron
4. Sam -> Sharron

Question 15

In a doubly linked list how would we insert the object Sharron between Harry and Sam?
<- <- helpPtr*
[Harry] -> -> [Sam]*
|
[Sharron]

IN pseudo-CODE!

Answer 15

1. newNode.next = helpPtr
2. newNode.prev = helpPtr.prev
3. helpPtr.prev.next = newNode
4. helpPtr.prev = newNode

Question 16

In a doubly linked list how would we delete the object Harry?

         <-  helpPtr*  <- 

[Bob] -> [Harry]* -> [Sharron]

IN ENGLISH!

Answer 16

1. Bob -> Sharron
2. Sharron -> Bob

Question 17

In a doubly linked list how would we delete the object Harry?

         <-  helpPtr*  <- 

[Bob] -> [Harry]* -> [Sharron]

IN pseudo-CODE!

Answer 17

1. helpPtr.prev.next = helpPtr.next
2. helpPtr.next.prev = helpPtr.prev

Question 18

In a circular linked list… we need a ____.

Answer 18

SIZE! Because we will never visit a null node! Gotta know when we hit the technical ‘end’.