Java 通用双向链表交换
Java Generic Doubly Linked List Swap
http://users.cis.fiu.edu/~weiss/dsaajava3/code/MyLinkedList.java
上面的 link 显示了我想要修改的代码,以便从双重 linked 列表中获得交换方法。由于在此处粘贴的 300 行代码可读性不佳,因此提前使用 URL 表示歉意。
对于输出,我只想有一个列表 输出,例如 :
[ 28 27 **21** 25 24 23 22 **26** 20 0 1 2 3 4 5 6 7 8 ] //(2, 7) swap
下面是我的尝试(部分代码改为include/modify原文):
兑换方式:
public AnyType swap( int idx, int idx2)
{
return swap( getNode( idx ), getNode ( idx2 ) );
}
private AnyType swap( Node<AnyType> p, Node<AnyType> p2)
{
Node<AnyType> temp = p; //realize it doesn't work due to linking
p = p2;
p2 = temp;
return p.data;
}
主要内容:
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size( ) - 1 );
lst.swap(2, 7);
System.out.println("swap: " + lst);
}
}
输出
swap: [ 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
21
我意识到我的解决方法不是使用 linked 列表。我一直在分析我要修改的代码;但是我很难用指针和双重 linked 列表来理解编码部分(不是概念)。请解释我应该如何解决问题。谢谢。
编辑
/* Swaps idx and idx2 nodes
* @param idx the index of the object
* @param idx2 the index of the object
*/
public void swap( int idx, int idx2)
{
swap( getNode( idx ), getNode ( idx2 ) );
if( idx < 0 || idx >= size( ) || idx2 < 0 || idx2 >= size( )){
throw new IndexOutOfBoundsException( "swap first index: " + idx + ", second index: " + idx2 );
}
}
/**
* Swaps node and data at p and p2
* @param p the index of the object
* @param p2 the index of the object
*/
public void swap( Node<AnyType> p, Node<AnyType> p2)
{
Node<AnyType> temp = p;
p = p2;
p2 = temp;
temp = p.next.prev;
p.next.prev = p2.next.prev;
p2.next.prev = temp;
AnyType dataTemp = p.data;
p.data = p2. data;
p2.data = dataTemp;
}
输出
[ 29 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 9 ]
swap: [ 29 28 22 26 25 24 23 27 21 20 0 1 2 3 4 5 6 7 8 9 ]
它正在运行。我做对了吗?但是我得到编译错误。我认为它与具有 warning: exporting non-public type through public API
的 public void swap( Node<AnyType> p, Node<AnyType> p2)
方法有关。我可以在这里做什么来修复它?
假设您的输入是:
[ 1 2 3 4 5 6 7 8 9 ]
并且您想交换 3 和 7:
[ 1 2 >7< 4 5 6 >3< 8 9 ]
这意味着您需要更新所有这些值:
2.next = 7
7.prev = 2
7.next = 4
4.prev = 7
6.next = 3
3.prev = 6
3.next = 8
8.prev = 3
总共8次赋值,不包括对临时变量的赋值。
如果您想交换 5 和 6 怎么办:
[ 1 2 3 4 >6< >5< 7 8 9 ]
4.next = 6
6.prev = 4
6.next = 5
5.prev = 6
5.next = 7
7.prev = 5
嗯...那只有 6 个作业。
如果你想交换第一个和最后一个元素怎么办:
[ >9< 2 3 4 5 6 7 8 >1< ]
你没有分享这部分,但我假设你有头尾参考,所以:
head = 9
9.prev = null
9.next = 2
2.prev = 9
8.next = 1
1.prev = 8
1.next = null
tail = 1
哇哦,不一样了。
现在您只需编写所有这些代码,注意处理所有组合。
http://users.cis.fiu.edu/~weiss/dsaajava3/code/MyLinkedList.java
上面的 link 显示了我想要修改的代码,以便从双重 linked 列表中获得交换方法。由于在此处粘贴的 300 行代码可读性不佳,因此提前使用 URL 表示歉意。
对于输出,我只想有一个列表 输出,例如 :
[ 28 27 **21** 25 24 23 22 **26** 20 0 1 2 3 4 5 6 7 8 ] //(2, 7) swap
下面是我的尝试(部分代码改为include/modify原文):
兑换方式:
public AnyType swap( int idx, int idx2)
{
return swap( getNode( idx ), getNode ( idx2 ) );
}
private AnyType swap( Node<AnyType> p, Node<AnyType> p2)
{
Node<AnyType> temp = p; //realize it doesn't work due to linking
p = p2;
p2 = temp;
return p.data;
}
主要内容:
class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size( ) - 1 );
lst.swap(2, 7);
System.out.println("swap: " + lst);
}
}
输出
swap: [ 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
21
我意识到我的解决方法不是使用 linked 列表。我一直在分析我要修改的代码;但是我很难用指针和双重 linked 列表来理解编码部分(不是概念)。请解释我应该如何解决问题。谢谢。
编辑
/* Swaps idx and idx2 nodes
* @param idx the index of the object
* @param idx2 the index of the object
*/
public void swap( int idx, int idx2)
{
swap( getNode( idx ), getNode ( idx2 ) );
if( idx < 0 || idx >= size( ) || idx2 < 0 || idx2 >= size( )){
throw new IndexOutOfBoundsException( "swap first index: " + idx + ", second index: " + idx2 );
}
}
/**
* Swaps node and data at p and p2
* @param p the index of the object
* @param p2 the index of the object
*/
public void swap( Node<AnyType> p, Node<AnyType> p2)
{
Node<AnyType> temp = p;
p = p2;
p2 = temp;
temp = p.next.prev;
p.next.prev = p2.next.prev;
p2.next.prev = temp;
AnyType dataTemp = p.data;
p.data = p2. data;
p2.data = dataTemp;
}
输出
[ 29 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 9 ]
swap: [ 29 28 22 26 25 24 23 27 21 20 0 1 2 3 4 5 6 7 8 9 ]
它正在运行。我做对了吗?但是我得到编译错误。我认为它与具有 warning: exporting non-public type through public API
的 public void swap( Node<AnyType> p, Node<AnyType> p2)
方法有关。我可以在这里做什么来修复它?
假设您的输入是:
[ 1 2 3 4 5 6 7 8 9 ]
并且您想交换 3 和 7:
[ 1 2 >7< 4 5 6 >3< 8 9 ]
这意味着您需要更新所有这些值:
2.next = 7
7.prev = 2
7.next = 4
4.prev = 7
6.next = 3
3.prev = 6
3.next = 8
8.prev = 3
总共8次赋值,不包括对临时变量的赋值。
如果您想交换 5 和 6 怎么办:
[ 1 2 3 4 >6< >5< 7 8 9 ]
4.next = 6
6.prev = 4
6.next = 5
5.prev = 6
5.next = 7
7.prev = 5
嗯...那只有 6 个作业。
如果你想交换第一个和最后一个元素怎么办:
[ >9< 2 3 4 5 6 7 8 >1< ]
你没有分享这部分,但我假设你有头尾参考,所以:
head = 9
9.prev = null
9.next = 2
2.prev = 9
8.next = 1
1.prev = 8
1.next = null
tail = 1
哇哦,不一样了。
现在您只需编写所有这些代码,注意处理所有组合。