Linked List

Question 1

What is a linked list?

Answer 1

linked list diagram

ordered collection of data = node with data and reference to the next node;
order won’t change
head, node, data, reference to the next node, tail
Create 2 separate nodes and point one to next.

Images from Algorithms - linked lists doc

Question 2

Coding exercise - linked lists.

Answer 2

Use new Node to set up node one and node 2

Use a constructor to set up class Node
class Node {

}

class LinkedList {

}
Why set to null instead of undefined?
undefined means the data hasn’t been set
null means it has been set to undefined

linkedList only knows about the first node = head, if you want info about other nodes, you have to crawl up the linked list

Use a constructor to create a class LinkedList and set the head to point to a node

Images from Algorithms - linked lists doc

Question 3

Linked List’s InsertFirst

Answer 3

create a head
create a node
break link on head with the class
move new node to be first and link it to tail (stick it to the front) - meaning before the former head
link the class with the head (update the head reference)

Images from Algorithms - linked lists doc

Question 4

sizing a list

Answer 4

Images from Algorithms - linked lists doc

Question 5

linkList’s methods: getFirst, getLast, clear, removeFirst

Answer 5

getFirst{
return this.head
{

getLast{}
Images from Algorithms - linked lists doc

clear(){
This.head = null
}

removeFirst()

Question 6

Remove last

Answer 6

Images from Algorithms - linked lists doc

Question 7

Insert last

Answer 7

Images from Algorithms - linked lists doc