题目:打开一个文本文件,每次读取一行内容,将每行作为一个String读入,并将那个String对象置入一个LinkedList中,按照相反的顺序打印出LinkedList中的所有行.
解题代码:
1 public static List<String> read(String filename) throws Exception { 2 String filepath = "path"; 3 FileReader fileReader = new FileReader(filepath + filename); 4 BufferedReader in = new BufferedReader(fileReader); 5 List<String> list = new LinkedList<String>(); 6 String s; 7 while((s = in.readLine()) != null) 8 list.add(s + "\n"); 9 in.close(); 10 return list; 11 } 12 public static void main(String[] args) throws Exception{ 13 List<String> list = read("filename"); 14 for(ListIterator<String> it = list.listIterator(list.size()); it.hasPrevious();) 15 System.out.print(it.previous()); 16 } 题目中: 将那个String对象置入一个LinkedList中,按照相反的顺序打印出LinkedList中的所有行.对应代码时 for(ListIterator<String> it = list.listIterator(list.size()); it.hasPrevious();) System.out.print(it.previous()); 通过调用LinkedList的listIterator(),返回一个指向链表最后一个元素的指针,在从后向前遍历. 先看一下ListIterator接口的定义: 1 public interface ListIterator<E> extends Iterator<E> { 2 //Iteator接口定义的方法. 3 boolean hasNext(); 4 E next(); 5 void remove(); 6 7 boolean hasPrevious(); 8 E previous(); 9 int nextIndex(); 10 int previousIndex(); 11 void set(E e); 12 void add(E e); 13 }在看一下LinkedList类中对ListIterator接口的实现:
1 private class ListItr implements ListIterator<E> { 2 //lastReturned为最近返回的节点,当调用previous()时,lastReturned = next; 3 private Node<E> lastReturned; 4 //next为当前节点的下一个节点. 5 private Node<E> next; 6 //nextIndex的范围是0-(size-1)(链表的长度减一).表示下个节点在链表中的位置. 7 private int nextIndex; 8 private int expectedModCount =modCount; 9 10 ListItr(int index) { 11 /* 12 *如果index等于size,则表示要跳转到链表的末端,则next=null,否则调用node(index). 13 *nextIndex被赋值为index. 14 */ 15 next = (index == size) ? null : node(index); 16 nextIndex = index; 17 } 18 //nextIndex的合理范围在0-(size-1) 19 public boolean hasNext() { 20 return nextIndex < size; 21 } 22 23 public E next() { 24 checkForComodification(); 25 //判断是否有下一个值. 26 if(!hasNext()) 27 throw new NoSuchElementException(); 28 lastReturned = next; 29 next = next.next; 30 nextIndex++; 31 return lastReturned.item; 32 } 33 //nextIndex的范围在0-(size-1),所以只要nextIndex>0,就表示当前节点有前节点. 34 public boolean hasPrevious() { 35 return nextIndex > 0; 36 } 37 //当调用previous时,lastReturned等于next. 38 public E previous() { 39 checkForComodification(); 40 if(!hasPrevious()) 41 throw new NoSuchElementException(); 42 将lastReturned = next. 43 lastReturned = next = (next == null) ? last : next.prev; 44 nextIndex--; 45 return lastReturned.item; 46 } 47 48 public int nextIndex() { 49 return nextIndex; 50 } 51 52 public int previousIndex() { 53 return nextIndex - 1; 54 } 55 //remove()移除的是lastReturned节点. 56 public void remove() { 57 checkForComodification(); 58 if(lastReturned == null) 59 throw new IllegalStateException(); 60 Node<E> lastNext = lastReturned.next; 61 //移除lastReturned 62 /* 63 *首先要考虑如果要删除的是链表中的第一个/最后一个节点. 64 *按照正常情况: 65 *lastReturned.prev.next = lastReturned.next; 66 *lastReturned.next.prev = lastReturned.prev; 67 *lastReturned.next,lastReturned.prev,lastReturned.item设置为null; 68 *链表长度减一. 69 */ 70 unlink(lastReturned); 71 if(next == lastReturned) 72 next = lastNext; 73 else 74 nextIndex--; 75 lastReturned = null; 76 expectedModCount++; 77 } 78 79 public void set(E e) { 80 if(lastReturned == null) 81 throw new IllegalStateException(); 82 checkForComodification(); 83 lastReturned.item = e; 84 } 85 //向链表中添加节点. 86 public void add(E e) { 87 checkForComodification(); 88 lastReturned = null; 89 //如果next==null,表示要插入到链表的末端. 90 if(next == null) 91 linkLast(e); 92 //否则插入到链表 93 else 94 linkBefore(e, next); 95 nextIndex++; 96 expectedModCount++; 97 } 98 99 final void checkForComodification() { 100 if(modCount != expectedModCount) 101 throw new ConcurrentModificationException(); 102 } 103 } 104 //采用二分法的形式,跳转的链表中第index个节点. 105 Node<E> node(int index) { 106 // assert isElementIndex(index); 107 //size >> 1 表示size/2 108 if (index < (size >> 1)) { 109 //first是链表的第一个节点 110 Node<E> x = first; 111 //从前向后查找 112 for (int i = 0; i < index; i++) 113 x = x.next; 114 return x; 115 } else { 116 //last是链表的最后一个节点. 117 //从后向前查找. 118 Node<E> x = last; 119 for (int i = size - 1; i > index; i--) 120 x = x.prev; 121 return x; 122 } 123 } 124 // 125 E unlink(Node<E> x) { 126 final E element = x.item; 127 final Node<E> next = x.next; 128 final Node<E> prev = x.prev; 129 //如果要删除的是第一个元素,则x.prev == null;需要将链表中的第一个节点first标记为next. 130 if(prev == null) 131 first = next; 132 //否则按照正常逻辑x.prev.next = x.next.在将当前节点的prev设置为null. 133 else { 134 prev.next = next; 135 x.prev = null; 136 } 137 //如果要删除的是最后一个元素,则x.next== null;需要将链表中最后一个几点last标记为prev. 138 if(next == null) 139 last = prev; 140 //否则按照正常逻辑x.next.prev = x.prev.将当前节点的next设置为null. 141 else { 142 next.prev = prev; 143 x.next = null; 144 } 145 //将当前节点的item设置为null. 146 x.item = null; 147 //链表长度减一. 148 size--; 149 //修改次数加一. 150 modCount++; 151 return element; 152 } 153 /* 154 *向链表的末端添加节点.这里需要考虑如果链表为空,链表不为空. 155 *要写出优秀的代码,要将链表为空和不为空都执行的部分提取出来,之后在考虑不一样的情况. 156 */ 157 void linkLast(E e) { 158 final Node<E> l = last; 159 final Node<E> newNode = new Node<E>(l, e, null); 160 last = node; 161 //l == null 的话,表示链表为空.将first设置为newNode 162 if(l == null) 163 first = newNode; 164 //如果链表不为空,将原来链表的最后一个节点.next = newNode. 165 else 166 l.next = newNode; 167 size++; 168 modCount++; 169 } 170 /*在succ节点前,添加节点.要考虑succ是不是头节点. 171 * 172 */ 173 void linkBefore(E e, Node<E> succ) { 174 final Node<E> pred = succ.prev; 175 Node<E> newNode = new Node<E>(pred, e, succ); 176 succ.prev = newNode; 177 //如果succ是头节点,则pred = succ.prev == null.将头节点设置为newNode 178 if(pred == null) 179 first = newNode; 180 else 181 prev.next = newNode; 182 size++; 183 modCount++; 184 }
转载于:https://www.cnblogs.com/flytoworld/p/10563660.html
