# Stack mit listen rekursive implementieren



## kurtisblow (3. Apr 2012)

Hallo,
ich muss einen Stack m.h.v Listen in Java implementieren.
Wir haben bereits ein vorgefertigtes .java file mit allen methoden, die wir nach
JavaDoc Beschrieb lösen sollen. Anschliessend muss ein Junit4 Test erfüllt werden.

Das .java file sieht so aus:


```
package u5a1;

import java.util.NoSuchElementException;
import list.List;

public class Lists {
	

	/**
	 * Returns a string representation of the list.
	 * 
	 * @return a comma-separated list of the list values
	 */
	
	public static String toString(List list)
	{
		if (list == null) return "null";
		
		StringBuffer buf = new StringBuffer();
		buf.append(list.value).append(", ").append(toString(list.next));
		return buf.toString();
	}
	
	/**
	 * Adds a value to at the beginning of a list.
	 * 
	 * @param list the list to which the value is added
	 * @param value the value which is added to the list
	 * @return a new list with the new element first followed by the given list
	 */
	
	public static List add(List list, int value)
	{
		if (list == null){
			return null;
		}
		
		return add(list.next,value);
	}
	
	/**
	 * Retrieves the size of a list.
	 * 
	 * @param list the list in question
	 * @return the number of values in the list.
	 */
	public static int size(List list)
	{
                int index = 0;
		if (list == null)
		{
			return index;
		}
		
		index += 1;
		
		return size(list.next);
	}

	/**
	 * Aggregates the sum of all list values.
	 * 
	 * @param list the list in question
	 * @return the sum of all list values
	 */
	public static int sum(List list)
	{
	}	

	/**
	 * Retrieves the last element of a list.
	 * 
	 * The last element of the empty list is the empty list.
	 * 
	 * @param list the list in question.
	 * @return the last element of the given list.
	 */
	public static List last(List list) 
    {
	}

	/**
	 * Retrieves a sublist of a list.
	 * 
	 * @param list the list in question
	 * @param index a position in the list starting at zero for the head value
	 * @return the sublist with the element indexed by index as head element
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
	}
}
```

Die Methode add(list,value) und die methode size(list)
habe ich bereits zu implementieren versucht.
Ich komme aber einfach nicht weiter und wäre froh, wenn jemand eine
Methode implementieren kann, damit man etwa sieht, wie das Vorgehen ist.
Bei size habe ich das Problem, dass ich einen Index zurückgeben muss, wenn ich ihn
so wie jetzt implementiere, dann wird ja bei jedem Rekursivaufruf index wieder = 0;
Global dürfen wir aber auch nichts hinzufügen, wie kann ich so die listsize zurückgeben?

Lg Kurt


----------



## SlaterB (3. Apr 2012)

hier kannst du abschreiben
http://www.java-forum.org/java-basics-anfaenger-themen/134097-liste.html

ok, nur wenige der noch freien Methoden,
zum Rest kannst dich schon einmal auf einen Verlauf wie im anderen Thema vorbereiten 
konkrete Fragen stellen, fertige Lösungen gibts kaum


----------



## kurtisblow (3. Apr 2012)

Danke, was ich bis jetzt noch nicht fertig gebracht habe ist folgendes:


```
public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) < index || index < 0 || (index == 0 && list == null && size(list) == 0))
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list == null)
		{
			return null;
		}
		return sublist(list.next,index);
		
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
                if (list == null)
		{
			throw new NoSuchElementException();
		}
		if(list.value == value)
		{
			return index(list,value);
		}
		return index(list.next,value);
	}
}
```

Wie kann ich die sublist-Methode weiter implementieren, damit list.next dem index entspricht?


----------



## SlaterB (3. Apr 2012)

'weiter entwickeln' impliziert einen bisherigen Plan, den mag ich im Code aber nicht ganz entdecken 
was hast du denn mit size() usw. vor?
wann willst du überhaupt etwas != null zurückgeben?

bisher sieht es höchstens so aus als verkleinerst du die Liste, bis ihre size() dem Index entspricht,
das ist aber kaum der Plan

