Home  Previous  Next 

CSC205::Lecture Note::Week 11
Assignments 
Code 
Handouts 
Resources 
Email Thurman 
Tweets::@compufoo
GDT::Bits::
Time

Weather

Populations

Special Dates
SinglyLinkedList.java
(OOP version) 
DoublyLinkedList.java

A linked list is a lowlevel structure upon which highlevel data structures can be built (e.g.
stacks
andqueues
can be implemented using a linkedlist).To date, we have grouped program data using the following ADTs (Abstract Data Types, or User Defined Types): array,
class
),Vector
, set, list, stack, and queue (and priority queue).Sometimes the only ADT available for organizing data is the builtin array; however, this can be problem if the the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. In these cases a linkedlist may be the solution.
A linkedlist is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).
If each node contains only one link member, then we have a singly linked list.
Unlike an array, the nodes of a linkedlist do not necessarily occupy consecutive memory locations. [C/C++ comment]
The implementation of a linkedlist relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linkedlist is created, its length (i.e. # of nodes) is unknown.] [C/C++ comment]
Although arrays support "simple" list storage applications, they cannot efficiently handle dynamic changes such as inserting and deleting from the middle of a list. As we have seen, these operations require shifting elements either to the right or the left. With large volumes of data, these copy operations can be expensive.
Terminology
A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The endoflist (EOL) is called the rear its link data member has the value
NULL
(i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.Description of a Node
A node can be described as follows:
Data
data field
 value is not used in any operation other than initializationnext pointer
 pointer to the following node (ornull
if there is no next node)Operations
constructor
 initialize a new nodenextNode
 returnnext
insertAfter
 resetnext
to point at the new node and adjust the value ofnext
in the new node to reference the successor of the current nodedeletetAfter
 unlink thenext
node and assign the valuenext
to reference the successor of the next nodeBjarne Stroustrup: Why you should avoid Linked Lists
CS 61B at UCBerkeley
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Inheritance allows classes to be defined in terms of other classes.
In Java, inheritance is implemented when a class
extends
another class.
Inheritance supports the isa type of relationship.
The child (or derived or subclass) class acquires (i.e. inherits) all the features of an existing class called the parent (or superclass).
You can override existing methods and add new methods. [Modify inherited behavior and implement additional behavior.]
You can add fields (i.e. additional data).
Most commonly inheritance is used for specialization.
Polymorphism is when an object of a child class is used as an object of its parent class. In other words, an object of a given class can have multiple forms, either as it own class or as any class it extends.
By default, all classes
extend
theObject
class that comes with the JSDK. Therefore, every object isan object of classObject
.Some benefits obtained from using inheritance are.
 duplication of code reduced
 less code
 more localization / improved readability
 easier to understand and maintain
You are not limited to just one layer of inheritance. The inheritance tree, or class hierarchy, can be as deep as needed.
In general, the further down in the hierarchy a class appears, the more specialized its behavior. [Class extension is most commonly used for specialization.]
The following is an example class hierarchy.
BankAccount (account#, balance)  +++   CheckingAccount SavingsAccount  +++   PassBookAccount InvestmentAccount public class BankAccount extends Object {...} public class CheckingAccount extends BankAccount {...} public class SavingsAccount extends BankAccount {...} public class PassBookAccount extends SavingsAccount {...} public class InvestmentAccount extends SavingsAccount {...} CheckingAccount "isa" BankingAccount and PassBookAccount "isa" SavingsAccount and so on. Note: BankAccount extends Object.Java supports singleinheritance only (i.e. a class can
extend
only one class).Typical characteristics of a derived class are.
 data is added
 functionality (behavior) is added
 functionality provided in the parent class is modified
The representation of the parent class cannot be altered (i.e. neither data nor functionality [behavior] can be removed).
Functionality defined in the parent class can be modified by overriding the appropriate methods in the derived class.
If a parent method is overridden in the child class and the child wants to invoke the parent's method, then the
super
keyword must be used to qualify the method name.class Foo { void echo() {...} } class Bar extends Foo { void echo() { super.echo(); //invoke echo() implemented in the parent class ... } }From 1999 (so it might be dated/stale): JavaWorld.com::How to avoid traps and correctly override methods from java.lang.Object
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
An abstract class is one that is used for derivation only. Objects cannot be instantiated from an abstract class. Attempting to do so at compiletime is a syntax error. Attempting to do so at runtime causes an error.
An abstract class can contain data and methods. Some of the methods may in turn be declared to be
abstract
. Abstract methods have no implementations.If a class contains an abstract method, then it must be an abstract class. However, you can have an abstract class that doesn't have any abstract methods.
An abstract method is a method that is declared, but the method's implementation is found in one of the derived classes. In otherwords, the classes that extend an abstract class are responsible for providing implementations of the abstract methods.
Syntax: abstract class SomeClassName { ... }The
Number
class in thejava.lang
package represents the abstract concept of numbers. It is used as a superclass to the wrapper classes (e.g.Integer
andFloat
).public abstract class Number implements java.io.Serializable { public abstract int intValue(); public abstract long longValue(); public abstract float floatValue(); public abstract double doubleValue(); public byte byteValue() { return (byte)intValue(); } public short shortValue() { return (short)intValue(); } }Each wrapper class (e.g.
Byte
,Integer
, etc.) extendsNumber
(except forCharacter
).The
Number
class ensures that there is common functionality across all classes that extend it (e.g.intValue()
).Every class that inherits from
Number
must implement the methods that are defined to beabstract
. TheNumber
class contains a couple of nonabstract methods (shortValue()
andbyteValue()
); in other words, these methods are implemented in the class. If you were to write a class that extendsNumber
, then you would have to check to see if the nonabstracts methods work for you specific type of number. If they don't, then you can provide implementations for the nonabstract methods by overriding them.You cannot instantiate a
Number
object. You can, however, have a handle (i.e. object variable) to aNumber
object (e.g.Number num
). The values that can be assigned to aNumber
object variable are handles to objects instantiated from classes that extend theNumber
class.Number num = new Integer(100); // a typecast is not necessaryDocs.Oracle.com::Tutorial::Abstract Methods and Classes
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Typically, sorting is executed on files that contain records having keys. The keys are used to control the sort.
The objective of a sort is to rearrange records so that their keys are ordered according to some welldefined ordering rule (e.g. numerical order or alphabetical order).
The sorting problem is defined as follows:
Given a set of records r1, r2, ..., r_{n} with key values k1, k2, ..., k_{n}, respectively, arrange the the records into any order s such that records r_{s1}, r_{s2}, ..., r_{sn} have keys obeying the property k_{s1} <= k_{s2} <= ... <= k_{sn}.If the file being sorted can fit into memory, then an internal sort can be done; otherwise, sorting files from a disk (or some other secondary storage device) is called external sorting.
For discussion purposes, we will focus on internal sorting (more specifically, the sorting of arrays).
A characteristic of sorting methods is stability. A sort is stable if it preserves the relative order of equal keys in a file; otherwise, it is nonstable. For example, if an alphabetized class list is sorted by grade, then a stable method produces a list in which students with the same grade are still in alphabetical order, but a nonstable method is likely to produce a list that is no longer in alphabetical order.
The efficiency of a sorting algorithm depends on two measurements:
 the number of comparisons
 the number of swaps
The amount of extra memory used by a sort is important. Extra memory is used by sort in the following ways:
 sort in place using no extra memory except for a small stack or table
 use a linkedlist and each element requires a link pointer
 need enough extra memory to store a copy of the array to be sorted
In general, if the records being sorted are large, then avoid "shuffling" them around by rearranging the elements of an array of pointers (or indicies). This is called indirect sorting.
Swapping adjacent records (i.e. items) is called an exchange.
There are numerous "simple" sorting algorithms are based on comparing and/or exchanging adjacent records  they are: bubbleSort, exchangeSort, selectionSort, and insertionSort.
There are numerous sorting algorithms that might be better than the aforementioned "simple" sorts. Some of these sorts are: shellSort, mergeSort, and quickSort.
Sorting and Searching: The Art of Computer Programming
by Donald E. Knuth is a classic text on the subject of sorting. It covers about 25 different sorting algorithms. The following a quote from the book:"But you can't look up all those license numbers in time," Drake objected. "We don't have to, Paul. We merely arrange a list and look for duplications."  Perry Mason (The Case of the Angry Mourner, 1951)
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
BubbleSort is an exchange sort that is inefficient, but easy to to understand.
Keep passing through the list, exchanging adjacent elements, if necessary; when no exchanges are required on some pass, the file is sorted.
 begin with elements 0 and 1 ('i' and 'j')
 compare two adjacent elements 'i' and 'j'
 if element 'i' less than element 'j', swap them
 move one position to the right
When sorting in ascending order, the largest element "sinks" to the end of the list and the smallest values "bubble up" towards their proper positions near the front of the list.
BubbleSort
pseudocode:// assume we have an array 'a' with length 'n' end_i = n1; while (end_i > 0) { last_i = 0; for (next_i = 0; next_i < end_i; next_i++) { if (COMPARE (a, next_i, next_i+1)) { SWAP (a, next_i, next_i+1); last_i = next_i; } } end_i = last_i; }
BubbleSort
is terrible [O(n^2)] if the list is sorted in reverse order. It works great given a list that is already sorted.YouTube.com::Bubble Sort by CS50 at Harvard
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
In most cases,
InsertionSort
is the best of the simple sorts (i.e.BubbleSort
,ExchangeSort
, andSelectionSort
).
InsertionSort
works well if only a few elements need sorting; however, it is a poor choice if dealing with a large number of elements.Often times
InsertionSort
is used as the final stage of more advanced sorts (e.g.QuickSort
).For an example of
InsertionSort
, assume we have an arrayA
and its length isN
. Let's look at passi
(1 <= i <= N1
). The sublistA[0]
toA[i1]
is already sorted in ascending order. The pass assignsA[i]
to the list. LetA[i]
be the TARGET and move down the list, comparing the target with itemsA[i1]
,A[i2]
, and so forth. Stop the scan at the first elementA[j]
that is less than or equal to TARGET or at the beginning of the list (j=0
). As we move down the list, slide each element to the right (A[j]=A[j1]
). When the correct location forA[i]
is found, insert it at locationj
.Said another way.
Assume elements are being collected using array named 'a'. The initial state is that the first element, considered by itself, is sorted. Each time a new element with value 'n' is "added" to the collection, it is inserted into a slot 'i' such that
a[i1] <= a[i] <= a[i+1]
. If the new element is inserted into the array (i.e. it is not the last element), then the elements to the right of the insertion point must be shifted.Many card players use the insertion sort. They are dealt a hand of cards. Each time they receive a card they place it in their hand in a sorted order. Luckily for them, shifting cards is simple. The following is an example of a card player that stores their cards in ascending order (lowesttohighest).
start with an empty hand receive an 8: 8 //1 element is always sorted receive a 4: 4 8 //4 is inserted, the 8 was shifted receive a 10: 4 8 10 //10 added (no shifting necessary) receive a 2: 2 4 8 10 //4,8,10 all shifted receive a 7: 2 4 7 8 10 //8,10 shifted
InsertionSort
pseudocode.// assume we have an array 'a' with 'n' elements for (cur_i = 1; cur_i < n; cur_i++) { next_i = cur_i; while (next_i > 0) { if (COMPARE (a, next_i, next_i1)) SWAP (a, next_i, next_i1); next_i; } }YouTube.com::Insertion Sort by CS50 at Harvard
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
ExchangeSort sort is an exchange sorts that works as follows: The item at index 0 is compared with each subsequent item in the list at index 1, 2, ..., N1. For each comparison, if the subsequent item is smaller than the element at index 0, the two entries are exchanged. Repeat this process with index 1, index 2 and so on up to index N2.
ExchangeSort
pseudocode:// assume we have an array 'a' with 'n' elements for (cur_i = 0, limit = n1; cur_i < limit; cur_i++) { for (next_i = cur_i+1; next_i < n; next_i++) { if (COMPARE (a, next_i, cur_i)) SWAP (a, next_i, cur_i); } }
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
SelectionSort is a simple sorting algorithm that makes a number of passes through a list (or sublist) and, on each pass, selects one element to be correctly position. Each element is moved only once; therefore, this type of sort can be handy when sorting files with very large records and small keys.
The item at index 0 is compared with each subsequent item in the list at index 1, 2, ..., N1. The index of the smallest item encountered is saved. After the comparisons have been completed, the smallest item is swapped with the item at index 0. Repeat this process with index 1, 2, and so on up to N1.
SelectionSort
pseudocode:// assume we have an array 'a' with 'n' elements for (cur_i = 0, limit = n1; cur_i < limit; cur_i++) { small_i = cur_i; for (next_i = cur_i+1; next_i < n; next_i++) { if (COMPARE (a, next_i, small_i)) small_i = next_i; } if (small_i != cur_i) SWAP (a, cur_i, small_i); }YouTube.com::Selection Sort by CS50 at Harvard
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
ShellSort was discovered by a computer scientist named Donald Shell in 1959. It is also referred to as the diminishing gap sort.
It is based on
InsertionSort
, but adds a new feature that improves performance. The basic idea behind this sort is that in early stages, farapart elements are compared, rather than adjacent ones as in simplier exchange sorts. This tends to eliminate large amounts of disorder quickly, so later stages have less work to do. The interval (i.e. gap) between compared elements is gradually decreased to one, at which point the sort effectively becomes an exchange method. The performance of this algorithm can be influenced by the gaps that are used.
ShellSort
is good for mediumsized arrays (few thousand items). By default,ShellSort
should probably be your choice for sorting. If performance becomes an issue, then change to a more advanced sorting technique such asQuickSort
.
ShellSort
pseudocode:// assume we have an array 'a' with length 'n' for (gap = n/2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) for (j = igap; j >= 0; j = gap) { if (!COMPARE (a, j, j+gap)) break; SWAP (a, j, j+gap); } }YouTube.com::Java Shell Sort by Derek Banas
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
QuickSort was first developed by C.A.R. Hoare. It requires the picking of a partition element (pivot) and then partially sorting the array about the partition. You can then sort each of the two partitions by recursive application of the same technique. The algorithm can sort quite rapidly, but it can also sort very slowly [O(n^2) worst case].QuickSort is a fast divideanconquer algorithm when comparison sorting arrays in place (frequently O(n log n)).
The basic algorithm for QuickSort is recursive and consists of the following steps:
The pivot divides array elements into two groups: those smaller than the pivot and those larger than the pivot.
 If the number of elements is 0 or 1, return.
 Pick any element and call it the pivot.
 Partition remaining elements into two disjoint groups called L and R.
 Return the result of QuickSort(L), followed by the pivot, followed by QuickSort(R).
The partition step places every element except the pivot in one of two groups.
13 81 43 92 31 65 57 26 75 0 Assume 65 is selected as the pivot. Partition the elements. Left: 13 43 31 57 26 0 Right: 81 92 75 Quicksort the left items. Quicksort the right items. 0 13 26 31 43 57 75 81 92 65Example:Original list: 8 1 4 9 6 3 5 2 7 0 Select the pivot 6 and swap the pivot with the last element. 8 1 4 9 0 3 5 2 7 6 Run i from lefttoright, and j from righttoleft. When i sees a large element, i stops. When j sees a small element, j stops. If i and j have not crossed, swap their items and continue; otherwise, stop this loop. i stops at element 8; j stops at element 2 the 8 and 2 are swapped 2 1 4 9 0 3 5 8 7 6 i stops at element 9; j stops at element 5 the 9 and 5 are swapped 2 1 4 5 0 3 9 8 7 6 i stops at element 9; j stops at element 3 i and j have crossed  swap pivot with i'th element (6 with 9) 2 1 4 5 0 3 6 8 7 9Picking the pivot is important to good performance. Never choose the first element as the pivot (you should also avoid the last element). The middle element is usually a reasonable choice. The perfect pivot is one that results in equally sized partitions. Picking a random pivot has proven efficient.The medianofthree is a popular technique for picking a pivot. Sort the first, middle and last elements of the list and use the median (in this case middle) value. Using this technique is good because while in the process of determining the pivot, you are also getting started on the sorting of the list (element 0 will be less than the pivot and element N1 will be greater than the pivot).
QuickSort
pseudocode:quickSort(T a[], int left, int right) if (left >= right) return; SWAP (a, left, (left+right)/2); last = left; for (i = left+1; i <= right; i++) { if (COMPARE (a, i, left) { ++last; SWAP (a, last, i); } } SWAP (a, left, last); quickSort(a, left, last1); quickSort(a, last+1, right);
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
{TopOfPage} {Oracle.com::API Specification  Tutorial} {Derek Banas Videos} {Data Structure Visualizations}
Home  Previous  Next 
