TP2/Liste.java

   1
   2 @ClassPreamble (
   3     author = "Jérôme Benoit",
   4     date = "05/12/2011"
   5 )
   6 public class Liste extends Structure {
   7
   8     private class IntNode {
   9         private int data;
  10         private IntNode next;
  11
  12         IntNode(int value) {
  13             setData(value);
  14             setNext(null);
  15         }
  16
  17         IntNode(int value, IntNode nextNode) {
  18             setData(value);
  19             setNext(nextNode);
  20         }
  21
  22         public int getData() {
  23             return data;
  24         }
  25
  26         public void setData(int value) {
  27             data = value;
  28         }
  29
  30         public IntNode getNext() {
  31             return next;
  32         }
  33
  34         public void setNext(IntNode nextNode) {
  35             next = nextNode;
  36         }
  37
  38     }
  39
  40     private IntNode headNode;
  41     private int list_counter;
  42
  43     Liste() {
  44         setHeadNode(null);
  45         setSize(0);
  46     }
  47
  48     private boolean isEmpty()
  49     {
  50         return getHeadNode() == null;
  51     }
  52
  53     public int getSize() {
  54         return list_counter;
  55     }
  56
  57     public void setSize(int size) {
  58         list_counter = size;
  59     }
  60
  61     public void setHeadNode(IntNode node) {
  62         headNode = node;
  63     }
  64
  65     public IntNode getHeadNode() {
  66         return headNode;
  67     }
  68
  69     public boolean inserer(int value) {
  70         boolean found = false;
  71         if (isEmpty()) {
  72             headNode = new IntNode(value);
  73             list_counter++;
  74             return true;
  75         } else if (value == headNode.getData()) {
  76             found = true;
  77             return true;
  78         } else {
  79             IntNode nodeCursorNext = headNode.getNext();
  80             while (nodeCursorNext != null) {
  81                 if (value == nodeCursorNext.getData()) {
  82                     found = true;
  83                     break;
  84                 } else {
  85                     nodeCursorNext = nodeCursorNext.getNext();
  86                 }
  87             }
  88             if (!found) {
  89                 headNode = new IntNode(value, headNode);
  90                 list_counter++;
  91             }
  92             // Insertion in a linked list can't fail
  93             return true;
  94         }
  95     }
  96
  97     public boolean supprimer(int value) {
  98         boolean deleted = false;
  99         if (isEmpty()) {
 100             return deleted;
 101         } else if (value == headNode.getData()) {
 102             headNode = headNode.getNext();
 103             deleted = true;
 104             list_counter--;
 105         } else {
 106             IntNode nodeCursor = headNode;
 107             IntNode nodeCursorNext = headNode.getNext();
 108             while (nodeCursorNext != null) {
 109                 if (value == nodeCursorNext.getData()) {
 110                     nodeCursor.setNext(nodeCursorNext.getNext());
 111                     deleted = true;
 112                     list_counter--;
 113                     break;
 114                 } else {
 115                     nodeCursor = nodeCursorNext;
 116                     nodeCursorNext = nodeCursorNext.getNext();
 117                 }
 118             }
 119         }
 120         return deleted;
 121     }
 122
 123     public void afficher() {
 124         String className = this.getClass().getSimpleName();
 125         int i = 0;
 126         System.out.println("---- " + className + " ----");
 127         if (isEmpty()) {
 128             return;
 129         } else if (headNode.getNext() == null) {
 130             System.out.println("element " + i + " : " + headNode.getData());
 131         } else {
 132             IntNode nodeCursorNext = headNode.getNext();
 133             System.out.println("element " + i + " : " + headNode.getData());
 134             i++;
 135             while (nodeCursorNext != null) {
 136                 System.out.println("element " + i + " : " + nodeCursorNext.getData());
 137                 nodeCursorNext = nodeCursorNext.getNext();
 138                 i++;
 139             }
 140         }
 141     }
 142
 143     public void compacter(int nElements) {
 144         // Remove the first nElements
 145         if (isEmpty() || nElements == 0) {
 146             return;
 147         } else if (headNode != null && headNode.getNext() == null) {
 148             headNode = null;
 149         } else {
 150             // We have at least 2 nodes in the linked list
 151             IntNode nodeCursor = headNode;
 152             int i = 0;
 153             // Go to the node at the nElements place
 154             while (i < nElements - 1 && nodeCursor.getNext() != null && nElements > 1) {
 155                 nodeCursor = nodeCursor.getNext();
 156                 i++;
 157             }
 158             // Set the nElements + 1 node as the root node
 159             // It might be null
 160             setHeadNode(nodeCursor.getNext());
 161         }
 162     }
 163
 164 }