[胡扯]java和scala的链表的嵌套循环实现

一个很简单的问题，不过今天被问到了，一下子也说不出应该调用哪个方法，想想挺好玩：有一个linkedlist，现在要对它做遍历，对遍历到的每一个元素A，需要对从A到尾节点的所有元素再进行一次遍历,完成一个嵌套循环

 

最直接的方式就是：

 

 int index = 0;
        for (Iterator<Integer> i = list.iterator(); i.hasNext();) {
            Integer num = i.next();
            index++;

            boolean startLoopWork = false;
            int innerIndex = 0;
            for(Iterator<Integer> j = list.iterator(); i.hasNext();) {
                Integer num2 = j.next();
                innerIndex++;
                startLoopWork = startLoopWork || index == innerIndex-1;
                if (startLoopWork) {
                    // do something
                    System.out.println(num + ":" + num2);
                }
            }
        }

 

虽然直接，但是意图表达的不是很直接，那么在内层就直接对sublist进行遍历吧：

 

        int anotherIndex = 0;
        for (Iterator<Integer> i = list.iterator(); i.hasNext();anotherIndex++) {
            Integer num = i.next();

            if (anotherIndex >= list.size()) break;
            List<Integer> subList = list.subList(anotherIndex+1, list.size());
            for(Iterator<Integer> j = subList.iterator(); j.hasNext();) {
                Integer num2 = j.next();
                // do something
                System.out.println(num + ":" + num2);
            }
        }

 

 

这个实际上也就是list.listIterator(index)做的事情，恩，list已经有这样的一个接口了：

 

for (ListIterator<Integer> i = list.listIterator(); i.hasNext();) {
            Integer num = i.next();

            for (Iterator<Integer> innerIterator = list.listIterator(i.nextIndex()); innerIterator.hasNext();) {
                Integer innerNum = innerIterator.next();
                // do something
                System.out.println(num + ":" + innerNum);
            }
        }

 

这样的实现下，innerIterator是一个O(n)算法，不过由于链表中的元素是private的Entry对象，对外不可见，所以...我觉得这个限制使得扩展性不够好，不知道有什么特别考虑么？望知道的朋友告知

 

最后看一个scala的实现，scala中对链表统一抽象成head::rest：

 

@tailrec

def doubleIterate[A](list: List[A])(f: (A, Option[A]) => Unit): Unit = {
    list match {
      case (head :: Nil) => f(head, None)
      case (head :: rest) =>
        rest.foreach (each => f(head, Some(each)))
        doubleIterate(rest)(f)
    }
  }

 

借助了scala的模式匹配机制，虽然写起来一样的繁琐，但是意图表达的比较清楚

 

这个实现的问题是只能应用于链表，而无法应用到其他的可以迭代的结构，比如array，string等，不过scala中并没有提供像java这样直接的api，所以为了能对所有具有iterable特性的数据结构进行这样的操作，还是只能回到原始的做法：

 

 def doubleIterateIterable[A](iterable: Iterable[A])(f: (A, A) => Unit) = {
    var index = 0
    iterable.foreach { i =>
      index = index + 1
      iterable.iterator.drop(index).foreach(j => f(i, j))
    }
  }

这里，间接性主要来自于闭包，不过scala的iterable特性没有提供foreachWithIndex这样的方法。话说java中应该也有类似drop的接口吧。