Transcript An Example
Programming and Problem Solving
With Java
Chapter 12: Lists
Writing ListClasses
Example: Infinite Precision Arithmetic
Example: Sorting a Lsit
Example: A Set Type
Doubly Linked Lists
Computer Security
Copyright 1999, James M. Slack
Introduction
Dynamic data structure
Grows and shrinks as program runs
Example: Java’s standard Vector class
Lists
Used often in everyday life (groceries, to-do, …)
Will also look at sets in this chapter
Dynamic data structures in later chapters
Stacks
Queues
Trees
Programming and Problem Solving With Java
2
Introduction
Characteristics of lists
There’s a first element
There’s a last element
All others have predecessor and successor
Operations on lists
Add element
Delete element
Search for element
Sort the elements
Programming and Problem Solving With Java
3
Writing List Classes: CharList
Character list class
Allows adding and deleting characters from either end
Operations
toString
insertFirst
insertLast
empty
removeFirst
removeLast
Programming and Problem Solving With Java
Returns contents in a string.
Put new character value at beginning
Put new character value at end
Returns true if empty
Remove node at beginning, return value
Remove node at end, return value
4
Writing List Classes: CharList
Short example
// Short demonstration of how to use the CharList
// class
import CharList;
public class DemoCharList
{
public static void main(String[] args)
{
CharList myCharList = new CharList();
[H i ! ]
Removed H
[i ! ]
// Insert some characters
myCharList.insertFirst('i');
myCharList.insertLast('!');
myCharList.insertFirst('H');
// Use the toString() method
System.out.println(myCharList);
// Remove character
System.out.println("Removed "
+ myCharList.removeFirst());
}
}
// Use the toString() method again
System.out.println(myCharList);
Programming and Problem Solving With Java
5
Writing List Classes: CharList
Longer example (uses TextMenu class)
//
//
//
//
//
This program lets you add characters onto
either end of a linked list, and remove them from either
end. It makes sure you don't try to remove characters
from an empty list. This is a demonstration of how to use
the CharList class.
import Keyboard;
import TextMenu;
import CharList;
Te xtM e nu
public class CharListTest extends TextMenu
{
static final int ADD_FIRST_COMMAND = 1;
static final int ADD_LAST_COMMAND = 2;
static final int REMOVE_FIRST_COMMAND = 3;
static final int REMOVE_LAST_COMMAND = 4;
CharList
CharListTe s t
// Constructor - set up menu for the editor
public CharListTest()
{
super("Character List Menu");
list = new CharList();
addSelection("Add first", '1', ADD_FIRST_COMMAND);
addSelection("Add last", '2', ADD_LAST_COMMAND);
addSelection("Remove first", '3', REMOVE_FIRST_COMMAND);
addSelection("Remove last", '4', REMOVE_LAST_COMMAND);
addSelection("Quit", '5', TextMenu.QUIT);
}
Programming and Problem Solving With Java
6
Writing List Classes: CharList
// Event dispatcher
public int handleEvent(int event)
throws java.io.IOException
{
switch (event)
{
case ADD_FIRST_COMMAND:
list.insertFirst(Keyboard.readChar(
"Enter character to add to beginning: "));
break;
case ADD_LAST_COMMAND:
list.insertLast(Keyboard.readChar(
"Enter character to add to end: "));
break;
case REMOVE_FIRST_COMMAND:
if (list.empty())
{
System.out.println("List is empty!");
}
else
{
System.out.println("Removed " + list.removeFirst()
+ " from beginning of list");
}
break;
case REMOVE_LAST_COMMAND:
if (list.empty())
{
System.out.println("List is empty!");
}
else
{
System.out.println("Removed " + list.removeLast()
+ " from end of list");
}
break;
}
System.out.println("List is now: " + list);
return event;
}
Programming and Problem Solving With Java
7
Writing List Classes: CharList
// Instance variables
CharList list;
public static void main(String[] args)
throws java.io.IOException
{
CharListTest listExample = new CharListTest();
}
}
listExample.run();
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 1
Enter character to add to beginning: b
List is now: [b ]
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 1
Enter character to add to beginning: a
List is now: [a b ]
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 2
Enter character to add to end: c
List is now: [a b c ]
Programming and Problem Solving With Java
3) Remove first
3) Remove first
3) Remove first
8
Writing List Classes: CharList
CharList is linked structure: each character on the
list keeps track of its successor
CharListNode is separate class
Space for the character
Reference to next character in list
Data value
'A'
Reference to next
node in the list
Last node references null (special value)
Programming and Problem Solving With Java
9
Writing List Classes: CharList
CharListNode class
class CharListNode
{
// Constructor
public CharListNode(char item, CharListNode next)
{
setItem(item);
setNext(next);
}
// getItem: Returns the item value
public char getItem() { return item; }
Data value
'A'
// getNext: Returns the next item
public CharListNode getNext() { return next; }
// setItem: Sets the item to the given value
public void setItem(char item)
{
this.item = item;
}
Reference to next
node in the list
// setNext: Sets the next item to the given object
public void setNext(CharListNode next)
{
this.next = next;
}
// Instance vaiables
private char item;
private CharListNode next;
Programming}and Problem Solving With Java
10
Writing List Classes: CharList
CharList class
References first and last nodes of the list
Reference
to first node
CharList
CharListNode
'A'
CharListNode
'B'
CharListNode
'C'
CharListNode
'D'
null
Reference
to last node
Number
of nodes
4
Constructor
// Default constructor
public CharList()
{
first = null;
last = null;
numNodes = 0;
}
Programming and Problem Solving With Java
Reference
to first node
Makes empty
CharList
Reference
to last node
Number
of nodes
CharList
null
null
0
11
Writing List Classes: CharList
Inserting a new node: insertFirst()
// insertFirst: Inserts a new item at the beginning of the list.
public void insertFirst(char item)
{
CharListNode newNode = new CharListNode(item, first);
}
newNode
numNodes++;
first = newNode;
if (last == null)
{
// Special case: An empty list.
// This new node is the last node in the list.
last = newNode;
}
'E'
After creating
the new node
'A'
'B'
4
Programming and Problem Solving With Java
newNode
'C'
'D'
null
'E'
After making
the new node
the first node
'A'
'B'
'C'
'D'
5
12
null
Writing List Classes: CharList
Inserting a new node: insertLast()
// insertLast: Inserts a new item at the end of the list
public void insertLast(char item)
{
CharListNode newNode = new CharListNode(item, null);
}
numNodes++;
if (first == null)
{
// Special case: this node is the first node in the list.
first = newNode;
}
else
{
// General case: this is not the only node in the list.
// Make the last node point to this one and make this
// the new last node.
last.setNext(newNode);
}
last = newNode;
After making
the new node
the last node
After creating
the new node
newNode
'E'
'A'
'B'
'C'
4
Programming and Problem Solving With Java
'D'
null
newNode
'E'
null
'A'
'B'
'C'
'D'
5
13
Writing List Classes: CharList
Removing a node:
removeFirst()
Before
removing first
node
node
'A'
'B'
'C'
'D'
null
'D'
null
'D'
null
4
Link around
first node
node
'A'
'B'
'C'
4
Delete first
node
node
'B'
Programming and Problem Solving With Java
3
'C'
14
Writing List Classes: CharList
Removing a node: removeFirst()
// removeFirst: Remove the first element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node, unless
//
deleting the last node. In that case, sets
//
currentNode to previous node.
// Note: The list cannot be empty
public char removeFirst()
{
Debug.assert(!empty(),
"CharList.removeFirst(): List is empty");
CharListNode node = first;
// Remove the first node from the list.
first = first.getNext();
if (empty())
{
// Special case: this is the only node in the list.
last = null;
}
numNodes--;
}
// Return the value of the removed node.
return node.getItem();
Programming and Problem Solving With Java
15
Writing List Classes: CharList
Before
removing last
node
Removing a node:
removeLast()
'A'
node
'B'
'C'
'D'
null
'D'
null
'D'
null
4
Find the node
before the last
'A'
previousNode
'B'
node
'C'
4
Take last node
out of list
'A'
Programming and Problem Solving With Java
3
previousNode
'B'
'C'
node
null
16
Writing List Classes: CharList
Removing
a
node:
removeLast()
// removeLast: Remove the last element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node, unless
//
deleting the last node. In that case, sets
//
currentNode to previous node.
// Note: The list cannot be empty
public char removeLast()
{
Debug.assert(!empty(), "CharList.removeLast(): List is empty");
CharListNode node = last, previousNode;
if (last == first)
{
// Special case: only one node in the list
last = first = null;
}
else
{
// General case: find second-to-last node
previousNode = first;
while (previousNode.getNext() != last)
{
previousNode = previousNode.getNext();
}
// Make second-to-last the last node
previousNode.setNext(null);
last = previousNode;
}
}
numNodes--;
// Return the value of the removed node.
return node.getItem();
Programming and Problem Solving With Java
17
Writing List Classes: CharList
empty(), count(), toString()
// empty: Returns true if the list is empty
public boolean empty()
{
return first == null;
}
// count: Returns the number of elements in the list
public int count()
{
return numNodes;
}
// toString: Returns a string representing the contents of
//
the list
public String toString()
{
CharListNode node = first;
String result = "[";
while (node != null)
{
result = result + node.getItem() + " ";
node = node.getNext();
}
}
return result + "]";
Programming and Problem Solving With Java
18
Writing List Classes: CharList
Problems with the CharList class
Can’t tell if particular value in the list (without displaying
the list and examining the output)
Can't insert a value in the middle
Can't remove a value from the middle
Can't traverse the list, except to display every element
Can't get a value from the list without removing it
Can't change a value in the list without removing it and
inserting the new value
Can only store characters
Programming and Problem Solving With Java
19
A General List Class
Additional features over CharList:
Store into the middle (not just ends)
Remove from middle
Check whether a particular value is in the list
Get values of elements inside the list
Store any object -- not just characters
To store and retrieve elements from middle of list
Need way to refer to list position
Will add current node marker
Will have methods for moving current node marker
Programming and Problem Solving With Java
20
A General List Class
List operations
append: Attach another list to end
count: Return number of nodes
toString: Return String version of list’s contents
find: Search for value. If in list, set the current node there
get: Return value in current node
goFirst: Change current node to beginning
goLast: Change current node to end
goNext: Change current node to next node
goPrevious: Change current node to previous node
insert: Put new value after current node
insertFirst: Put new value at beginning
Programming and Problem Solving With Java
21
A General List Class
List operations (continued)
insertLast: Put new value at end
isDefined: Return true if current node defined
empty: Return true if list empty
isFirst: Return true if current node is first node
isLast: Return true if current node is last node
put: Change value of current node
remove: Remove current node, return its value
removeFirst: Remove node at beginning of the list, return
its value
removeLast: Remove node at end of list, and return its
value
Programming and Problem Solving With Java
22
A General List Class: Line Editor
Today, most editors are full-screen
Move cursor with keys or mouse
Type at position of cursor
Older style: line editor
Make changes to one line at a time
Must specify line to change with a command
Not as easy to use as full-screen editor
Much easier to write, though
Programming and Problem Solving With Java
23
A General List Class: Line Editor
Example of line editor: MS-DOS edlin
C:\>edlin Hello.java
New file
*I
1:*class Hello
2:*{
3:* public static void main(String[] args)
4:* {
5:*
System.out.println("Hello!");
6:* }
7:*}
8:*^C
Line
commands
*1I
*L
*E
C:\>
1:*// Says Hello
2:*
3:*^C
1: // Says Hello
2:
3:*class Hello
4: {
5:
public static void main(String[] args)
6:
{
7:
System.out.println("Hello!");
8:
}
9: }
Programming and Problem Solving With Java
Current line
(marked
with *)
24
A General List Class: Line Editor
Will use List class to make line editor
Store each line in a list node
Commands
Show all lines with line numbers
Insert lines after a given line number
Delete a line
Quit the program
To insert lines
Type as many lines as desired
Type just period on line to end
Programming and Problem Solving With Java
25
A General List Class: Line Editor
Example run of line editor
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: i
(Enter just a period to stop inserting lines)
: This is the first line in the editor. The
: editor is in insert mode. When a period is
: typed by itself, insert mode stops.
: .
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: i
After which line: 2
(Enter just a period to stop inserting lines)
: --- This is the new third line. --: .
Programming and Problem Solving With Java
26
A General List Class: Line Editor
Example run of line editor (continued)
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: --- This is the new third line. --4: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
| q) Quit
| Enter selection: d
Line to delete: 3
i) Insert lines
d) Delete a line
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
i) Insert lines
| q) Quit
| Enter selection: q
Are you sure you want to quit? (y/n): y
Programming and Problem Solving With Java
d) Delete a line
27
A General List Class: Line Editor
Design of the line editor program
Will use the TextMenu framework for menus
Will use the List class to store lines
Te xtMe nu
Lis t
EditApplication
Programming and Problem Solving With Java
28
A General List Class: Line Editor
Methods in EditApplication class
EditApplication(): Constructor, initializes menu
handleEvent(): Event dispatcher
goToLine(): Changes current line to user-specified line
number
insertLines(): Prompts user for a line number, then
prompts user for lines to insert after that. Stops when
user enters line with just a period.
deleteLine(): Prompts user for a line number, then
deletes that line
displayLines(): Display all lines
Programming and Problem Solving With Java
29
A General List Class: Line Editor
EditApplication constructor
// Constructor - set up menu for the editor
public EditApplication()
{
super("Edit Menu");
editBuffer = new List();
addSelection("Show all lines", 's', SHOW_COMMAND);
addSelection("Insert lines", 'i', INSERT_COMMAND);
addSelection("Delete a line", 'd', DELETE_COMMAND);
addSelection("Quit", 'q', TextMenu.QUIT);
}
EditApplication constants
static final int SHOW_COMMAND = 1;
static final int INSERT_COMMAND = 2;
static final int DELETE_COMMAND = 3;
EditApplication main()
public static void main(String[] args)
throws java.io.IOException
{
EditApplication editor = new EditApplication();
}
editor.run();
Programming and Problem Solving With Java
30
A General List Class: Line Editor
EditApplication handleEvent()
// Event dispatcher for the editor
public int handleEvent(int event)
throws java.io.IOException
{
switch (event)
{
case SHOW_COMMAND:
displayLines();
break;
case INSERT_COMMAND:
insertLines();
break;
case DELETE_COMMAND:
deleteLine();
break;
case TextMenu.QUIT:
if (Keyboard.readChar(
"Are you sure you want to quit? (y/n)", "yn") != 'y')
{
event = TextMenu.CANCEL_QUIT;
}
break;
}
return event;
}
Programming and Problem Solving With Java
31
A General List Class: Line Editor
EditApplication insertLines() steps
Ask the user where to begin inserting new lines.
Move to that line in the list.
Read a line from the user.
As long as the line isn't just a period, do the following
steps.
•Insert the line into the list.
•Move to the new line, so the next line will be inserted after it.
•Read the next line from the user.
Programming and Problem Solving With Java
32
A General List Class: Line Editor
EditApplication
insertLines()
// insertLines: Prompts user for a line number, then prompts
//
user for lines to insert after that line.
//
Stops when the user enters a line with just
//
a period on it.
void insertLines()
throws java.io.IOException
{
String line;
if (!editBuffer.empty())
{
goToLine(Keyboard.readInt("After which line: ", 1,
editBuffer.count()));
}
}
System.out.println(
"(Enter just a period to stop inserting lines)");
line = Keyboard.readString(": ");
while (!line.equals("."))
{
if (editBuffer.isDefined())
{
editBuffer.insert(line);
editBuffer.goNext();
}
else
{
editBuffer.insertFirst(line);
editBuffer.goFirst();
}
line = Keyboard.readString(": ");
}
Programming and Problem Solving With Java
33
A General List Class: Line Editor
EditApplication gotoLine()
// goToLine: Changes the current line to a specific line number
// Note: lineNum must be in the range 1 to number of lines
//
in buffer
void goToLine(int lineNum)
{
// Check precondition
Debug.assert(lineNum >= 1 && lineNum <= editBuffer.count(),
"EditApplication.goToLine(): Invalid line number");
}
editBuffer.goFirst();
for(int i = 1; i < lineNum; i++)
{
editBuffer.goNext();
}
Programming and Problem Solving With Java
34
A General List Class: Line Editor
EditApplication deleteLine() steps
Ask the user which line to delete
Move to that line
Delete that line
EditApplication deleteLine()
// deleteLine: Prompts user for a line number, then deletes
//
that line
void deleteLine()
throws java.io.IOException
{
if (editBuffer.empty())
{
System.out.println("No lines");
}
else
{
goToLine(Keyboard.readInt("Line to delete: ", 1,
editBuffer.count()));
editBuffer.remove();
}
}
Programming and Problem Solving With Java
35
A General List Class: Line Editor
EditApplication displayLines()
// displayLines: Display all lines in the buffer
void displayLines()
{
int lineNumber = 0;
}
for(editBuffer.goFirst();
editBuffer.isDefined();
editBuffer.goNext())
{
lineNumber++;
System.out.println(lineNumber + ": " + editBuffer.get());
}
Shows how to use for statement to traverse
elements of a list
Move to first line with goFirst()
Test whether past end of list with isDefined()
Move to next line with goNext()
Programming and Problem Solving With Java
36
A General List Class: Implementation
List is a container type
Holds elements of another type
Array is another container type
Common implementation of a container as a linked
type
Class for each node of the container
Class for the container itself
Used this implementation with CharList
CharListNode
CharList
Will store an Object value in each node
Programming and Problem Solving With Java
37
A General List Class: Implementation
ListNode class
class ListNode
{
// Constructor
ListNode(Object item, ListNode next)
{
setItem(item);
setNext(next);
}
// getItem: Returns the item value
public Object getItem() { return item; }
// getNext: Returns the next item
public ListNode getNext() { return next; }
// setItem: Sets the item to the given value
public void setItem(Object item)
{
this.item = item;
}
// setNext: Sets the next item to the given object
public void setNext(ListNode next)
{
this.next = next;
}
// Instance variables
Object item;
ListNode next;
Programming}and Problem Solving With Java
38
A General List Class: Implementation
List class structure
Reference to
first node
List
ListNode
1
ListNode
2
ListNode
3
ListNode
4
null
Reference to
last node
Reference to
current node
Number
of nodes
4
Instance variables
// Instance variables
int numNodes;
ListNode first,
last,
currentNode;
Programming and Problem Solving With Java
//
//
//
//
The number of nodes in the list
Reference to the first node
Reference to the last node
Reference to the current node
39
A General List Class: Implementation
List constructor
// Default constructor
public List()
{
first = null;
last = null;
currentNode = null;
numNodes = 0;
}
List insertFirst (similar to CharList)
// insertFirst: Inserts a new item at the beginning of the list.
public void insertFirst(Object item)
{
ListNode newNode = new ListNode(item, first);
}
numNodes++;
first = newNode;
if (last == null)
{
// Special case: An empty list.
// This new node is the last node in the list.
last = newNode;
}
Programming and Problem Solving With Java
40
A General List Class: Implementation
List insertLast (similar to CharList)
// insertLast: Inserts a new item at the end of the list
public void insertLast(Object item)
{
ListNode newNode = new ListNode(item, null);
}
numNodes++;
if (first == null)
{
// Special case: this node is the first node in
// the list.
first = newNode;
}
else
{
// General case: this is not the only node in the list.
// Make the last node point to this one and make
// this the new last node.
last.setNext(newNode);
}
last = newNode;
Programming and Problem Solving With Java
41
A General List Class: Implementation
List insert()
Puts new node after currentNode
Caller responsible for setting currentNode first
// insert: Inserts a new item after a node pointed to by
//
currentNode.
// Note: currentNode must be defined
public void insert(Object item)
{
Debug.assert(isDefined(),
"List.insert(): currentNode undefined");
ListNode newNode = new ListNode(item, currentNode.getNext());
}
numNodes++;
currentNode.setNext(newNode);
if (currentNode == last)
{
// Special case: this is the new last node.
last = newNode;
}
Programming and Problem Solving With Java
42
A General List Class: Implementation
List put()
// put: Changes the value of the currentNode node to item
// Note: currentNode must be defined
public void put(Object item)
{
Debug.assert(isDefined(),
"List.put(): currentNode undefined");
currentNode.setItem(item);
}
List get()
// get: Returns the value in the currentNode
// Note: currentNode must be defined
public Object get()
{
Debug.assert(isDefined(),
"List.get(): currentNode undefined");
return currentNode.getItem();
}
Programming and Problem Solving With Java
43
A General List Class: Implementation
List removeFirst()
Uses removeNode() helper method
// removeFirst: Remove the first element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that case,
//
sets currentNode to previous node.
// Note: The list must not be empty
public Object removeFirst()
{
Debug.assert(!empty(),
"List.removeFirst(): List is empty");
}
Object returnValue = first.getItem();
removeNode(first, null);
return returnValue;
Programming and Problem Solving With Java
44
A General List Class: Implementation
List removeLast()
Uses removeNode() helper method
// removeLast: Remove the last element from the list
//
and return its value. If item is
//
currentNode, then sets currentNode
//
to next node, unless deleting the last
//
node. In that case, sets currentNode to
//
previous node.
// Note: The list must not be empty
public Object removeLast()
{
Debug.assert(!empty(),
"List.removeLast(): List is empty");
}
// Set last to node before last one
Object returnValue = last.getItem();
removeNode(last, findPreviousNode(last));
return returnValue;
Programming and Problem Solving With Java
45
A General List Class: Implementation
List remove()
// remove: Removes item referenced by currentNode, and
//
returns its value. Sets currentNode to next
//
node, unless deleting the last node. In that
//
case, sets currentNode to previous node.
// Note: currentNode must be defined
public Object remove()
{
Debug.assert(isDefined(),
"List.remove(): currentNode undefined");
Object returnValue = currentNode.getItem();
removeNode(currentNode,
findPreviousNode(currentNode));
return returnValue;
}
List append()
// append: Appends elements of the source list to this one
public void append(List source)
{
for (source.goFirst();
source.isDefined();
source.goNext())
{
insertLast(source.get());
}
}
Programming and Problem Solving With Java
46
A General List Class: Implementation
List find()
// find: If a particular value is in the list, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode as it was and
//
returns false.
public boolean find(Object data)
{
ListNode node = first;
// Find node containing the data value
while (node != null && !(node.getItem().equals(data)))
{
node = node.getNext();
}
}
if (node == null)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
47
A General List Class: Implementation
List goFirst()
// goFirst: Sets currentNode to beginning of list
public void goFirst()
{
currentNode = first;
}
List goList()
// goLast: Sets currentNode to end of list
public void goLast()
{
currentNode = last;
}
List goNext()
// goNext: Sets currentNode to next element in the list
// Note: currentNode must be defined
public void goNext()
{
Debug.assert(isDefined(),
"List.goNext(): currentNode undefined");
currentNode = currentNode.getNext();
}
Programming and Problem Solving With Java
48
A General List Class: Implementation
List goPrevious()
// goPrevious: Sets currentNode to previous element in
//
the list
// Note: currentNode must be defined
public void goPrevious()
{
Debug.assert(isDefined(),
"List.goPrevious(): currentNode undefined");
currentNode = findPreviousNode(currentNode);
}
Programming and Problem Solving With Java
49
A General List Class: Implementation
Removing a node
previousNode
node
1
2
Before
removing
3
4
null
4
null
4
previousNode
node
1
2
Link around
node
3
3
Programming and Problem Solving With Java
50
A General List Class: Implementation
List//removeNode()
removeNode: Removes the given node from the list, adjusts
//
first, last, and currentNode
//
if necessary. If node is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that
//
case, sets currentNode to previous node.
void removeNode(ListNode node, ListNode previousNode)
{
if (node == first)
{
first = first.getNext();
}
else
{
previousNode.setNext(node.getNext());
}
if (last == node)
{
last = previousNode;
}
// Reset currentNode, if necessary
if (currentNode == node)
{
if (currentNode.next == null)
{
currentNode = previousNode;
}
else
{
currentNode = currentNode.getNext();
}
}
numNodes--;
Programming}and Problem Solving With Java
51
A General List Class: Implementation
List findPreviousNode()
Modified linear search
Must find the node before the one we want
// findPreviousNode: Returns the node before the given
//
node, or null if the node is the
//
first node in the list.
// Pre: node must be a valid node in the list
ListNode findPreviousNode(ListNode node)
{
ListNode previousNode;
if (node == first)
{
return null;
}
}
previousNode = first;
while (previousNode.getNext() != node)
{
previousNode = previousNode.getNext();
}
return previousNode;
Programming and Problem Solving With Java
52
Infinite Precision Arithmetic
Range of long may not be enough
-9,223,372,036,854,775,808 9,223,372,036,854,775,807
Can make a type that holds any number of digits
// Sample use of the InfinitePrecision class.
import InfinitePrecision;
public class TestInfinitePrecision
{
public static void main(String[] args)
{
InfinitePrecision first = new InfinitePrecision(
"4958614030582059703402389481948372634758695783");
InfinitePrecision second = new InfinitePrecision(
"8089614672364869790583723648597007904201129034");
}
}
System.out.println("The sum of:
System.out.println("
and:
System.out.println("
is:
The sum of:
and:
is:
Programming and Problem Solving With Java
" + first);
" + second);
" + first.add(second));
4958614030582059703402389481948372634758695783
8089614672364869790583723648597007904201129034
13048228702946929493986113130545380538959824817
53
Infinite Precision Arithmetic
InfinitePrecision instance variable
// Instance variables
List digits = new List();
InfinitePrecision default constructor
Use this when we want to assign 0 to the number
// Default Constructor
// Note: An empty list is treated as zero
public InfinitePrecision()
{
}
Programming and Problem Solving With Java
54
Infinite Precision Arithmetic
InfinitePrecision constructor with long argument
// Constructor: Sets the number to that given in the
//
long integer
public InfinitePrecision(long number)
{
// Put digits in number from right to left
while (number != 0)
{
digits.insertFirst(new Integer((int) (number % 10)));
number = number / 10;
}
}
Trace on new InfnitePrecision(12345);
number
digits (list)
0
12345
[]
1
1234
[5]
2
123
[4, 5]
3
12
[3, 4, 5]
4
1
[2, 3, 4, 5]
5
0
[1, 2, 3, 4, 5]
step
Programming and Problem Solving With Java
55
Infinite Precision Arithmetic
InfinitePrecision constructor with string argument
// Constructor: Sets the number to that given in the string
// Note: The string should have only digits
public InfinitePrecision(String number)
{
int i = 0;
}
while (i < number.length())
{
Debug.assert(Character.isDigit(number.charAt(i)),
"InfinitePrecision(): invalid character in string");
digits.insertLast(
new Integer(Character.digit(number.charAt(i), 10)));
i++;
}
Trace on new InfnitePrecision(“12345”);
i
number
digits (list)
0
"12345"
[]
1
"12345"
[1]
2
"12345"
[1, 2]
3
"12345"
[1, 2, 3]
4
"12345"
[1, 2, 3, 4]
5
"12345"
[1, 2, 3, 4, 5]
Programming and Problem Solving With Java
56
Infinite Precision Arithmetic
Adding two infinite precision numbers
Use the manual technique from right to left
Carry
1
1
2
6
7
4
8
2
5
3
4
2
7
+
Programming and Problem Solving With Java
57
Infinite Precision Arithmetic
InfinitePrecision add() (part1)
// add: Returns sum of this value and the other
//
InfinitePrecision value
InfinitePrecision add(InfinitePrecision otherValue)
{
InfinitePrecision result = new InfinitePrecision();
int carry = 0;
digits.goLast();
otherValue.digits.goLast();
// Add digits from right to left
while (digits.isDefined()
&& otherValue.digits.isDefined())
{
result.digits.insertFirst(new Integer(
(((Integer) digits.get()).intValue()
+ ((Integer) otherValue.digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) digits.get()).intValue()
+ ((Integer) otherValue.digits.get()).intValue()
+ carry) / 10;
}
digits.goPrevious();
otherValue.digits.goPrevious();
Programming and Problem Solving With Java
58
Infinite Precision Arithmetic
InfinitePrecision add() (part2)
// Append any remaining digits from this value to result's
// left
for (; digits.isDefined(); digits.goPrevious())
{
result.digits.insertFirst(new Integer(
(((Integer) digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) digits.get()).intValue()
+ carry) / 10;
}
// Append any remaining digits from other value to result's
// left
for (; otherValue.digits.isDefined();
otherValue.digits.goPrevious())
{
result.digits.insertFirst(new Integer(
(((Integer) otherValue.digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) otherValue.digits.get()).intValue()
+ carry) / 10;
}
if (carry != 0)
{
result.digits.insertFirst(new Integer(carry));
}
}
return result;
Programming and Problem Solving With Java
59
Infinite Precision Arithmetic
InfinitePrecision toString()
// toString: Returns a String version of the number
public String toString()
{
String result = "";
if (digits.empty())
{
return "0";
}
else
{
}
}
for (digits.goFirst();
digits.isDefined();
digits.goNext())
{
result = result + digits.get();
}
return result;
Programming and Problem Solving With Java
60
Making List work with Primitives
Can store objects in a List directly
List myList = new List();
myList.insertFirst(“a string”);
Must wrap primitives
myList.insertFirst(new Integer(1234));
myList.insertLast(new Double(6.39));
Can overload List methods so they work with
primitives
// insertFirst: Inserts a new int at the beginning of the
//
list (Overloaded version for int)
public void insertFirst(int item)
{
insertFirst(new Integer(item));
}
Now can store integers directly
myList.insertFirst(1234);
Should also overload for other primitives (long, float, ...)
Programming and Problem Solving With Java
61
Making List work with Primitives
Must cast values from a list, and unwrap primitives
String aString = (String) myList.get();
int anInt = ((Integer) myList.get()).intValue();
Unfortunately, can’t override get() to return int
Overriding works only when parameters differ
To retrieve primitives from List easily
Write getInt() for retrieving integers, getDouble() for
doubles, etc.
// getInt: Returns the int value in the currentNode
//
(Overloaded version for int)
// Note: currentNode must be defined
public int getInt()
{
return ((Integer) get()).intValue();
}
This is why Keyboard class has readInt(), readString(), ...
Use of getInt() is more readable than get()
int anInt = myList.getInt();
Programming and Problem Solving With Java
62
Sorting a List
Two ways to sort a list
Keep it sorted all the time
Users can’t put elements where they want
Sort only when needed
More flesxible
Users can put elements anywhere - can sort later if ncessary
Problem
List stores Object values
Objects have no order -- how to sort them??
Specific objects (dates, strings, ...) do have an order,
though
Can’t put sort() in List class
Programming and Problem Solving With Java
63
Sorting a List: Comparators
Can make a subclass of List that allows sorting
Put responsibility for sorting in separate class
Write a Comparator class
Comparator: object that compares two other objects
Tells which object is less
Comparator compares Object values
Comparator is an abstract class
Why? Can’t compare Object values
Use as a template for subclasses of Comparator
Programming and Problem Solving With Java
64
Sorting a List: Comparators
Comparator class
public abstract class Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
abstract public int compareTo(Object a, Object b);
}
Subclass of Comparator for comparing strings
public class StringComparator extends Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
public int compareTo(Object a, Object b)
{
return ((String) a).compareTo((String) b);
}
}
Programming and Problem Solving With Java
65
Sorting a List: Comparators
Subclass of Comparator for comparing integers
public class IntegerComparator extends Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
public int compareTo(Object a, Object b)
{
int inta = ((Integer) a).intValue();
int intb = ((Integer) b).intValue();
}
}
if (inta < intb)
{
return -1;
}
if (inta > intb)
{
return 1;
}
return 0;
Programming and Problem Solving With Java
66
Sorting a List: SortableList
Skeleton for SortableList class
import List;
import Comparator;
public class SortableList extends List
{
// Constructor
public SortableList(Comparator comparator)
{
this.comparator = comparator;
}
//
//
//
//
}
--------------------------------------------------------------Sort method can go here. It should use comparator.compareTo()
to compare elements of the list.
---------------------------------------------------------------
// Instance variables
Comparator comparator;
Inherits all the methods of List: insert(), remove(), ...
Can use any sorting algorithm in SortableList
Programming and Problem Solving With Java
67
Sorting a List: Quick Sort
Quick sort
Very fast and efficient
On average, the fastest known sorting algorithm
Can be very slow occasionally
Works well with lists (and arrays)
Programming and Problem Solving With Java
68
Quick Sort
Step 1: Choose a
pivot element
{4, 2, 6, 1, 3, 7, 5}
Pivot
4
How quick sort works
Choose pivot
Make list of elements
less than pivot
Make list of elements
greater than pivot
Sort both lists
(using quick sort)
Combine the sorted
lists
Step 2: Make a list
of elements less
than the pivot
[4, 2, 6, 1, 3, 7, 5]
Less
than
pivot
[2, 3, 1]
Step 3: Make a list
of elements more
than the pivot
Pivot
4
[4, 2, 6, 1, 3, 7, 5]
Less
than
pivot
[2, 3, 1]
4
[6, 7, 5]
Step 4: Sort sublists
and append
Less
than
pivot
[1, 2, 3]
Programming and Problem Solving With Java
Greater
than
pivot
Pivot
Greater
than
pivot
Pivot
4
[1, 2, 3, 4, 5, 6, 7]
[5, 6, 7]
69
Quick Sort
Choice of pivot is critical in quick sort
Ideally, the pivot should be the middle value of the list
If list is already sorted, choosing first element gives very
slow sort (why?)
Common pivot selection technique for array
Choose middle value of:
array[0]
array[array.length-1]
array[array.length / 2]
Even better: choose random element as the pivot
Can’t get middle element from list (efficiently)
Ideas for choosing a
pivot value for a list??
Programming and Problem Solving With Java
70
SortableList quickSort()
// quickSort: Sorts the list
public void quickSort()
{
SortableList lessList = new SortableList(comparator);
SortableList greaterList = new SortableList(comparator);
Object pivot, element;
goFirst();
if (!isEmpty())
{
pivot = removeFirst();
while (!isEmpty())
{
element = removeFirst();
if (comparator.compareTo(element, pivot) < 0)
{
lessList.insertFirst(element);
}
else
{
greaterList.insertFirst(element);
}
}
lessList.quickSort();
greaterList.quickSort();
}
}
// Append lists to get result
append(lessList);
insertLast(pivot);
append(greaterList);
Programming and Problem Solving With Java
71
SortableList quickSort()
Demonstration of SortableList
// Demonstrates the use of the SortableList class,
// which contains a quick sort algorithm.
import SortableList;
import StringComparator;
public class TestSortableList
{
public static void main(String[] args)
{
SortableList myList = new SortableList(new StringComparator());
myList.insertFirst("banana");
myList.insertFirst("orange");
myList.insertFirst("apple");
myList.insertFirst("grape");
myList.insertFirst("pear");
myList.insertFirst("strawberry");
myList.insertFirst("cherry");
}
}
System.out.println("Before sort: " + myList);
myList.quickSort();
System.out.println("After sort: " + myList);
Before sort: [cherry strawberry pear grape apple orange banana ]
After sort: [apple banana cherry grape orange pear strawberry ]
Programming and Problem Solving With Java
72
SortableList quickSort()
Another Demonstration of SortableList
// Demonstrates the use of the SortableList class,
// which contains a quick sort algorithm.
import SortableList;
import IntegerComparator;
public class TestSortableList2
{
public static void main(String[] args)
{
SortableList myList = new SortableList(new IntegerComparator());
myList.insertFirst(3);
myList.insertFirst(8);
myList.insertFirst(2);
myList.insertFirst(1);
myList.insertFirst(4);
myList.insertFirst(7);
myList.insertFirst(5);
}
}
// Note use of special insertFirst()
// made especially for int type
// (Otherwise, would need to use
// new Integer(3), for example,
// instead of 3)
System.out.println("Before sort: " + myList);
myList.quickSort();
System.out.println("After sort: " + myList);
Before sort: [5 7 4 1 2 8 3 ]
After sort: [1 2 3 4 5 7 8 ]
Programming and Problem Solving With Java
73
A Set Type
Set: heterogeneous, unordered collection of
elements without duplicate values
Common set operations
Operation
Symbol
Description
Example
Union
The union of two sets is
everything that is in
either set.
{1,2} {2 ,3} {1,2 ,3}
Intersection
{1,2} {2,3} {2}
Difference
The intersection of two
sets is everything that is
in both sets.
Programming and Problem Solving With Java
The difference of two
sets is everything that is
the first set but not in the
second.
{1,2} {2,3} {1}
74
A Set Type
Set operations
Union
A
Intersection
A
B
Difference
B
Programming and Problem Solving With Java
A
B
75
A Set Type
Demonstration of how to use the Set class
// Demonstrates use of the Set class
import Set;
public class TestSet
{
public static void main(String[] args)
{
// Make two sets
Set a = new Set();
Set b = new Set();
Set a is
Set b is
a union b is
a intersect b is
a difference b is
// Put 1 and 2 in set a
a.add("1");
a.add("2");
// Put 2 and 3 in set b
b.add("2");
b.add("3");
}
}
// Display results
System.out.println("Set a is
System.out.println("Set b is
System.out.println("a union b is
System.out.println("a intersect b is
System.out.println("a difference b is
Programming and Problem Solving With Java
"
"
"
"
"
+
+
+
+
+
{2 1}
{3 2}
{1 3 2}
{2}
{1}
a);
b);
a.union(b));
a.intersect(b));
a.difference(b));
76
A Set Type: Implementation
Store set elements in a list
// Instance variables
List data = new List();
Constructor for Set
// Default constructor
public Set()
{
}
add() method must not insert duplicate values
// add: Adds an element to a set if not already in the set.
//
If the element is already in the set, it is not
//
added again.
public void add(Object item)
{
if (!isMember(item))
{
data.insertFirst(item);
}
}
Programming and Problem Solving With Java
77
A Set Type: Implementation
Set remove() method
// remove: Removes the given item from the set. Does nothing
//
if the element is not in the set.
public void remove(Object item)
{
if (data.find(item))
{
data.remove();
}
}
Easy to write
List class methods do all the work
Programming and Problem Solving With Java
78
A Set Type: Implementation
Set union() method
// union: Returns the union of this set and otherSet, that
//
is, all items in either set.
public Set union(Set otherSet)
{
Set result = new Set();
// Copy everything from otherSet to result
result.data.append(otherSet.data);
// Add items from this set to the result (The add() member
// method will make sure that no element is added twice.)
for (data.goFirst();
data.isDefined();
data.goNext())
{
result.add(data.get());
}
}
return result;
Another approach: use add() for both sets
Not as efficient - don’t need to check for duplicates until
second set added
Programming and Problem Solving With Java
79
A Set Type: Implementation
Set intersect() method
// intersect: Returns the intersection of this set and
//
otherSet, that is, all items in both sets.
public Set intersect(Set otherSet)
{
Set result = new Set();
}
// Copy items from this set that are also in otherSet to
// result
for (data.goFirst();
data.isDefined();
data.goNext())
{
if (otherSet.isMember(data.get()))
{
result.add(data.get());
}
}
return result;
Programming and Problem Solving With Java
80
A Set Type: Implementation
Set difference() method
// difference: Returns the difference of this set and
//
otherSet, that is, all items in this set but
//
not in otherSet.
public Set difference(Set otherSet)
{
Set result = new Set();
// Copy those items from this set that are not in otherSet
// to result
for (data.goFirst();
data.isDefined();
data.goNext())
{
if (!otherSet.isMember(data.get()))
{
result.add(data.get());
}
}
}
return result;
Programming and Problem Solving With Java
81
A Set Type: Implementation
Set toString() method
// toString: Returns the set's contents as a string in
//
standard displayable format: {1, 3, 2}
public String toString()
{
String listStr = data.toString();
}
return "{"
+ listStr.substring(1, listStr.length() - 2)
+ "}";
Programming and Problem Solving With Java
82
A Set Type: Implementation
Set count(), empty(), isFull(), isMember() methods
// count: Returns the number of items in the set
public int count()
{
return data.count();
}
// empty: Returns true if the set is empty, false
//
otherwise
public boolean empty()
{
return data.empty();
}
// isFull: Returns true if the set is not empty, false
//
otherwise (always return false for list
//
implemention)
public boolean isFull()
{
return false;
}
// isMember: Returns true if item is in the set, false
//
otherwise
boolean isMember(Object item)
{
return data.find(item);
}
Programming and Problem Solving With Java
83
Doubly Linked Lists
Singly linked list
Each node references its successor
Can only move from node to next node
Doubly linked list
Each node references successor and predecessor
Advantage: Can delete node without searching for
successor and predecessor
Advantage: Can go through list backward
Reference to
first node
DList
DListNode
null
1
DListNode
DListNode
2
3
null
Reference to
last node
Reference to
current node
Number
of nodes
3
Programming and Problem Solving With Java
84
Doubly Linked Lists
Problems with doubly linked lists
Takes more memory than singly linked
Lots of special cases in implementation
Can remove many special cases with
Dummy header: unused node
Circular references
Reference
to header
node
Reference
to current
node
DList
Header
1
2
2
Number of
nodes
Programming and Problem Solving With Java
85
Doubly Linked Lists
Empty doubly linked list
Reference
to header
node
DList
Reference
to current
node
NULL
Header
0
Number of
nodes
Note: reference to end of list not necessary
Programming and Problem Solving With Java
86
Doubly Linked List: Implementation
DoubleListNode class
class DoubleListNode
{
// Default Constructor
public DoubleListNode()
{
this(null, null, null); // (This is the default action, but it
// doesn't hurt to be explicit)
}
// Constructor
public DoubleListNode(Object item,
DoubleListNode previous,
DoubleListNode next)
{
this.item = item;
this.previous = previous;
this.next = next;
}
// getItem: Returns the item value
public Object getItem() { return item; }
// getNext: Returns the next item
public DoubleListNode getNext() { return next; }
Programming and Problem Solving With Java
87
Doubly Linked List: Implementation
DoubleListNode class (continued)
// getPrevious: Returns the previous item
public DoubleListNode getPrevious() { return previous; }
// setItem: Sets the item to the given value
public void setItem(Object item)
{
this.item = item;
}
// setNext: Sets the next item to the given object
public void setNext(DoubleListNode next)
{
this.next = next;
}
// setPrevious: Sets the previous item to the given object
public void setPrevious(DoubleListNode previous)
{
this.previous = previous;
}
}
// Instance variables
DoubleListNode next, previous;
Object item;
Programming and Problem Solving With Java
88
Doubly Linked List: Implementation
DoubleList instance variables
// Instance variables
DoubleListNode header;
DoubleListNode currentNode;
int numNodes;
DoubleList constructor
// Reference to dummy header
// Reference to current node
// Number of nodes in list
// Default constructor
public DoubleList()
{
numNodes = 0;
}
// Allocate dummy header node
header = new DoubleListNode();
header.setPrevious(header);
header.setNext(header);
Programming and Problem Solving With Java
Reference
to header
node
DList
Reference
to current
node
NULL
Header
0
Number of
nodes
89
Doubly Linked List: Implementation
Inserting a
node at
the
beginning
of a list
After creating
the new node
temp
3
Reference
to header
node
Reference
to current
node
DList
Header
1
2
2
Number of
nodes
After inserting
the new node
temp
3
Reference
to header
node
Reference
to current
node
Number of
nodes
Programming and Problem Solving With Java
DList
Header
1
2
3
90
Doubly Linked List: Implementation
DoubleList insert() method
// insertFirst: Inserts a new item at the beginning of the
//
list
public void insertFirst(Object item)
{
DoubleListNode oldFirstNode = header.getNext();
DoubleListNode newNode
= new DoubleListNode(item, header, oldFirstNode);
}
numNodes++;
oldFirstNode.setPrevious(newNode);
header.setNext(newNode);
Programming and Problem Solving With Java
91
Doubly Linked List: Implementation
Removing
a value
from a
list
Before
removing
Ref erence
to header
node
Ref erence
to current
node
DList
Header
1
2
1
2
2
Number of
nodes
Link around
node
Ref erence
to header
node
Ref erence
to current
node
DList
Header
2
Number of
nodes
Adjust current
node
Ref erence
to header
node
Ref erence
to current
node
Number of
nodes
Programming and Problem Solving With Java
DList
Header
2
1
92
Doubly Linked List: Implementation
DoubleList remove()
// remove: Removes item referenced by currentNode, and
//
returns its value. Sets currentNode to next
//
node, unless deleting the last node. In that
//
case, sets currentNode to previous node.
// Note: currentNode must be defined
public Object remove()
{
Debug.assert(isDefined(),
"DoubleList.remove(): currentNode undefined");
Object returnValue = currentNode.getItem();
removeNode(currentNode);
return returnValue;
}
Programming and Problem Solving With Java
93
Doubly Linked List: Implementation
DoubleList removeNode()
// removeNode: Removes the given node from the list, adjusts
//
first, last, and currentNode
//
if necessary. If node is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that
//
case, sets currentNode to previous node.
void removeNode(DoubleListNode node)
{
DoubleListNode nextNode = node.getNext(),
previousNode = node.getPrevious();
previousNode.setNext(nextNode);
nextNode.setPrevious(previousNode);
numNodes--;
}
// Reset currentNode, if necessary
if (currentNode == node)
{
if (currentNode.next == header)
{
currentNode = previousNode;
}
else
{
currentNode = nextNode;
}
}
Programming and Problem Solving With Java
94
Doubly Linked List: Implementation
DoubleList find()
// find: If a particular value is in the list, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode as it was and
//
returns false.
public boolean find(Object data)
{
DoubleListNode node = header.getNext();
// Find node containing the data value
while (node != header && !(node.getItem().equals(data)))
{
node = node.getNext();
}
}
if (node == header)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
95
Computer Security: Layers
Layers of security
Protected Information
Encryption
Inference and access controls
Database authentication
Operating system authentication
Intrusion detection
Intrusion prevention
Programming and Problem Solving With Java
ATTACK
Personnel screening
96
Computer Security: Layers
Physical security: intrusion prevention and detection
Fences
Lack of windows
Walls that extend to the roof
Mechanical and electronic locks
Guards
Adequate lighting
Automated entry booths
Uninterruptible power supplies
Power filters and surge suppressors
Smoke and fire detection
Automatic fire extinguishers
Programming and Problem Solving With Java
97
Computer Security: Layers
Operating system
Identification: unique name for each user
Authentication: confirmation of user by computer and
vice versa
Authentication techniques
Check what user knows (password, ...)
Check what user carries (smartcard, ...)
Check who user is (retina scan, voice print, ...)
Password recommendations (US DoD)
Users should be able to change
Should be machine generated
System should display last login time
Programming and Problem Solving With Java
98
Computer Security: Disclosure
Disclosure of information can be harmful
Military and government disclosure: national security
Commercial disclosure: trade secrets, customer lists, ...
US Laws forbidding disclosure of personal
information
Right to Financial Privacy (1978)
Privacy Act (1974)
(Other countries have similar laws)
Programming and Problem Solving With Java
99
Computer Security: Disclosure
Covert channel
Unconventional method of
information transfer
Types of covert channels
Storage
Timing
Very difficult to identify
covert channels
Programming and Problem Solving With Java
Message not allowed
User A
User B
Message
Move
disk
head
Detect
head
movement
Disk Drive
100
Computer Security: Disclosure
Indirect disclosure: inference or aggregation
Inference
Can guess value by adding outside information
Example: Anderson is only female manager
Can guess Anderson’s salary from FSalary - TSalary
•FSalary, total salary of all females
•TSalary, total salary of all non-manager females
Aggregation
Can guess value by combining nonsensitive values
Example: knowing 1 CIA phone number is Ok
Knowing ALL CIA phone numbers is NOT Ok
Programming and Problem Solving With Java
101
Computer Security: Modification
Data modification or destruction more serious to
commercial computers
Usually caused by disgruntled employees
Trapdoor: turns off normal security checking
Example: no password for some accounts
Trojan horse: malicious program hidden in another
Virus: self-perpetuating Trojan horse, attaches to
other programs
Worm: self-perpetuating program takes over idle
machines in a network
Time bombs and logic bombs
Programming and Problem Solving With Java
102
Computer Security: Military
Focus: control of disclosure
Sensitivity levels
Unclassified
Confidential
Secret
Top secret
Compartments: topic areas
Nuclear
Spy
...
NUC
SPY
Top Secret
Secret
Confidential
o3
o1
o2
Unclassified
Each object has security level
Each user has clearance
Programming and Problem Solving With Java
103
Computer Security: Military
Mandatory access control (MAC)
Enforcement of military security
Unauthorized disclosure is illegal
Discretionary access control (DAC)
Owner of data decides who can access it
Most common commercial security technique
Used in many operating systems (NT, Unix, VAX VMS)
MAC and DAC combined = military security
Programming and Problem Solving With Java
104
Computer Security: Military
Modes of operation for military computers
Dedicated: users cleared for all data, can access all data
System-high: users cleared for all data, can access some
data
Compartmented: users cleared for most restricted data,
can access some data
Multilevel: users not cleared for all data, can access
some data
Most military computers run in system-high mode
Military would like to move to multilevel
Cheaper
Easier to keep data consistent
Programming and Problem Solving With Java
105
Computer Security: Military
DoD security classifications
Level D
No security
Level C (C1, C2)
Discretionary access control
NT, VAX VMS, some variants of Unix are C2
C2 is minimum for commercial security
Level B (B1, B2, B3)
Level C features
Plus mandatory access control
Level A
Level B features
Plus formal proof of correctness
Programming and Problem Solving With Java
106
Computer Security: Access Control
Discretionary access control (DAC)
Allows data owner to choose who else can access
Little protection against Trojan horse attacks
Implementation of DAC
Capabilities
Access control lists
Protection bits
Capabilities
Files
FILE1
FILE2
User A
Files
FILE1
FILE2
FILE3
User B
System associates access rights
with each user
User C
Advantage: more protection
against Trojan horse attacks
Disadvantage: revoking rights
is difficult
Programming and Problem Solving With Java
Rights
R, W
R
Files
FILE2
FILE3
Rights
R
R, W
R, W
Rights
R
R, W
107
Computer Security: Access Control
Access control lists
Another way to implement DAC
Stores list of authorized users
with each resource
US National Computer
Center recommends this
approach
Users Rights
User A R, W
User B R
FILE1
FILE2
Users
User A
User B
User C
Rights
R
R, W
R
FILE3
Users Rights
User B R, W
User C R, W
Programming and Problem Solving With Java
108
Computer Security: Access Control
Protection bits
Another way to implement DAC
9 bits (Boolean values) per object
Owner read
Owner write
Owner execute
Group read
Group write
Group execute
Others read
Others write
Others execute
Used with many Unix variants
% ls -l newmodel.txt
-rw-rw---- 1 slack
219 Jan
6 14:07 newmodel.txt
% chmod u-w newmodel.txt
-r--rw---- 1 slack
219 Jan
6 14:07 newmodel.txt
Change projection with chmod
Simplest approach to implement DAC
But weak protection -- doesn’t qualify for level C security
Programming and Problem Solving With Java
109
Computer Security: Commercial
Commercial security emphasizes prevention of
unauthorized modification
Most common unauthorized modification
Programming and Problem Solving With Java
110
Computer Security: Commercial
Major types of undesirable changes
Unauthorized user inserts false information deliberately
Authorized user inserts false information accidentally
Prevent unauthorized changes with security
techniques
MAC
DAC
How to prevent accidental changes?
Programming and Problem Solving With Java
111
Computer Security: Commercial
Can’t prevent all accidental changes
Prevent most of them with integrity constraints
(business rules)
Age of employees must be between 18 and 80
No employee can earn more than his or her manager
Integrity
Validity (no false information)
Completeness (all true information included)
Integrity usually enforced at database level
Correct state: when data satisfies all Integrity constraints
Database system tries to keep data in correct state
Programming and Problem Solving With Java
112
Computer Security: Commercial
Transaction: group of changes to data
Must take database from one correct state to another
correct state
Transaction example
Integrity constraint: Sales + value of inventory is constant
Customer buys shoes: steps in database
1. Subtract value of shoes from inventory
2. Add amount of sale to sum of today’s sales
Incorrect state between steps
Correct state only after both steps completed
Programming and Problem Solving With Java
113
Computer Security: Commercial
Types of database integrity constraints
Structure-based: part of the database structure
Value-based: based on values in the database
Structure-based example
Can only store an integer in an Age field (defined as
Integer)
Value-based example
No employee can earn more than his or her manager
Programming and Problem Solving With Java
114
Computer Security: Commercial
Clark-Wilson model of integrity
Looks
like
objectoriented!!
Only transaction procedures can change data
Users can only use transaction
procedures -- can’t access data directly
Task: several transactions
Separation of duties: make sure a different person
handles each transaction in a task
Example: Paying a supplier
Receive new inventory
Approve supplier’s invoice
Request payment to supplier
Print check
Programming and Problem Solving With Java
115
Computer Security: Individual
Choose a good password
Shouldn’t be easy to guess
Don’t use name of friend, pet, hometown, ...
Don’t use a word in English
Should be easy to remember, but nonsensical to others
How to choose a password
Use a mnemonic (“The frog jumped up and kicked the
horse.” Tfjuakth)
Concatenate two unrelated words (“cube” + “branch”
cubebranch)
Keep your password safe
Don’t write it down anywhere
Don’t let others user your account
Programming and Problem Solving With Java
116
Computer Security: Individual
Encryption
Scrambles data according to an encryption key
Makes data useless to others
Must use decryption key to get original data back
Encryption by rotation
A B C D E F G H I
J K L ...
Plaintext: “This is a test.”
Encrypted text (key of 3): “Wklv%lv%whvw1”
Common encryption techniques
DES
Blowfish
PGP
Programming and Problem Solving With Java
117
Computer Security: Individual
Protect against viruses
Use virus protection programs
Keep their virus lists current
Protect against fire, flood, theft
Insurance
Backup
Back up your data
Copy to diskette, Zip disk, tape
Full backup: all the data on the computer
Incremental backup: changes since last full backup
Programming and Problem Solving With Java
118
Computer Security: Individual
Backup procedure
Have at least two backups -- one offsite
Newest full
backup
on tape
Previous
full backup
on tape
Newest
incremental
backup
on floppies
Previous
incremental
backup
on floppies
Programming and Problem Solving With Java
Ready for
reuse
Ready for
reuse
119