effective java书中,为什么常规的递归克隆当链表过长时会导致栈溢出?

 public class HashTable implements Cloneable {  
    private Entry [] buckets = ... ;  

    public static class Entry {  
        final Object key ;  
        Object value ;  
        Entry next ;  

        public Entry(Object key, Object value, Entry next) {  
            this.key = key ;  
            this.value = value ;  
            this.next = next ;  
        }  

        // 递归地深层复制每个链表节点对象   
        Entry deepCopy() {  
            return new Entry(key, value,  
                    next == null ? null : next.deepCopy()) ;  
        }  
    }  

    @Override  
    public HashTable clone() {  
        try {  
            HashTable result = (HashTable) super.clone() ;  
            result.buckets = new Entry[buckets.length] ;  
            //采用循环的方式对每个桶引用的单链表进行深层拷贝  
            for (int i = 0; i < buckets.length; i++) {  
                if (buckets[i] != null) {  
                    result.buckets[i] = buckets[i].deepCopy() ;  
                }  
            }  
            return result ;  
        } catch(CloneNotSupportedException e) {  
            throw new AssertionError() ;  
        }  
    }  
    ...//其余方法省略  
}  

effective java书中说这种方法虽然灵活,但是针对列表中的每个元素,都要消耗一段栈空间。如果链表过长,就容易导致栈溢出。

而如果用迭代的话就可以避免:

 Entry deepCopy() {  
    Entry result = new Entry(key, value, next) ;  
    for (Entry p = result; p.next != null; p = p.next) {  
        p.next = new Entry(p.next.key, p.next.value, p.next.next) ;  
    }  
    return result ;  
}  

想知道为什么会出现栈溢出?用迭代为什么可以避免?求大神解答。

查看全部
yecunsb10049
土成
2017/03/09 03:20
  • 递归
  • java
  • 链表
  • 点赞
  • 收藏
  • 回答
    私信
满意答案
查看全部

2个回复