Transcript Formalizing the Dynamic Semantics of Java

7
Linked List Data Structures
• Linked lists: singly-linked and
doubly-linked.
• SLL Insertion.
• SLL Searching.
• ADTs
© 2001, D.A. Watt and D.F. Brown
7-1
Linked lists (1)
• A linked list consists of a sequence of nodes connected by
links, plus a header.
• Each node (except the last) has a successor, and each node
(except the first) has a predecessor.
• Each node contains a single element (object or value), plus
links to its successor and/or predecessor.
ant
header
node
ant
bat
element
bat
cat
link
null link
cat
7-2
Linked lists (2)
• The length of a linked list is the number of
nodes.
• An empty linked list has no nodes.
• In a linked list:
 We can manipulate the individual elements.
 We can manipulate the links, thus changing the
linked list’s very structure! (This is impossible
in an array.)
7-3
Singly-linked lists (1)
• A singly-linked list (SLL) consists of a sequence of
nodes, connected by links in one direction only.
• Each SLL node contains a single element, plus a link to the
node’s successor (or a null link if the node has no
successor).
• An SLL header contains a link to the SLL’s first node (or a
null link if the SLL is empty).
pig
dog
cat
rat
dog
7-4
Singly-linked lists (2)
• Java class implementing SLL nodes:
public class SLLNode
{
protected Object element;
protected SLLNode succ;
public SLLNode (Object elem, SLLNode succ)
{
this.element = elem;
this.succ = succ;
}
}
7-5
Singly-linked lists (3)
• Java class implementing SLL headers:
public class SLL
{
private SLLNode first;
public SLL ()
{
// Construct an empty SLL.
this.first = null;
}
…
SLL methods (to follow)
}
7-6
Example: SLL traversal
• Instance method (in class SLL) to traverse an SLL:
public void printFirstToLast ()
{
// Print all elements in this SLL, in first-to-last order.
for (SLLNode curr = this.first;
curr != null; curr = curr.succ)
System.out.println(curr.element);
}
• Animation:
first
ant
bat
cat
curr
7-7
Example: SLL manipulation (1)
• Instance method (in class SLL) to delete an SLL’s first
node:
public void deleteFirst ()
{
// Delete this SLL’s first node (assuming length > 0).
this.first = this.first.succ;
}
• Animation:
first
ant
bat
cat
7-8
Example: SLL manipulation (2)
• Instance method (in class SLL) to delete an SLL’s second
node:
public void deleteSecond ()
{
// Delete this SLL’s second node (assuming length > 1).
SLLNode second = this.first.succ;
this.first.succ = second.succ;
}
• Animation:
first
ant
bat
cat
second
7-9
Example: SLL manipulation (3)
• Instance method (in class SLL) to swap an SLL’s first and
second nodes:
public void swapFirstTwo ()
{
// Swap this SLL’s 1st and 2nd nodes (assuming length > 1).
SLLNode second = this.first.succ;
this.first.succ = second.succ;
second.succ = this.first;
this.first = second;
}
• Animation:
first
second
ant
bat
cat
7-10
Insertion
• Problem: Insert a new element at a given point in a
linked list.
• Four cases to consider:
1) insertion in an empty linked list;
2) insertion before the first node of a nonempty linked list;
3) insertion after the last node of a nonempty linked list;
4) insertion between nodes of a nonempty linked list.
• The insertion algorithm needs links to the new node’s
successor and predecessor.
7-11
SLL insertion (1)
• SLL insertion algorithm:
To insert elem at a given point in the SLL headed by first:
1. Make ins a link to a newly-created node with element elem and
successor null.
2. If the insertion point is before the first node:
2.1. Set node ins’s successor to first.
2.2. Set first to ins.
3. If the insertion point is after the node pred:
3.1. Set node ins’s successor to node pred’s successor.
3.2. Set node pred’s successor to ins.
4. Terminate.
7-12
SLL insertion (2)
• Animation (insertion before first node):
To insert elem at a given point in the SLL headed by first:
1. Make
ins aelem
linkatto
a newly-created
node
with
To insert
a given
point in the SLL
headed
byelement
first:
elem
1. and
Makesuccessor
ins a link tonull.
a newly-created node with element
and successor
2. If the elem
insertion
point isnull.
before the first node:
2. Set
If the
insertion
is beforetothe
first node:
2.1.
node
ins’spoint
successor
first.
2.1. Set node ins’s successor to first.
2.2. Set
first to ins.
2.2. Set first to ins.
3. If the
point
is isafter
pred:
3. Ifinsertion
the insertion
point
afterthe
the node
node pred:
3.1. Set
ins’sins’s
successor
pred’ssuccessor.
successor.
3.1.node
Set node
successortotonode
node pred’s
3.2.node
Set node
pred’s
successortotoins.
ins.
3.2. Set
pred’s
successor
4. Terminate.
4. Terminate.
first first
ins
bat bat
cat
cat
ant
ant
7-13
SLL insertion (3)
• Animation (insertion after intermediate node):
To insert elem at a given point in the SLL headed by first:
To insert
a given
point in the SLL
headed
first:
1. Make
ins aelem
linkatto
a newly-created
node
withbyelement
1. and
Makesuccessor
ins a link tonull.
a newly-created node with element
elem
elem and successor null.
2. If the
insertion point is before the first node:
2. If the insertion point is before the first node:
2.1. Set
ins’sins’s
successor
2.1.node
Set node
successortotofirst.
first.
2.2. Set
2.2.first
Set to
firstins.
to ins.
3. Ifinsertion
the insertion
point
afterthe
the node
node pred:
3. If the
point
is isafter
pred:
3.1.node
Set node
successortotonode
node pred’s
pred’s successor.
3.1. Set
ins’sins’s
successor
successor.
3.2. Set node pred’s successor to ins.
3.2.
Set node pred’s successor to ins.
4. Terminate.
4. Terminate.
first
first
pred
dog
dog
ins
fox
fox
eel
eel
7-14
SLL insertion (4)
• Implementation as a Java method (in class SLL):
public void insert (Object elem SLLNode pred)
{
SLLNode ins = new SLLNode(elem, null);
if (pred == null)
{
ins.succ = this.first;
this.first = ins;
}
else
{
ins.succ = pred.succ;
pred.succ = ins;
}
}
7-15
Searching (1)
• Problem: Search for a given target value in a linked list.
• Unsorted SLL linear search algorithm:
To find which (if any) node of the SLL headed by first contains an
element equal to target:
1. For each node curr in the SLL headed by first, repeat:
1.1. If target is equal to node curr’s element, terminate with
answer curr.
2. Terminate with answer none.
• DLL linear search is similar, except that we can search
from last to first if preferred.
7-16
Searching (2)
• Analysis (counting comparisons):
Let n be the SLL’s length.
• If the search is successful:
Average no. of comparisons = (n + 1)/2
• If the search is unsuccessful:
No. of comparisons = n
• In either case, time complexity is O(n).
7-17
Searching (3)
• Java implementation:
public SLLNode search (Object target)
{
for (SLLNode curr = this.first;
curr != null; curr = curr.succ)
{
if (target.equals(curr.element))
return curr;
}
return null;
}
7-18
Data types
• We classify all data into data types, such as:
 Booleans
 integers
 objects of various classes.
