Linked List

• Data organized into nodes.
• Each node has a data item and a link to the next node.
• Last node links to null.

Linked List

Look at the Node class in the starter code

Exercise: Create a “singly” linked list class. It should store a reference to the “head” node. First just implement the following operations:

• add to the beginning of the list (call this addFirst)
• find the size of the list
• get the first element of the list (the integer in the “head” node).

Test out your class in a main method.

Running time

• What is the running time of the addFirst method?
• What is the running time of the size method? Is there any way we can improve it?

The implementation details of the class really do matter here. If you design the class well, you can support this operation in constant time. How?

Exercise

Implement the following methods. They should run in \(O(1)\) time:

• addLast (adds an integer to the end of the list)
• getFirst (gets the first integer in the list)
• getLast (gets the last integer in the list)

get method

To truly have a list structure, we should be able to access any element of the list. For example, if I add \(5, 10, 3, 7\) to my list, I should be able to call \(list.get(1)\) and it should return \(10\).

• Running time (Big Oh) of the ArrayList’s get?
• Best running time for get in our linked list class? Pseudocode?

In general, a structure in which we can access the \(i^{\text{th}}\) element in constant time is said to support random access.

(Binary tree with root 2)