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; } // variante : le lièvre va deux fois plus loin à chaque fois, // et la tortue avance à chaque fois jusqu'à la position précédente public static boolean hasCycle2(Singly s) { Singly t = s, h = s; for (int n = 1; true; n *= 2) { for (int k = 0; k < n ; k++) { if (h == null) return false; h = h.next; } for (int k = 0; k < n-1; k++) { if (t == h ) return true; t = t.next; } t = t.next; assert t==h; } } /* 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"); } }