ich könnte jetzt eine mögliche Idee verraten, die zu der Rekursion passt, 
das kommt aber der Quelltext-Lösung so eines Zweizeilers ganz schön nahe.., 
dann zumindest bisschen als Frage formuliert: 

wenn der Index 0 ist, was muss dann zurückgegeben werden?
wie sieht es bei Index 1 aus, was von der Liste ist dann die Lösung? 
wie kann das durch Rekursionsaufruf erreicht werden so dass vielleicht schon die nächste Stufe das richtige macht?


----------



## kurtisblow (3. Apr 2012)

Hier nochmal der ganze Code:


```
package u5a1;
//Group SebDav
import java.util.NoSuchElementException;
import list.List;

public class Lists {
	

	/**
	 * Returns a string representation of the list.
	 * 
	 * @return a comma-separated list of the list values
	 */
	
	public static String toString(List list)
	{
		if (list == null) return "null";
		
		StringBuffer buf = new StringBuffer();
		buf.append(list.value).append(", ").append(toString(list.next));
		return buf.toString();
	}
	
	/**
	 * Adds a value to at the beginning of a list.
	 * 
	 * @param list the list to which the value is added
	 * @param value the value which is added to the list
	 * @return a new list with the new element first followed by the given list
	 */
	
	public static List add(List list, int value)
	{
		return new List(value, list);
	}
	
	/**
	 * Retrieves the size of a list.
	 * 
	 * @param list the list in question
	 * @return the number of values in the list.
	 */
	public static int size(List list)
	{
		if (list == null)
		{
			return 0;
		}		
		return 1 + size(list.next);
	}

	/**
	 * Aggregates the sum of all list values.
	 * 
	 * @param list the list in question
	 * @return the sum of all list values
	 */
	public static int sum(List list)
	{
		if (list == null)
		{
            return 0;
        } 
		return list.value + sum(list.next); 
	}	

	/**
	 * Retrieves the last element of a list.
	 * 
	 * The last element of the empty list is the empty list.
	 * 
	 * @param list the list in question.
	 * @return the last element of the given list.
	 */
	public static List last(List list) 
    {
		if (list == null)
		{
			return null;
		}
		
		if (list.next != null)
		{
			return last(list.next);
		}
		return list;
	}

	/**
	 * Retrieves a sublist of a list.
	 * 
	 * @param list the list in question
	 * @param index a position in the list starting at zero for the head value
	 * @return the sublist with the element indexed by index as head element
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) < index || index < 0 || (index == 0 && list == null && size(list) == 0))
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list == null)
		{
			return null;
		}
		return sublist(list.next,index);
		
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
		if (list == null || size(list) < index || index < 0)
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list.value == index)
		{
			return list.value;
		}
		return index(list.next,index);
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
		if (list == null)
		{
			throw new NoSuchElementException();
		}
		
		if(list.value == value)
		{
			return list.value;
		}
		return index(list.next,value);
	}
}
```

Naja, also wenn der index == 0 -> es muss die ganze Liste zurückgegeben werden.
Wenn der index == 1 muss alles ausser das erste Element ausgegeben werden.
Da die Elemente bei add umgekehrt angeordnet werden also alle ausser das letzte.
Ich verstehe einfach auch nicht wie man per Rekursion ohne Laufvariable(Variable die die Rekursionsschritte mitzählt) z.B in index(list,value)
den index zurückgeben kann, wenn man nur die Werte zur Verfügung hat?


----------



## SlaterB (3. Apr 2012)

> Da die Elemente bei add umgekehrt angeordnet werden also alle ausser das letzte.

das glaube ich nicht, das ist jedenfalls nicht so leicht zu machen, dann sehe ich auch Problem mit Laufvariable usw.,

> Wenn der index == 1 muss alles ausser das erste Element ausgegeben werden.

das dagegen passt perfekt zum Listen-Aufbau und perfekt zum Aufbau dieser rekursiven Methode,
ein rekursiver Aufruf ist klar, mit list.next, dies ist dann in der nächsten Methode ohne weitere Änderungen der Rückgabewert,

jetzt ist nur noch die Frage, wieso der nächste Aufruf dann aufhören sollte, 
aufhören tut die Methode bei index 0, aktuell ist der Index 1, und die Länge der Liste verringert sich ja um 1, 
damit ist vielleicht klar, wie auch der Index verändert werden könnte so dass es hinkommt 

