Transcript Lec. notes

ISOM
MIS 215 Module 1 –
Unordered Lists
Where are we?
ISOM
MIS215
Basic Algorithms
Introduction List Structures
Search
Techniques
Intro to
Java, Course
Java lang.
basics
Linked
Lists
Arrays
Sorting Techniques
Hashtables
Binary Search
Stacks,
Queues
Advanced structures
Graphs,
Trees
Bubblesort
Fast Sorting algos
(quicksort, mergesort)
Newbie
Programmers
Designers
Developers
Professionals
2
Today’s buzzwords
ISOM
• Unordered Lists
 Lists that are not REQUIRED to be ordered to be functional
 That does not mean that they cannot be ordered if
necessary
• Linked Lists
 A data structure where the lists are implemented using a
dynamically allocated structure, with nodes and links to the
next nodes.
• Java References
 A “reference” in Java is simply a variable of an object type
 All objects are dynamically allocated at runtime (with “new”)
 Its like a pointer, but still not like a pointer 
Overview
ISOM
• List introduction
• List specifications
• List implementations




•
•
•
•
Contiguous
Simply Linked
Simply Linked with Position Pointer
Doubly Linked
Strings
Application: Text Editor
Linked Lists in Arrays
Application: Generating Permutations
Unordered Lists
ISOM
• Lists that do not have to be ordered to be
functional
• Can be ordered if necessary
• Examples?
The Specifications of
General Lists
ISOM
Basic operations: clear, isListEmpty,
isListFull, size, traverse
List operations: insert, remove, find.
The Insert operation: insert(Itemtype x)
OR
insert(int p, Itemtype x)
Pre: The list has been created, and is not full, x is a valid list
entry, and 0<=p<=n, where n is the number of entries in list.
Post: x has been inserted into position p in list; the entry
formerly in position p (provided p<n) and all later entries
have their position numbers increased by 1.
Our List Skeleton (for now)
ISOM
/**
* Our first List class. Notice the Javadoc style comments
*/
public class MyList {
/**
* The MyList Constructor - we may need variants later
*/
public MyList() {}
/**
* The clear operation - removes all entries from the list
*/
public void clear() {}
/**
* Check if the list is empty
*/
public boolean isListEmpty() {}
/**
* Check if the list is full
*/
public boolean isListFull() {}
/**
* What is the current size of the list? Note that this is
* different from the maximum possible size.
*/
public int size() {}
/**
* Traverse the list - maybe just print all items in the screen
*/
public void traverse() {}
}
The Implementations of
General lists
ISOM
• Contiguous implementation
 using arrays
 insertions and deletions are done with
movement of data entries
• Linked implementations
 singly linked lists
• allocating memory dynamically
• insertions and deletions are done by changing
references
 doubly linked lists
• using two references for each entry
Lets try arrays first!
ISOM
• What variables should MyList need?
• What possible variations of the
constructor?
What would be useful to know when
the list is being created?
What would you allow your users to
set once for the life of the instance?
Implementing List as Array
ISOM
• CFC on the MyList class
• How do we implement clear?
• How do we implement isListEmpty?
• How do we implement isListFull?
Now for the List operations
ISOM
• insert
• remove
• find
A singly linked list
ISOM
• Each node in the list contains...
data (we’ll use only integers, as usual)
a link to the next node
• in Java, we’ll call this a reference
• (if you know C, it’s a pointer)
• Here’s a picture....
Links (contd.)
ISOM
data
next
node

Class Design
ISOM
Our first UML in MIS215
LinkedList
Node First
Node
0..M
int Item
Node Next
Insertion on a Linked List
ISOM
Stacks
Stacks
are
are
lists
lists
simple
Deletions on a Linked List
ISOM
Stacks
are
but
Stacks
are
but
?
structures
simple
important
data
structures
simple
important
data
Doubly Linked List
ISOM
Comparison of the
Implementations
ISOM
• In processing a continuous list with n entries:
 insert and remove require O(n) time
 clear, isListEmpty, isListFull, size operate in constant time.
• We call this O(1) complexity
• In processing a linked list with n entries:





Complexity of insert?
Complexity of remove?
Complexity of size?
Complexity of isListEmpty?
Complexity of isListFull?
Complexity Analysis
ISOM
Complexity of _____________
A. O(1) … i.e., Constant time
B. O(n) … i.e., proportional to #items
C. More than O(n)?
Build this table for
unordered lists
ISOM
Operation
Array
implementation
Linked List
Implementation
create/constructor
O(1)
O(1)
size
clear
traverse
isListFull
isListEmpty
insert
remove
find
findAt*
Quick Quiz: Accessing items
in the chain
ISOM
• In an array, how do we access an item in the
array (say, the 4th item)?
• If we have a chain (i.e., linked list), how do we
get to the 4th item in the chain?
Analysis of the
Implementations
ISOM
• Contiguous storage is generally preferable:
 when the structures are individually small
 when the size of the list is known when the program is
written
 when fewer insertions or deletions need to be made
except at the end of the list
 when random access is important.
• Linked storage proves superior:
 when the structures are large
 when the size of the list is not known in advance
 when flexibility is needed in inserting, deleting and rearranging the entries.