Tietorakenteet, 1. kurssikoe 28.10.2002: Tehtävän 2 arvosteluperusteet ja esimerkkivastaus / Jukka Kohonen

Tehtävänanto

Pisteytys

Määrittelyistä 3 p.
Puutteista ja virheistä yleensä -1 p/kpl, esim.

• viite listan alkupäähän (tms.) puuttuu
• viite käsiteltävään solmuun puuttuu (eikä muutakaan keinoa osoittaa käsiteltävää solmua ole esitetty)
• olennaisia metodeita puuttuu: -1...-2 p

Lisäyksen ja poiston toteutuksesta 4 p.
Puutteista ja virheistä -1...-2 p/kpl, esim.

• ketjurakenne rikkoutuu aina tai jossain erikoistapauksessa

Pienistä Java-koodin syntaksivirheistä ei ole sakotettu.

Tarkennuksia ja huomioita

Määrittelyt

Tarkoitus oli, että lista toteutetaan Java-luokkana, jonka kentät ja metodit esitellään, parametrien tyyppejä myöten.

Solmu-luokassa piti määritellä sekä tietokenttä, että molemmansuuntaiset linkkikentät (next, prev).

Lista-luokan piti tarjota jokin keino osoittaa listan alkupäätä (tai tunnussolmua tms.) ja lisäksi jokin keino osoittaa käsiteltävää solmua listan keskeltä, esim. erillisellä käsiteltävä-viitteellä, iteraattorilla tms.

Metodeita piti esitellä riittävästi. Tyypillisiä Lista-luokan metodeita olisivat:

• konstruktori ja/tai createList
• next (seuraavaan solmuun siirtyminen)
• initialize (alkuun siirtyminen)
• retrieve (käsiteltävän solmun tiedon nouto)
• isEmpty (listan tyhjyyden/epätyhjyyden tutkinta)
• atEnd (ollaanko listan "lopussa")

Vähintään vaadittiin, että listan solmujen sisältämään tietoon on mahdollista päästä käsiksi listan ulkopuolelta - retrieve-metodilla tai muuten.

Koska lista on kaksisuuntainen, olisi luontevaa määritellä myös prev-operaatio (edelliseen solmuun siirtyminen). Tätä ei kuitenkaan vaadittu.

Lisäyksen ja poiston toteutus

Lisäys:

• luotava uusi solmu
• lisättävä se käsiteltävän solmun eteen tai taakse (sellainen toteutus, joka lisää aina listan päähän, ei riitä)
• ketjurakenteen säilyttävä ehjänä molempiin suuntiin; tässä oli yllättävän paljon vaikeuksia. Kun lista on kaksisuuntainen, on lisäyksessä yleensä päivitettävä neljää linkkikenttää:
  • uuden solmun omat prev- ja next-linkit
  • uutta edeltävän solmun next-linkki
  • uuden jäljessä olevan solmun prev-linkki. Varsinkin tämä tuntui unohtuvan.
• toimittava oikein myös erikoistapauksissa:
  • jos lisätään tyhjään listaan (esim. heti luonnin jälkeen)
  • jos lisätään listan jompaankumpaan päähän

Poisto:

• poistettava käsiteltävä solmu (oli se listan päässä tai keskellä)
• ketjurakenteen säilyttävä ehjänä molempiin suuntiin
• toimittava oikein myös erikoistapauksissa:
  • jos lista tyhjenee, sen on kuitenkin pysyttävä ehjänä
  • jos lista oli jo tyhjä, olisi hyvä käsitellä virhe esim. aiheuttamalla poikkeus; tätä ei kuitenkaan vaadittu

Useimmissa ratkaisuissa ei käytetty tunnussolmua, mistä seurasi, että käsiteltäviä erikoistapauksia (listan päitä) tuli aika lailla ja osa sitten unohtui.

Esimerkkivastaus

Tämä vastaus perustuu tunnussolmulliseen rengaslistaan. Ajatuksena on, että erikseen käsiteltävien tapausten määrä minimoituu ja toteutuksesta tulee mahdollisimman yksinkertainen.

Listassa on aina tunnussolmu, ja epätyhjässä listassa lisäksi "oikeita" solmuja. Solmut muodostavat molempiin suuntiin yhtenäisen renkaan: viimeisen solmun next-linkki osoittaa tunnussolmuun, samoin ensimmäisen solmun prev-linkki. (Kun lista on tyhjä, siinä on vain tunnussolmu, ja tunnussolmun next- ja prev-linkit osoittavat tunnussolmuun itseensä. Lista on siis silloinkin (pieni) "rengas".)

Listassa on käsiteltävä-viite, joka osoittaa joko johonkin "oikeaan" solmuun tai tunnussolmuun. Lisäys tapahtuu käsiteltävän alkion eteen. Tämä ratkaisu tekee helpoksi listan alkuun lisäämisen: asetetaan käsiteltäväksi solmuksi listan ensimmäinen solmu ja lisätään sen eteen. Samoin listan loppuun lisääminen onnistuu: asetetaan käsiteltävä-viite osoittamaan tunnussolmua ja lisätään sen eteen, siis viimeisen "oikean" solmun perään. Voidaan siis ajatella, että kun käsiteltävä-viite osoittaa tunnussolmua, ollaan "listan lopussa" (mikä on nyt eri asia kuin listan viimeisessä alkiossa oleminen).

Operaatiot voisi tietysti määritellä toisinkin. Esimerkiksi lisäys voisi tapahtua käsiteltävän solmun perään. On kuitenkin syytä olla tarkkana, että tulee määritelleeksi operaatiot niin, että listan molempiin päihin pystyy tekemään lisäyksiä!

// DList -- doubly-linked circular list with header node (tunnussolmu).
// Data is of type Object.

public class DList {
    
    private class Node {
	private Object data;
	private Node prev;
	private Node next;
    }

    Node header;
    Node current;

    // Constructor
    public DList() {
	header = new Node();                // create a header node
	header.next = header.prev = header; // initialize the "circle"
	current = header;
    }

    // Method declarations:

    // i) movement
    public void next()       { ... };	// move to next node
    public void prev()       { ... };   // move to previous node
    public void initialize() { ... };   // move to beginning

    // ii) access to data
    public Object retrieve() { ... };   // return data of current node
    
    // iii) state query
    public boolean isEmpty() { ... };   // is the list empty?
    public boolean atEnd()   { ... };   // are we at end of list?

    // Implementation for insert and delete:
    
    // Insert before current node.
    // (If we are at end of list, i.e. at the header node, insert at end.)
    public void insert(Object data) {
	// Create new node
	Node n = new Node();
	n.data = data;

	// Insert the new node into the linked structure
	n.prev = current.prev;
	n.next = current;
	current.prev.next = n;
	current.prev = n;
    }

    // Delete current node.
    public void delete() throws EmptyList, AtEnd {
	// Error checking: Is the list empty?
	if (header.next == header)
	    throw new EmptyList();

	// Error checking: Are we at end of list?
	if (current == header)
	    throw new AtEnd();

	// Remove current node from the linked structure
	current.next.prev = current.prev;
	current.prev.next = current.next;

	// Move to next node
	current = current.next;
    }
}