überlege das mal weiter, funktioniert so dann auch für beliebig hohe Indexe


----------



## kurtisblow (3. Apr 2012)

Ok, dann müsste ja eigentlich list.next index-mal aufgerufen werden und dann alles normal weitergeführt?
Dann würden ja die indices-ersten Elemente übersprungen? wie aber kann ich list.next index-mal aufrufen ohne etwas zurückzugeben?


----------



## SlaterB (3. Apr 2012)

wie gesagt, der rekursive Aufruf
return sublist(list.next,?);
steht fest, nix mit n-mal aufrufen, du kannst aber einen anderen index übergeben damit auf diese Weise quasi gezählt wird,
schau dir nochmal meine Hinweise an, denkbar einfach


----------



## kurtisblow (3. Apr 2012)

vielleicht irgendetwas so:


```
if(list != null && index > 0)
		{
			return sublist(list.next,index-1);
		}
```


----------



## kurtisblow (3. Apr 2012)

Naja, diese 3 Test will es mir einfach nicht erfüllen?


```
public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) <= index || index < 0 )
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list == null)
		{
			return null;
		}
		
		if(list != null && index > 0)
		{
			return sublist(list.next,index-1);
		}
		
		return sublist(list.next,index); 
		
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) <= index || index < 0)
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list.value == index)
		{
			return index(list,list.value);
		}
		return index(list.next,index);
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
		if (list == null)
		{
			throw new NoSuchElementException();
		}
		
		if(list.value == value)
		{
			return valueAt(list,value);
		}
		return index(list.next,value);
	}
```

Ich habe schon gedebuggt, jedoch wird z.B in sublist(list,index) schon der erste Test nicht erfüllt, da es mir nach dem ersten Durchlauf eine Exceptin wirft.

Die Tests sind folgende:


```
package u5a1;

import java.util.NoSuchElementException;

import list.List;

import org.junit.Test;
import org.junit.Assert;


public class Tests extends list.Tests {
	@Test
	public void add()
	{
		List list = null;
		check(list, "null");
		List list2 = Lists.add(list, 1);
		check(list, "null");
		check(list2, "1, null");
		List list3 = Lists.add(list2, 2);
		check(list, "null");
		check(list2, "1, null");
		check(list3, "2, 1, null");
	}
	
	private void checkSize(List list, int expected)
	{
		Assert.assertEquals(expected, Lists.size(list));
	}
	
	@Test
	public void size()
	{
		checkSize(null, 0);
		checkSize(create(1), 1);
		checkSize(create(1,2), 2);
	}	
	
	private void checkSum(List list, int expected)
	{
		Assert.assertEquals(expected, Lists.sum(list));
	}
	
	@Test
	public void sum()
	{
		checkSum(null, 0);
		checkSum(create(1), 1);
		checkSum(create(1,2), 3);
	}
	
	private void checkLast(List list, String expected)
	{
		check(Lists.last(list), expected);
	}
	
	@Test
	public void last()
	{
		checkLast(null, "null");
		checkLast(create(1), "1, null");
		checkLast(create(1,2), "1, null");
		checkLast(create(1,2,3), "1, null");
	}
	
	@Test(expected = IndexOutOfBoundsException.class)
	public void sublistFail1()
	{
		Lists.sublist(null, 0);
	}

	@Test(expected = IndexOutOfBoundsException.class)
	public void sublistFail2()
	{
		Lists.sublist(create(1), 1);
	}
	
	@Test(expected = IndexOutOfBoundsException.class)
	public void sublistFail3()
	{
		Lists.sublist(create(1,2), 2);
	}
	
	@Test(expected = IndexOutOfBoundsException.class)
	public void sublistFail4()
	{
		Lists.sublist(create(1,2), -1);
	}
	
	private void checkSublist(List list, int index, String expected)
	{
		check(Lists.sublist(list, index), expected);
	}

	@Test
	public void sublist()
	{
		checkSublist(create(1), 0, "1, null");
		checkSublist(create(1,2), 0, "2, 1, null");
		checkSublist(create(1,2), 1, "1, null");
		checkSublist(create(1,2,3), 0, "3, 2, 1, null");
		checkSublist(create(1,2,3), 1, "2, 1, null");
		checkSublist(create(1,2,3), 2, "1, null");
	}

	@Test(expected = IndexOutOfBoundsException.class)
	public void valueAtFail1()
	{
		Lists.valueAt(null, 0);
	}

	@Test(expected = IndexOutOfBoundsException.class)
	public void valueAtFail2()
	{
		Lists.valueAt(create(1), 1);
	}

	@Test(expected = IndexOutOfBoundsException.class)
	public void valueAtFail3()
	{
		Lists.valueAt(create(2), 2);
	}

	@Test(expected = IndexOutOfBoundsException.class)
	public void valueAtFail4()
	{
		Lists.valueAt(create(2), -1);
	}
	
	private void checkValue(List list, int index, int value)
	{
		Assert.assertEquals(value, Lists.valueAt(list, index));
	}
	
	@Test
	public void valueAt()
	{
		checkValue(create(1), 0, 1);
		checkValue(create(1,2), 0, 2);
		checkValue(create(1,2), 1, 1);
		checkValue(create(1,2,3), 0, 3);
		checkValue(create(1,2,3), 1, 2);
		checkValue(create(1,2,3), 2, 1);
	}
	
	@Test(expected = NoSuchElementException.class)
	public void findFail1()
	{
		Lists.index(null, 1);
	}

	@Test(expected = NoSuchElementException.class)
	public void findFail2()
	{
		Lists.index(create(1), 2);
	}
	
	@Test(expected = NoSuchElementException.class)
	public void findFail3()
	{
		Lists.index(create(1,2), 3);
	}
	
	private void checkFind(List list, int value, int index)
	{
		Assert.assertEquals(index, Lists.index(list, value));
	}
	
	@Test
	public void find()
	{
		checkFind(create(1), 1, 0);
		checkFind(create(1,2), 1, 1);
		checkFind(create(1,2), 2, 0);
		checkFind(create(1,2,3), 1, 2);
		checkFind(create(1,2,3), 2, 1);
		checkFind(create(1,2,3), 3, 0);	
	}
}
```


