0

由于节点主要由其链接（下一个和上一个）定义，因此删除一组节点与仅删除一个节点大致相同。你有一个链 -1-2-3-4-5- 并且你删除了一些链接：-1 2-3-4 5-。

public LinkedList<Elem<E>> remove(int from, int to) 
{
    Elem<E> left = head;      
    for (int i=0; i < from; i++) 
    {
        left = left.next;

    }
    Elem<E> right = left;
    for(int i = 0; i< to - from; i++){
      right = right.next;
    }
    // removing the elements from the list;
    left.next = right;
    right.previous = left;
    size -= to - from;

    //left to right are still linked, so just shove them into
    //a new linkedlist and return.
    LinkedList<Elem<E>> ret = new LinkedList<Elem<E>>();
    ret.head = left;
    ret.tail = right;
    return ret;
}

测试类：

import junit.framework.Assert;
import junit.framework.TestCase;
import junit.framework.TestSuite;

public class TestAll extends TestCase {

    public static void testRemoveStart() {

 List<Integer> l1, l2;

 l1 = new LinkedList<Integer>();

 for (int i=0; i<10; i++) {
     l1.add(i);
 }

 l2 = l1.remove(0, 4);

 Assert.assertEquals(5, l2.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i), l2.get(i));
 }

 Assert.assertEquals(5, l1.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i+5), l1.get(i));
 }

    }

    public static void testRemoveMiddle() {

 List<Integer> l1, l2;

 l1 = new LinkedList<Integer>();

 for (int i=0; i<10; i++) {
     l1.add(i);
 }

 l2 = l1.remove(3, 7);

 Assert.assertEquals(5, l2.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i+3), l2.get(i));
 }

 Assert.assertEquals(5, l1.size());

 for (int i=0; i<3; i++) {
     Assert.assertEquals(new Integer(i), l1.get(i));
 }

 for (int i=3; i<5; i++) {
     Assert.assertEquals(new Integer(i+5), l1.get(i));
 }

    }

    public static void testRemoveLast() {

 List<Integer> l1, l2;

 l1 = new LinkedList<Integer>();

 for (int i=0; i<10; i++) {
     l1.add(i);
 }

 l2 = l1.remove(5, 9);

 Assert.assertEquals(5, l2.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i+5), l2.get(i));
 }

 Assert.assertEquals(5, l1.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i), l1.get(i));
 }

    }

    public static void testRemoveOne() {

 List<Integer> l1, l2;

 l1 = new LinkedList<Integer>();

 for (int i=0; i<10; i++) {
     l1.add(i);
 }

 l2 = l1.remove(5, 5);

 Assert.assertEquals(1, l2.size());

 Assert.assertEquals(new Integer(5), l2.get(0));

 Assert.assertEquals(9, l1.size());

 for (int i=0; i<5; i++) {
     Assert.assertEquals(new Integer(i), l1.get(i));
 }

 for (int i=5; i<9; i++) {
     Assert.assertEquals(new Integer(i+1), l1.get(i));
 }

    }

    public static void testExceptions() {

 List<Integer> l;

 l = new LinkedList<Integer>();

 for (int i=0; i<10; i++) {
     l.add(i);
 }

 boolean flag = false;
 try {
     l.remove(-5, -1);
 } catch (IllegalArgumentException e) {
     flag = true;
 } catch (Exception e) {
     ;
 }
 Assert.assertTrue(flag);

 for (int i=0; i<10; i++) {
     Assert.assertEquals(new Integer(i), l.get(i));
 }

 flag = false;
 try {
     l.remove(-1, 5);
 } catch (IllegalArgumentException e) {
     flag = true;
 } catch (Exception e) {
     ;
 }
 Assert.assertTrue(flag);

 for (int i=0; i<10; i++) {
     Assert.assertEquals(new Integer(i), l.get(i));
 }

 flag = false;
 try {
     l.remove(0, 10);
 } catch (IllegalArgumentException e) {
     flag = true;
 } catch (Exception e) {
     ;
 }
 Assert.assertTrue(flag);

 for (int i=0; i<10; i++) {
     Assert.assertEquals(new Integer(i), l.get(i));
 }

 flag = false;
 try {
     l.remove(5, 4);
 } catch (IllegalArgumentException e) {
     flag = true;
 } catch (Exception e) {
     ;
 }
 Assert.assertTrue(flag);

 for (int i=0; i<10; i++) {
     Assert.assertEquals(new Integer(i), l.get(i));
 }

    }


    /**
     * Runs the test suite using the textual runner.
     */

    public static void main( String[] args ) {
 TestSuite suite = new TestSuite();
 suite.addTestSuite( TestAll.class );
 junit.textui.TestRunner.run( suite );
    }

}

以下是我得到的错误：

5 个测试失败：TestAll testRemoveStart testRemoveMiddle testRemoveLast testRemoveOne testExceptions 文件：C:\Users\Mikros0ft\Google Drive\Semester 2\ITI1121\Assignment 4\3\TestAll.java [行：30] 失败：junit.framework.AssertionFailedError：预期： <5> 但是是：<4> 文件：C:\Users\Mikros0ft\Google Drive\Semester 2\ITI1121\Assignment 4\3\TestAll.java [行：56] 失败：junit.framework.AssertionFailedError：预期：< 5> 但是是：<10> 文件：C:\Users\Mikros0ft\Google Drive\Semester 2\ITI1121\Assignment 4\3\TestAll.java [行：86] 失败：junit.framework.AssertionFailedError：预期：<5 > 但是是：<14> 文件：C:\Users\Mikros0ft\Google Drive\Semester 2\ITI1121\Assignment 4\3\TestAll.java [行：112] 失败：junit.framework.AssertionFailedError：预期：<1>但是是：<10> 文件：C：\Users\Mikros0ft\Google Drive\Semester 2\ITI1121\Assignment 4\3\TestAll.java [行：146] 失败：junit.framework.AssertionFailedError: null

4

2 回答 2

0

假设，from并且to都包含，替换这个

Elem<E> right = left.next.next;

经过

Elem<E> right = left.next;
for (int i = 0; i <= to - from; i++)
    right = right.next

size也发生变化。

size -= to - from + 1

其他一切都保持不变。

于 2013-04-09T20:50:41.373 回答
0

由于节点主要由其链接（下一个和上一个）定义，因此删除一组节点与仅删除一个节点大致相同。你有一个链 -1-2-3-4-5- 并且你删除了一些链接：-1 2-3-4 5-。

public LinkedList<Elem<E>> remove(int from, int to) 
{
    Elem<E> left = head;      
    for (int i=0; i < from; i++) 
    {
        left = left.next;

    }
    Elem<E> right = left;
    for(int i = 0; i< to - from; i++){
      right = right.next;
    }
    // removing the elements from the list;
    left.next = right;
    right.previous = left;
    size -= ((to - from)+1);

    //left to right are still linked, so just shove them into
    //a new linkedlist and return.
    LinkedList<E> ret = new LinkedList<E>();
    ret.head = left;
    ret.tail = right;
    return ret;
}
于 2013-04-09T20:53:31.737 回答