Transcript 05-linkedlist

TCSS 143, Autumn 2004
Lecture Notes
Implementation of Array Lists
and Linked Lists
1
Java's List interface: review

Java has an interface java.util.List to
represent a list of objects. It adds the
following methods to those in Collection:
public void add(int index, Object o)
Inserts the specified element at the specified position in this list.
public Object get(int index)
Returns the element at the specified position in this list.
public int indexOf(Object o)
Returns the index in this list of the first occurrence of the
specified element, or -1 if the list does not contain it.
2
List interface, cont'd.

More java.util.List methods:
public int lastIndexOf(Object o)
Returns the index in this list of the last occurrence of the specified
element, or -1 if the list does not contain it.
public Object remove(int index)
Removes the object at the specified position in this list.
public Object set(int index, Object o)
Replaces the element at the specified position in this list with the
specified element.
3
ArrayList implementation



Let's examine instructor's provided
IntArrayList class, to get an idea of how
ArrayList works
An IntArrayList stores a list of ints and
mimics many of the methods of
java.util.ArrayList
simpler to examine than a real ArrayList,
but limited (cannot be used for other data
types)
4
reminder: ArrayList problems





an insertion into a full list causes a large
reallocation
an insertion to the front forces us to "slide"
down the subsequent items
a removal also forces us to "slide" down
subsequent items
still need to use indexes/subscripts a lot
the syntax for using it is somewhat ugly
5
The underlying issue


the elements of an ArrayList are too tightly
attached; can't easily rearrange them
can we break the element storage apart into a
more dynamic and flexible structure?
6
Idea: a list of linked nodes



create a special Node object that represents
one storage slot to hold one element of the list
each node will keep a reference to the node
after it (the "next" node)
the last node will have next == null
(drawn as / ), signifying the end of the list
7
A linked list

linked list: a collection that provides the list
operations named previously, implemented
using a linked sequence of nodes

the list only needs to keep a reference to the first
node (we might name it myFront)
8
LinkedList

Class java.util.LinkedList implements
List using linked nodes as the internal
implementation
9
Some list states of interest



empty list
(myFront == null)
list with one element
list with many
elements
10
Let's draw them together...

an add operation





at the front, back, and middle
a remove operation
a get operation
a set operation
an index of (searching) operation
11
Node implementation (int)
/* Stores one element of a linked list. */
public class IntNode {
public int data;
public Node next;
public Node(int data) {
this(data, null);
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
12
Linked list implementation
/* Models an entire linked list. */
public class IntLinkedList {
private Node myFront;
public IntLinkedList() {
myFront = null;
}
/* Methods go here */
}
13
Linked list methods
// inserts given value at front
public void addFirst(int value)
// returns true if no nodes are in list
public boolean isEmpty()
// returns number of elements
public int size()
14
Linked list methods, cont'd.
// returns string representation of list
public String toString()
// appends given val at end
public void addLast(int value)
// inserts given value at given index
public void add(int index, int value)
15
Linked list methods, cont'd.
// returns value at given index
// (exception when index is OOB)
public int get(int index)
// sets element at given index to
// have the given value, and returns it
// (exception when index is OOB)
public int set(int index, int value)
16
Linked list methods, cont'd.
/ returns index of value in list;
// -1 if value is not in the list
public boolean indexOf(int value)
// returns true if value is in list
public boolean contains(int value)
// removes all values from list
public void clear()
17
Linked list methods, cont'd.
// removes and returns front value
// (exception when list is empty)
public int removeFirst()
// removes and returns rear value
// (exception when list is empty)
public int removeLast()
// removes,returns value at index
// (exception when index is OOB)
public void remove(int index)
18
Algorithm efficiency, in brief

operations that always execute a fixed number
of statements are called "constant time"
operations


operations that take longer to perform if our list
is longer are called "linear time" operations


often called O(1) : "big-Oh of 1" or "order of 1"
often called O(n) : "big-Oh of n" or "order of n",
where n means the size of the list
O(n) operations are slower and we want to
avoid them when we can
19
Which methods are O(n)?
METHOD
addFirst(int)
isEmpty()
size()
toString()
addLast(int)
add(int, int)
get(int)
set(int, int)
RUNTIME (Big-Oh)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
20
Which methods are O(n)?
METHOD
indexOf(int)
contains(int)
clear()
removeFirst()
removeLast()
remove(int)


RUNTIME (Big-Oh)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
= O(_____)
Can we categorize which operations are slow?
What does this say about how to use our list?
21
A particularly slow idiom
// print every element of the list
for (int i = 0; i < list.size(); i++) {
int element = list.get(i);
System.out.println(i + ": " + element);
}

This code executes an O(n) operation (get)
every time through a loop that runs n times!


Its runtime is O(n2), which is much worse than O(n)
this code will take prohibitively long to run for large
data sizes
22
The problem of position



The code on the previous slide is wasteful
because it throws away the position each time
it would be much better if we could somehow
keep the list in place at each index as we
looped through it
Java uses special objects to represent a
position of a list as it's being examined...

these objects are called "Iterators"
23
Iterators in Java

interface java.util.Iterator



public boolean hasNext()
Returns true if there are more elements to see.
public Object next()
Returns the next object
in this collection.
Throws an exception
if no more elements
remain.
public Object remove()
Deletes the element that was
last returned by next.
24
Iterator usage example
ArrayList names = new ArrayList();
//...
// print every name in the list, in upper case
Iterator itr = myList.iterator();
while (itr.hasNext()) {
String nextElement = (String)itr.next();
System.out.println(nextElement.toUpperCase());
}
25
Benefits of iterators


speed up iteration through linked lists
provide a unified way to examine all elements
of a collection



every collection in Java has an iterator method
don't need to look up that collection's method
names to see how to use it
removes the hassle of managing indexes and
worrying about out-of-bounds problems when
examining a list's elements in order
26
An optimization: myBack

add a myBack pointer to the last node

what benefits does this provide?


which methods' Big-Oh runtime improves to O(1)?
what complications does this add to the
implementation of the methods of the list?
27
A variation: dummy header

dummy header: a front node intentionally left
blank



myFront always refers to dummy header
(myFront will never be null)
requires minor modification to many methods
surprisingly, makes implementation much easier
28
References

Koffman/Wolfgang Ch. 4, pp. 193-248
29