----------



## SlaterB (3. Apr 2012)

```
if(list != null && index > 0)
        {
            return sublist(list.next,index-1);
        }
        
        return sublist(list.next,index);
```
nur wenn das if erfüllt ist soll der rekursive Aufruf erfolgen, wieso danach auch noch?
danach gehört natürlich 
> return list;
und gut ist

wenn direkt davor
> if(list == null)
steht, musst du eigentlich auch nicht auf != null prüfen..

--------

valueAt() arbeitet ähnlich mit dem Index, 
bei index() musst du die Rückgabe hochzählen

naja, alles braucht einen Kopf zum Denken, ist am Anfang sicher nicht leicht


----------



## Frank Jüstel (3. Apr 2012)

Das ist doch eine tolle Sache


----------



## kurtisblow (3. Apr 2012)

Danke, fast alles geschafft,
nur sehe ich hier einfach keinen Fehler:


```
public static int index(List list, int value) throws NoSuchElementException
	{
		if (list == null)
		{
			throw new NoSuchElementException();
		}
		
		if(list.value == value)
		{
			return list.value-value;
		}
		return index(list.next,value);
	}
```

Was könnte da an der Abbruchbedinung falsch sein?


----------



## SlaterB (3. Apr 2012)

was könnte daran denn richtig sein, was stellst du dir überhaupt als Ziel der Methode vor?
da [c]list.value == value[/c] gilt, wie dein if voraussetzt, ist der Rückgabewert [c]list.value-value[/c] in jedem Fall 0,
eine Methode also, die immer 0 zurückgibt, wenn nicht schlimmeres wie Exception

ist das ein Fortschritt in der Welt des 21. Jahrhunderts?

auch sonst könnte eine Value von z.B. 34473987 wenig zur Berechnung des Rückgabewerts beitragen oder?
denn das Ziel der Methode ist doch anscheinend, den Index, Position 0, 1, 2, 3 oder 4 oder normalerweise sonst was niedriges zurückzugeben,
hier musst du offensichtlich die Anzahl der rekursiven Aufrufe zählen,
wie gesagt nach dem Fund + return noch weiter hochzählen


