© 1999-2003, Flemming Koch Jensen
Alle rettigheder forbeholdt
Dobbelthægtede lister
Vejledende løsninger

 

 

1

Først er der service-metoden: findNode:

List.java
 
private Node findNodeByIndex( int index ) {
  int i=0;
  
  for ( Node n=first.next; n!=last; n=n.next )
    if ( i == index )
      return n;
    else
      i++;
  
  return null;
}
I modsætning til den findNode vi lavede i kapitlet, søges der her ikke efter en knude med et bestemt data-objekt, men der tælles frem til det ønskede index. Såfremt index er for stort returneres null.
get-metoden bygger i al væsentlighed på findNode:
List.java
 
public Object get( int index ) {
  Node n = findNodeByIndex( index );
  
  if ( n != null )
    return n.getData();
  else
    return null;  
}
insert-metoden er til gengæld mere interessant:
List.java
 
public boolean insert( int index, Object obj ) {
  Node before, after;
  
  if ( 0 <= index && index < size )
    after = findNodeByIndex( index );
  else if ( index == size )
    after = last;  
  else
    return false;  
  
  before = after.prev;
  
  Node n = new Node( obj, before, after );
  
  before.next = n;
  after.prev = n;
  
  size++;
  
  return true;
}
Det interessante er if-sætningen. Da det giver mening at indsætte et element på den position, der kommer efter det sidste element, er vi nød til at kunne håndtere den situation; hvor index er lig size. Her kan findNode ikke hjælpe os, da den ser den pågældende position som en fejl-position. Vi er derfor nød til at lave en if-sætning med hele tre muligheder.
Resten af implementationen er ukompliceret.
remove-metoden er igen mere almindelig, idet findNode passer bedre her:
List.java
 
public Object remove( int index ) {
  Node n = findNodeByIndex( index );
  
  if ( n != null ) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
    
    size--;
    
    return n.getData();
  } else
    return null;
}
Endelig har vi en testanvendelse:
Main.java
 
public class Main {

  public static void main( String[] argv ) {
    List list = new List();
    
    for ( int i=0; i<5; i++ )
      list.insert( 0, 3*i );
    
    System.out.println( list );
    
    System.out.println( list.get( 2 ) );
    System.out.println( list );
    
    list.remove( 2 );
    System.out.println( list );
    
    list.insert( 4, 88 );
    System.out.println( list );
  }
}
 
[List: 12 9 6 3 0]
6
[List: 12 9 6 3 0]
[List: 12 9 3 0]
[List: 12 9 3 0 88]