verkettete Liste

rapier · 13. Januar 2005

Hallo,
ich bin gerade dabei, eine Listenklasse (doppelt verkettete Liste) zu schreiben.
Doch leider geht es nicht so wie ich mir das vorstelle (oder ich schau schon zu lange da drauf und sehe was einfaches nicht)
Die Listenklasse sieht folgendermaßen aus:

PHP:

class ListItem extends Klasse {
	var $_data;
	var $_prev;
	var $_next;

	function ListItem($item = NULL) {
		$this->_prev = $this->_next = NULL;
		$this->_data = $item;
	}
}
class ChainedList extends Klasse{

	/* Private: */
	var $_head = NULL;
	var $_tail = NULL;
	var $_actual = NULL;
	var $_items = 0;

	/* Public: */
	function ChainedList() {}
	function getFirst() {
		if (!$this->_head) {
			$this->setError('Kann Kopfelement nicht finden');
			return NULL;
		}
		$this->_actual = $this->_head;
		return $this->_actual->_data;
	}

	function getLast() {
		if (!$this->_tail) {
			$this->setError('Kann Tailelement nicht finden');
			return NULL;
		}
		$this->_actual = $this->_tail;
		return $this->_actual->_data;
	}

	function getNext() {
		if (!$this->_actual) {
			$this->setError('Kein aktuelles Element verf&uuml;gbar');
			return NULL;
		}
		$this->_actual = $this->_actual->_next;
		if (!$this->_actual) {
			$this->setError('Kein aktuelles Element verf&uuml;gbar');
			return NULL;
		}
		return $this->_actual->_data;
	}

	function getPrev() {
		if (!$this->_actual) {
			$this->setError('Kein aktuelles Element verf&uuml;gbar');
			return NULL;
		}
		$this->_actual = $this->_actual->_prev;
		if (!$this->_actual) {
			$this->setError('Kein aktuelles Element verf&uuml;gbar');
			return NULL;
		}
		return $this->_actual->_data;
	}

	function insertBefore($item) {
		$tmp = new ListItem($item);

		/* Haenge vorne an, wenn kein aktuelles Element */
		if (!$this->_actual) {
			$this->_actual = $this->_head;
		}
		/* Ist Liste leer? */
		if ($this->_actual == NULL) {
			$this->_head = $this->_tail = $tmp;
			$tmp->_prev = $tmp->_next = NULL;
		}else{
			$tmp->_prev = $this->_actual->_prev;
			$tmp->_next = $this->_actual;
			$this->_actual->_prev = $tmp;

			/* Gibt es ein Vorgaengerelement? */
			if ($tmp_>_prev) {
				$tmp->_prev->_next = $tmp;
			}else{
				/* Kein Vorgaengerelement - Head auf aktuelles Element setzen */
				$this->_head = $tmp;
// 				$tmp->_prev = NULL;
			}
		}
		$this->_actual = $tmp;
		$this->_items++;
		return TRUE;
	}

	function insertBehind($item) {
		$tmp = new ListItem($item);

		/* Haenge vorne an, wenn kein aktuelles Element */
		if (!$this->_actual) {
			$this->_actual = $this->_tail;
		}
		/* Ist Liste leer? */
		if ($this->_actual == NULL) {
			$this->_head = $this->_tail = $tmp;
			$tmp->_prev = $tmp->_next = NULL;
		}else{
			$tmp->_prev = $this->_actual;
			$tmp->_next = $this->_actual->_next;
			$this->_actual->_next = $tmp;

			/* Gibt es ein Vorgaengerelement? */
			if ($tmp_>_next) {
				$tmp->_next->_prev = $tmp;
			}else{
				/* Kein Vorgaengerelement - Head auf aktuelles Element setzen */
				$this->_tail = $tmp;
				$tmp->_next = NULL;
			}
		}
		$this->_actual = $tmp;
		$this->_items++;
		return TRUE;
	}

	function insertHead($item) {
		$this->_actual = $this->_head;
		return $this->insertBefore($item);
	}

	function insertTail($item) {
		$this->_actual = $this->_tail;
		return $this->insertBehind($item);
	}
}

Wenn ich jetzt mit

PHP:

$list = new ChainedList();

$list->insertHead('eins<br />');
$list->insertHead('zwei<br />');
$list->insertHead('drei<br />');

eine Liste mit drei Einträgen erzeuge, ist Head bzw. Tail Eintrag korrekt gesetzt. Das durchgehen der Liste mit

PHP:

echo $list->getFirst();
echo $list->getNext();
echo $list->getNext();
echo $list->getNext();

funktioniert problemlos, leider jedoch nicht die umgekehrte Richtung. Ein

PHP:

echo $list->getLast();
echo $list->getPrev();
echo $list->getPrev();
echo $list->getPrev();

bringt mir nur den letzten Eintrag.

Wenn ich statt insertHead() ein insertTail() verwende ist es das gleiche gespiegelt - dann geht getFirst() / getNext() nicht und getLast() / getPrev() funktioniert ordnungsgemäß.

Ich hab scheinbar irgendwo eine Verknüpfung durcheinandergehauen, nur leider finde ich die nicht.

Besten Dank schonmal für's anschauen
Frank

verkettete Liste

rapier

Grünschnabel

Neue Beiträge