Transcript COMP 103 Lecture 1 - School of Engineering and Computer Science

COMP 103
Linked List
 Marcus Frean, Lindsay Groves, Peter Andreae, and John Lewis, and Thomas Kuehne, VUW
2016-T2 Lecture 11
Thomas Kuehne
School of Engineering and Computer Science, Victoria University of Wellington
RECAP-TODAY
2
RECAP

Linked Structures: LinkedNode

Linked nodes support building linked lists


various useful list operations can be added to LinkedNode
But…

what about removing the first node in a list?

should clients always need to check for “null”?

how to avoid expensive searching for nodes?
TODAY

Explicitly representing a Linked List

Implementing other useful containers with LinkedNode
LinkedList
3

A linked list should support operations such as “isEmpty()”
and “removeFirst()”


Linked nodes cannot support these goals directly
Solution: Use a LinkedList class as a “wrapper” class



LinkedList uses LinkedNode much like ArrayList uses a Java array
LinkedList delegates many operations to LinkedNode
Special cases are dealt with by LinkedList
LinkedList
uses
Internal data structure:
Linked Node
A
B
My
Program
_______
________
______
uses
ArrayList
Internal data structure:
Array
A
B
Making a LinkedList class
4
class LinkedList <E> {
Underlying data structure
private LinkedNode<E> head = null;
Direct implementation
public void printList( ) {
for (LinkedNode<E> rest = head; rest != null; rest = rest.next() )
System.out.printf("%s, ", rest.get());
}
Delegation to LinkedNode behaviour
public void printList( ) {
if (head != null)
head.printAll();
LinkedList
}
…
}
head
LinkedNode
LinkedNode
Inserting
5
/** Inserts the value at position n in the list (counting from 0)
Assumes list is not empty, and 0 <= n < length */
public void insert (E item, int n) {
if ( n == 0 ) {
head = new LinkedNode<E>(item, head);
} else
insertItemAtPos(item, n, head); // c.f., L10, slide #16
}
Alternatively, delegate to LinkedNode:
head.insertItemAtPos(item, n);
head
Q
W
E
R
T
Types of Lists: ArrayLists, LinkedLists
6
<<interface>>
Collection
Maintaining order
& growing
is expensive
Indexing
is expensive
<<interface>>
List
<<abstract class>>
AbstractList
<<class>>
<<abstract class>>
ArrayList
AbstractSequentialList
underlying data structure:
ARRAY
<<class>>
LinkedList
underlying data structure:
LINKED NODE
Cost of Indexing?!
7

Random access of linked nodes is costly

What to do about it?
It’s a feature, not a bug! 
 Solution
1: Do not allow it
(→ Stack)
 Solution
2: Restrict it
(→ Queue)
 Solution
3: Support it to some extent
(→ CursorList)
No Random Access: e.g., Stack
8
Stack
top

Which end of the list to use for the top element?
 need
for efficiently adding and removing elements
Restricted Access: e.g., Queue
9
Queue
front
back

Which end of the list to use for enqueuing elements?

How to efficiently dequeue elements?
Some Support: e.g., Cursor List
10
CursorList
cursor
head

Maintaining a current manipulation point
 not
as flexible as random access
 sometimes sufficient
 always efficient!

Is this a full replacement for an iterator?