Transcript linked-list

Linked Lists
CSC 172
SPRING 2002
LECTURE 3
Data Structures?
 We
make distinctions in the level of abstraction
 Abstract
Data Type (ADT) - functionality/behavior
 Dictionary,
 Data
Model – organization
 List,
 Data
Stack, Queue
Tree, Graph
Structure – implementation
 Array,
Linked list, BST, Adjacency Matrix
The Dictionary ADT
 Computer
programs commonly maintain a set of
values where we wish to
 Insert
elements into the set
 Delete Elements from the set
 Look up elements (see if they are currently in the set)
 There
are lots of ways to implement this
 Some are more efficient than others
The Dictionary Interface
public interface Dictionary {
public abstract void insert(Object o);
public abstract void delete(Object o);
public abstract boolean lookup(Object o);
}
List Data Model
 A list
is a finite sequence of zero or more elements
 Grocery
list
 Laundry list
 (a1,a2,…,an)
 Formally,
 Empty,
we can think of a list as either
or
 An element followed by a (possibly empty) list
Lists
 Empty
(no elements)
 An element (head), followed by a list (tail)
 Head
sometimes called CAR
 Tail sometimes called CDR
 Length
0
of a list is
for an empty list
 1 + length(tail) for a non-empty list
How can we implement this?
 We
can implement a Dictionary ADT . . .
using a list data model . . .
with an array data structure . . .
or a linked-list data structure.
Arrays
An array is a collection of data items of the same type
 Every element of the collection can be accessed
separately.
Object [] data = new Object[10];

Array Implementation
public class myInfo implements Dictionary{
private int defaultCapacity = 100, length = 0;
private Object[] datum;
public myInfo() {
datum = new Object[defaultCapacity];
}
public myInfo(int initCapacity) {
datum = new Object[initCapacity];
}
Implementation
public class myInfo implements Dictionary{
private int defaultCapacity = 100, length = 0;
private Object[] datum;
public myInfo() {
datum = new Object[defaultCapacity];
}
public myInfo(int initCapacity) {
datum = new Object[initCapacity];
}
Insert
Is this ok?
public void insert (Object o) {
datum[length++] = o;
}
What is the run time?
What if I have more than 100 elements?
Expand
private void expand(){
Object[] tempData =
new Object[datum.length * 2];
for (int j = 0 ; j<length;j++)
tempData[j] = datum[j];
datum = tempData;
}
So, what is the runtime of this
Insert
Better?
public void insert (Object o) {
if (length >= (datum.length –1)) expand();
datum[length++] = o;
}
This is what the Java class Vector gets you
What is the (worst case) run time, now?
Self-referential data types
class Node {
private Object data;
private Node next;
}
data
next
// the “data”
// the “link”
Linked List
 A linked
list “has-a” reference to a node
 The
“head” of the list
 The ending node has “null” for the next
head
data
next
data
Next
data
Next
null
Linked-List Implementation
public class myInfo implements Dictionary{
private int length = 0;
private Node head = null;
Adding a first node
Adding a first node
public void insert(Object obj){
Node newLink = new Node();
newLink.data = obj;
newLink.next = head;
head = newLink;
}
What is the run time of this?
Lookup: Array
public boolean lookup(Object o){
for (int j = 0 ; j < length;j++)
if (datum[j].equals(o)) return true;
return false;
}
Run time?
Lookup: Linked List
public boolean lookup(Object o){
Object temp = head;
while (temp != null){
if ((temp.data).equals(o)) return true;
temp = temp.next;
}
return false;
}
Run time?
Lookup: Linked List, recursive
public boolean lookup(Object o){
return lookupNode(o,head);
}
public boolean lookupNode(Object o, Node n){
if (n == null) return false;
else if((n.data).equals(o) return true;
else return lookupNode(o,n.next);
}
Run time?
Deleting a node from a List
Delete: Linked List, recursive
public boolean delete(Object o){
return deleteNode(o,head);
}
Delete: Linked List, recursive
public void deleteNode(Object o, Node n){
if (n == null) return ;
if (n.next == null) return;
else if(((n.next).data).equals(o)) {
n.next = (n.next).next
return ;
}
else return deleteNode(o,n.next);
}
Run time?
Delete: Array
 We
have to look it up O(n)
 Deletion is setting it to null
 But, we have to “shift” all the remaining elements.
Delete: Array
public void delete(Object o){
for (int j = 0 ; j < length;j++)
if (datum[j].equals(o)) {
for (int k = j; k<(length-1);k++)
datum[k] = datum[k+1];
return;
};
}
Run time?
Compare (worst case) Run Time
(what about space?)
ARRAY
LINKED-LIST
Insert
N (in case of
expansion)
1
Lookup
N
N
Delete
N (lookup + shift)
N (for lookup)
Workshop sing-up
. The coefficient for the workshop differential is
positive and significant. On average, each
additional workshop attended in CSC 172
increases the final grade point by 0.19. In
substantive terms, this means that a student who
attends five additional workshops in CSC 172
should expect his/her grade to increase by almost
one full letter grade.