Object Oriented Programming fully
supports this idea.
Set of values:
3
1 7 6 6 2
5 5 4 4 28 28 28 28 30
--------------------------
5 1 - 7 * 6 3 / +
Discussion: Implementation of a stack using arrays.
/**
* Headerless singly linked list, elements are ordered by key field.
* @author Jaanus Poial
* @version 0.8
* @since JDK 1.5
*/
public class Element implements java.util.Iterator<Element>,
Comparable<Element> {
/** key, ordering is defined by the key */
private String key;
/** next element in the list */
private Element next;
/** Default constructor. */
Element() {
this (null, null);
}
/** Constructor with key.
* @param v key
*/
Element (String v){
this (v, null);
}
/** Constructor with key and next.
* @param v key
* @param e next
*/
Element (String v, Element e) {
setKey (v);
setNext (e);
}
/** Getter method for <code> next </code> field.
* @return next element in the list or <code> null </code>.
*/
public Element getNext() {
return next;
}
/** Setter method of the <code> next </code> field.
* @param e value to be stored
* @return "old" value of the field
*/
public Element setNext (Element e) {
Element tmp = next;
next = e;
return tmp;
}
/** Getter method of the <code> key </code> field.
* @return key
*/
public String getKey() {
return key;
}
/** Setter method of the <code> key </code> field.
* @param v key
* @return "old" value of the field
*/
public String setKey (String v) {
String tmp = key;
key = v;
return tmp;
}
/** Comparison of elements. Delegated to comparison of keys.
* @param element second element in comparison
* @return int according to Comparable interface description
*/
@Override
public int compareTo (Element element) {
return getKey().compareTo (element.getKey());
}
//========================================================================
// Standard operations on the list - add, merge, delete, find
//========================================================================
/** Add element to the list.
* @param e element to be added
* @return first element of the changed list
*/
public Element add (Element e) {
if (e == null) return this; // actually, it is an error
if (e == this) return this; // it is an error, too
if (e.getKey().compareTo (getKey()) < 0) { // e.key < this.key
e.setNext (this); // add to the beginning of the list
return e;
}
Element ptr = this; // let us find the right place after ptr
while (ptr.getNext() != null) {
if (e.getKey().compareTo (ptr.getNext().getKey()) < 0) {
// add after ptr
e.setNext (ptr.getNext());
ptr.setNext (e);
return this;
}
ptr = ptr.getNext();
}
ptr.setNext (e); // add to the end
e.setNext (null); // just in case ...
return this;
}
/** Merge lists <code> this </code> and <code> e </code>.
* The result consists of shallow copies of original elements.
* @param e first element of the second list
* @return first element of the resulting list
*/
public Element merge (Element e) {
Element j1 = this; // placeholder in the first list
Element j2 = e; // placeholder in the second list
Element smaller = null; // element to be cloned and added
if (j2 == null) {
smaller = j1;
j1 = j1.getNext(); // here j1 cannot be null
} else if (j2.getKey().compareTo (j1.getKey()) < 0) {
smaller = j2;
j2 = j2.getNext();
} else {
smaller = j1;
j1 = j1.getNext();
}
Element res = new Element (smaller.getKey(), null); // result
Element j = res; // placeholder in the resulting list
while ((j1 != null) && (j2 != null)) { // both lists are non-empty
if (j2.getKey().compareTo (j1.getKey()) < 0) {
smaller = j2;
j2 = j2.getNext();
} else {
smaller = j1;
j1 = j1.getNext();
}
j.setNext (new Element (smaller.getKey(), null));
j = j.getNext();
}
if (j1 == null) j1 = j2; // j1 is the remaining part
while (j1 != null) {
j.setNext (new Element (j1.getKey(), null));
j1 = j1.getNext();
j = j.getNext();
}
return res;
}
/** Delete an element from the list.
* @param e element to be deleted
* @return first element of the changed list or <code> null </code>
*/
public Element delete (Element e) {
if (e == null) return this; // nothing to be deleted (error)
if (e == this) return getNext(); // delete the first element
Element ptr = this;
while (ptr != null) {
if (e == ptr.getNext()) {
ptr.setNext (e.getNext());
}
ptr = ptr.getNext();
}
return this;
}
/** Find an element by the value of key.
* @param key key to use
* @return element or <code> null </code>.
*/
public Element find (String key) {
Element ptr = this;
while (ptr != null) {
if (key.compareTo (ptr.getKey()) == 0) return ptr;
ptr = ptr.getNext();
}
return null;
}
/** String representation uses keys.
* @return list of keys
*/
@Override
public String toString() {
StringBuffer buffer = new StringBuffer();
Element ptr = this;
while (ptr != null) {
buffer.append (ptr.getKey().toString()); // key
if (ptr.getNext() != null)
buffer.append (", "); // delimiter in the middle
else buffer.append (";"); // delimiter in the end
ptr = ptr.getNext();
}
return buffer.toString(); // buffer -> String
}
/** Does there exist a next element.
* @return true or false
*/
@Override
public boolean hasNext() {
return getNext() != null;
}
/** The next element in iterator.
* @return next element
*/
@Override
public Element next() throws java.util.NoSuchElementException {
if (getNext() == null)
throw new java.util.NoSuchElementException();
else
return getNext();
}
@Override
public void remove() {
this.delete (getNext());
}
/** Main method.
* @param param command line arguments
*/
public static void main (String[] param) {
System.out.println ("Start");
Element myList = null;
System.out.println (myList); // null
myList = new Element ("e1");
System.out.println (myList); // e1;
myList = myList.add (null);
System.out.println (myList); // e1;
myList = myList.add (new Element ("e0"));
System.out.println (myList); // e0, e1;
myList = myList.add (new Element ("e3"));
System.out.println (myList); // e0, e1, e3;
myList = myList.add (new Element ("e2"));
System.out.println (myList); // e0, e1, e2, e3;
myList = myList.delete (myList.find ("e4"));
System.out.println (myList); // e0, e1, e2, e3;
myList = myList.delete (myList.find ("e0"));
System.out.println (myList); // e1, e2, e3;
myList = myList.delete (myList.find ("e2"));
System.out.println (myList); // e1, e3;
myList = myList.delete (myList.find ("e3"));
System.out.println (myList); // e1;
myList = myList.delete (myList.find ("e1"));
System.out.println (myList); // null
Element otherList = new Element ("7");
myList = new Element ("5");
myList = myList.add (new Element ("3"));
otherList = otherList.add (new Element ("4"));
Element y = myList.merge (otherList);
System.out.println (y); // 3 4 5 7
System.out.println (myList); // 3 5
System.out.println (otherList); // 4 7
System.out.println ("Finish");
}
}