• Each data type is characterized by:
 a set of values
 a data representation
(which is common to all these values)
 a set of operations
(which can be applied uniformly to all these values).
7-19
Introducing new data types
• To introduce a new data type, we must define its values,
data representation, and operations.
• In Java, use a class declaration:
 The class’s instance variables determine the values and data
representation.
 The class’s constructors and methods are the operations.
• Each object of the class:
 has those instance variables
 is created by one of those constructors
 may be inspected and/or updated by any of those methods.
7-20
Abstract data types
• An abstract data type (ADT) is characterized by:
 a set of values
 a set of operations.
It is not characterized by its data representation.
• The data representation is private, so application code
cannot access it. (Only the operations can.)
• The data representation is changeable, with no effect on
application code. (Only the operations must be recoded.)
7-21
ADT specification (1)
• Each ADT should have a contract that:
 specifies the set of values of the ADT
 specifies each operation of the ADT
(i.e., the operation’s name, parameter type(s), result type, and
observable behavior).
• The contract does not specify the data representation, nor
the algorithms used to implement the operations.
• The observable behavior of an operation is its effect as
‘observed’ by the application code.
 Example of observable behavior: search an array.
 Examples of algorithms with that behavior: linear search, binary
search.
7-22
ADT specification (2)
• The ADT programmer undertakes to provide an
implementation of the ADT that respects the contract.
• The application programmer undertakes to process
values of the ADT using only the operations specified in
the contract.
• Separation of concerns:
 The ADT programmer is not concerned with what applications the
ADT is used for.
 The application programmer is not concerned with how the ADT is
implemented.
• Separation of concerns is essential for designing and
implementing large systems.
7-23
ADT implementation
• An implementation of an ADT entails:
 choosing a data representation
 choosing an algorithm for each operation.
• The data representation must be private.
• The data representation must cover all possible values.
• The algorithms must be consistent with the data
representation.
7-24