Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 166

Exercise 7.3 (Dynamic insertion for sorting)
Consider sorting an array Dictionary of strings by successively inserting
the array item Dictionary[i] into a linked list of Strings . Provide a
static function static StringList Sort(String [] array) that sorts the string
array into a linked list, and return its head element. What is the time
complexity of this sorting method?
Exercise 7.4 (Sparse polynomial representation)
Consider the following recursive type for representing sparse polynomials
(polynomials with many coecients set to zero):
Program 7.19 A class for manipulating sparse polynomials
class SparsePolynomial
int degree ;
double coefficient ;
SparsePolynomial next ;
SparsePolynomial( int d, double v, SparsePolynomial poly)
this .degree=d;
this . coefficient=v;
this .next=poly;
}
}
Write the following static functions:
- static void Display(SparsePolynomial poly) that displays a poly-
nomial to the console,
- static SparsePolynomial Add(SparsePolynomial p,
SparsePolynomial q) that performs the addition of two polynomials
p and q ,
- static SparsePolynomial Multiply(SparsePolynomial p,
SparsePolynomial q) that calculates the product of two polynomials
p and q .
Exercise 7.5 (String pattern matching)
Given two strings of characters stored in array of char , design a predicate
static boolean occurence(char [] T, char [] M, int i) that re-
ports whether string M is located at index i of string T . The arrays of char-
acters can be extracted from corresponding strings of type String using
the method toCharArray() (for example, String stringt="A simple