LinkedList

Question 1

What interface does LinkedList implement?

Answer 1

LinkedList implements List, which extends from Collection

Question 2

What are the LinkedList methods?

Answer 2

add(x) = adds item x to the

listset(x,y) = set location x to the value y

get(x) = get the item at location x

size() = returns the # of items in the list

remove() = removes an item from the list

clear() = removes all items from the list

Question 3

What is a LinkedList when implementing ListNode

?

Answer 3

A linked list is a group of nodes. Each node contains a value and a refence to the next node in the list.

Question 4

What is a Node?

Answer 4

A node typically has a data component and a reference to the next node.

Question 5

What would be the output of:
ListNode x = new ListNode("10",     new ListNode("11",     new ListNode("12",null)));
out.println(x.getValue());
out.println(x.getNext().getNext().getValue());
out.println(x.getNext().getValue());

Answer 5

10
12
11

Question 6

How do you remove the first node?

Answer 6

front = front.getNext();

this shifts the list to the next node

Question 7

What is a DoubleNode?

Answer 7

A doubly node typically has a data component and a reference to the next node and the previous node.

Each node can go both ways

Doubly nodes can be used to make a circular linked list where the front points at the back and vice versa.

Question 8

What is the Big-O Notation?

Answer 8

Big-O notation is an assessment of an algorithm’s efficiency. Big-O notation helps gauge the amount of work that is taking place.

Question 9

List all the Big-O Notations to the LL commands:

Answer 9

traverse all nodes = O(N)

search for an item = O(N)

remove any item = O(N)

location unknown get any item = O(N)

location unknown add item at the end = O(N)

add item at the front = O(1)