package list; // listes simplement chaînées public class Singly { public int element; public Singly next; public Singly(int element, Singly next) { this.element = element; this.next = next; } public static int length(Singly s) { int len = 0; for ( ; s != null; s = s.next) len++; return len; } public static boolean contains(Singly s, int x) { while (s != null) { if (s.element == x) return true; s = s.next; } return false; } public static int get(Singly s, int i) { for (; s != null; s = s.next) if (i-- == 0) return s.element; throw new IllegalArgumentException(); } /* algorithme de détection de cycle de Floyd * (dit algorithme du lièvre et de la tortue) */ public static boolean hasCycle(Singly s) { if (s == null) return false; Singly tortoise = s, hare = s.next; while (tortoise != hare) { if (hare == null) return false; hare = hare.next; if (hare == null) return false; hare = hare.next; tortoise = tortoise.next; } return true; } /* tirage aléatoire dans une liste * (en un seul parcours) */ public static int randomElement(Singly s) { if (s == null) throw new IllegalArgumentException(); int candidate = 0, index = 1; while (s != null) { if ((int)(index * Math.random()) == 0) candidate = s.element; index++; s = s.next; } return candidate; } public static String listToString(Singly s) { StringBuffer sb = new StringBuffer("["); while (s != null) { sb.append(s.element); if (s.next != null) sb.append(" -> "); s = s.next; } return sb.append("]").toString(); } public String toString() { return listToString(this); } public static void main(String[] args) { Singly x = new Singly(1, new Singly(2, new Singly(3, null))); System.out.println(listToString(x)); System.out.println(x); assert (Singly.get(x, 0) == 1); assert (Singly.get(x, 1) == 2); assert (Singly.get(x, 2) == 3); assert Singly.length(x) == 3; try { Singly.get(x, 3); assert false; } catch (IllegalArgumentException e) {}; try { Singly.get(x, -1); assert false; } catch (IllegalArgumentException e) {}; System.out.println("Singly OK"); } }