----------



## kurtisblow (3. Apr 2012)

```
package u5a1;
//Group SebDav
import java.util.NoSuchElementException;
import list.List;

public class Lists {
	

	/**
	 * Returns a string representation of the list.
	 * 
	 * @return a comma-separated list of the list values
	 */
	
	public static String toString(List list)
	{
		if (list == null) return "null";
		
		StringBuffer buf = new StringBuffer();
		buf.append(list.value).append(", ").append(toString(list.next));
		return buf.toString();
	}
	
	/**
	 * Adds a value to at the beginning of a list.
	 * 
	 * @param list the list to which the value is added
	 * @param value the value which is added to the list
	 * @return a new list with the new element first followed by the given list
	 */
	
	public static List add(List list, int value)
	{
		return new List(value, list);
	}
	
	/**
	 * Retrieves the size of a list.
	 * 
	 * @param list the list in question
	 * @return the number of values in the list.
	 */
	public static int size(List list)
	{
		if (list == null)
		{
			return 0;
		}		
		return 1 + size(list.next);
	}

	/**
	 * Aggregates the sum of all list values.
	 * 
	 * @param list the list in question
	 * @return the sum of all list values
	 */
	public static int sum(List list)
	{
		if (list == null)
		{
            return 0;
        } 
		return list.value + sum(list.next); 
	}	

	/**
	 * Retrieves the last element of a list.
	 * 
	 * The last element of the empty list is the empty list.
	 * 
	 * @param list the list in question.
	 * @return the last element of the given list.
	 */
	public static List last(List list) 
    {
		if (list == null)
		{
			return null;
		}
		
		if (list.next != null)
		{
			return last(list.next);
		}
		return list;
	}

	/**
	 * Retrieves a sublist of a list.
	 * 
	 * @param list the list in question
	 * @param index a position in the list starting at zero for the head value
	 * @return the sublist with the element indexed by index as head element
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static List sublist(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) <= index || index < 0 )
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(list == null)
		{
			return null;
		}
		
		if(index > 0)
		{
			return sublist(list.next,index-1);
		}
		
		return list; 
		
	}
	
	/**
	 * Retrieves the value at a position of a list.
	 * 
	 * @param list the list from which the value is selected
	 * @param index a position in the list starting at zero for the head element.
	 * @return the value at position index
	 * @throws IndexOutOfBoundsException if the list is smaller than index
	 */
	public static int valueAt(List list, int index) throws IndexOutOfBoundsException
	{
		if (size(list) <= index || index < 0)
		{
			throw new IndexOutOfBoundsException();
		}
		
		if(index != 0)
		{
			return valueAt(list.next,index-1);
		}
		return list.value;
	}

	/**
	 * Retrieves the index of the first occurrence of a value  in a list.
	 * 
	 * @param list the list in which the value is searched
	 * @param value the value which is searched
	 * @return the index of the first occurrence of value in the list, starting with zero for the head.
	 * @throws NoSuchElementException if the given value is not in the list
	 */
	public static int index(List list, int value) throws NoSuchElementException
	{
		if (list == null || value > size(list))
		{
			throw new NoSuchElementException();
		}		
		return list.value-value;
		
	}
}
```


----------



## Firephoenix (3. Apr 2012)

Beim dem Post über mir muss ich an den Spruch
<You write "pls" because it is shorter than "please" and I will answer "no" because its shorter than "yes">
denken.

Der TO hat offenbar keine Probleme mehr sonst hätte er Fragen gestellt und den Code sicherlich aus Freundlichkeit für Leser gepostet die über die Suche hier landen...

.
.
.


musste sein 


Anmerkungen beim Drüberlesen:
-deine toString wird am ende immer den String null anhängen, ist das gewollt?
-zur Value: 





> auch sonst könnte eine Value von z.B. 34473987 wenig zur Berechnung des Rückgabewerts beitragen oder?


Hast du dir den Beitrag von SlaterB durchgelesen bevor du deinen Code drunter kopiert hast?
Falls nein mach das mal und überleg dir dann was diese Codezeile macht:

```
value > size(list)
```
Gruß


----------

