题目:打开一个文本文件,每次读取一行内容,将每行作为一个String读入,并将那个String对象置入一个LinkedList中,按照相反的顺序打印出LinkedList中的所有行.
解题代码:
public static List<String> read(String filename) throws Exception {
String filepath = "path";
FileReader fileReader = new FileReader(filepath + filename);
BufferedReader in = new BufferedReader(fileReader);
List<String> list = new LinkedList<String>();
String s;
while((s = in.readLine()) != null)
list.add(s + "\n");
in.close();
return list;
}
public static void main(String[] args) throws Exception{
List<String> list = read("filename");
for(ListIterator<String> it = list.listIterator(list.size()); it.hasPrevious();)
System.out.print(it.previous());
}
题目中:将那个String对象置入一个LinkedList中,按照相反的顺序打印出LinkedList中的所有行.对应代码时
for(ListIterator<String> it = list.listIterator(list.size()); it.hasPrevious();)
System.out.print(it.previous());
通过调用LinkedList的listIterator(),返回一个指向链表最后一个元素的指针,在从后向前遍历.
先看一下ListIterator接口的定义:
public interface ListIterator<E> extends Iterator<E> {
//Iteator接口定义的方法.
boolean hasNext();
E next();
void remove();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void set(E e);
void add(E e);
}
在看一下LinkedList类中对ListIterator接口的实现:
private class ListItr implements ListIterator<E> {
//lastReturned为最近返回的节点,当调用previous()时,lastReturned = next;
private Node<E> lastReturned;
//next为当前节点的下一个节点.
private Node<E> next;
//nextIndex的范围是0-(size-1)(链表的长度减一).表示下个节点在链表中的位置.
private int nextIndex;
private int expectedModCount =modCount;
ListItr(int index) {
/*
*如果index等于size,则表示要跳转到链表的末端,则next=null,否则调用node(index).
*nextIndex被赋值为index.
*/
next = (index == size) ? null : node(index);
nextIndex = index;
}
//nextIndex的合理范围在0-(size-1)
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
//判断是否有下一个值.
if(!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
//nextIndex的范围在0-(size-1),所以只要nextIndex>0,就表示当前节点有前节点.
public boolean hasPrevious() {
return nextIndex > 0;
}
//当调用previous时,lastReturned等于next.
public E previous() {
checkForComodification();
if(!hasPrevious())
throw new NoSuchElementException();
将lastReturned = next.
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
//remove()移除的是lastReturned节点.
public void remove() {
checkForComodification();
if(lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
//移除lastReturned
/*
*首先要考虑如果要删除的是链表中的第一个/最后一个节点.
*按照正常情况:
*lastReturned.prev.next = lastReturned.next;
*lastReturned.next.prev = lastReturned.prev;
*lastReturned.next,lastReturned.prev,lastReturned.item设置为null;
*链表长度减一.
*/
unlink(lastReturned);
if(next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if(lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
//向链表中添加节点.
public void add(E e) {
checkForComodification();
lastReturned = null;
//如果next==null,表示要插入到链表的末端.
if(next == null)
linkLast(e);
//否则插入到链表
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if(modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//采用二分法的形式,跳转的链表中第index个节点.
Node<E> node(int index) {
// assert isElementIndex(index);
//size >> 1 表示size/2
if (index < (size >> 1)) {
//first是链表的第一个节点
Node<E> x = first;
//从前向后查找
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//last是链表的最后一个节点.
//从后向前查找.
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果要删除的是第一个元素,则x.prev == null;需要将链表中的第一个节点first标记为next.
if(prev == null)
first = next;
//否则按照正常逻辑x.prev.next = x.next.在将当前节点的prev设置为null.
else {
prev.next = next;
x.prev = null;
}
//如果要删除的是最后一个元素,则x.next== null;需要将链表中最后一个几点last标记为prev.
if(next == null)
last = prev;
//否则按照正常逻辑x.next.prev = x.prev.将当前节点的next设置为null.
else {
next.prev = prev;
x.next = null;
}
//将当前节点的item设置为null.
x.item = null;
//链表长度减一.
size--;
//修改次数加一.
modCount++;
return element;
}
/*
*向链表的末端添加节点.这里需要考虑如果链表为空,链表不为空.
*要写出优秀的代码,要将链表为空和不为空都执行的部分提取出来,之后在考虑不一样的情况.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<E>(l, e, null);
last = node;
//l == null 的话,表示链表为空.将first设置为newNode
if(l == null)
first = newNode;
//如果链表不为空,将原来链表的最后一个节点.next = newNode.
else
l.next = newNode;
size++;
modCount++;
}
/*在succ节点前,添加节点.要考虑succ是不是头节点.
*
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
Node<E> newNode = new Node<E>(pred, e, succ);
succ.prev = newNode;
//如果succ是头节点,则pred = succ.prev == null.将头节点设置为newNode
if(pred == null)
first = newNode;
else
prev.next = newNode;
size++;
modCount++;
}