java linkedlist with multiple connections

[isamuhunter]

Hello everyone...I'm trying to create a journey planner for an underground system...but the first thing Is to create the skeleton of the underground system... my problem is I don't know how to add more links to a single node when the station has an intersection with other lines...

public class LinkedList {

    public LinkedList( ) {
        header = new ListNode( null );
    }

    public boolean isEmpty( ) {
        return header.next == null;
    }

    public void makeEmpty( ) {
        header.next = null;
    }
    public LinkedListIterator zeroth( ) {
        return new LinkedListIterator( header );
    }

    public LinkedListIterator first( ) {
        return new LinkedListIterator( header.next );
    }
    public void insert( Object x, LinkedListIterator p ) {
        if( p != null && p.current != null )
            p.current.next = new ListNode( x, p.current.next );
    }    
    public LinkedListIterator find( Object x ) {
        ListNode itr = header.next;
        while( itr != null && !itr.element.equals( x ) )
            itr = itr.next;
        return new LinkedListIterator( itr );
    }
    public LinkedListIterator findPrevious( Object x ) {
        ListNode itr = header;
        while( itr.next != null && !itr.next.element.equals( x ) )
            itr = itr.next;
        return new LinkedListIterator( itr );
    }
    public static void printList( LinkedList theList ) {
        if( theList.isEmpty( ) )
            System.out.print( "Empty list" );
        else {
            LinkedListIterator itr = theList.first( );
            for( ; itr.isValid( ); itr.advance( ) )
                System.out.print( itr.retrieve( ) + ", " );
        }
        System.out.println( );
    }
    private ListNode header;
    public static int listSize( LinkedList theList ) {
        LinkedListIterator itr;
        int size = 0;
        for( itr = theList.first(); itr.isValid(); itr.advance() )
            size++;
        return size;
    }
    public static void main( String [ ] args ) {
            String stationListA[]= {"Dejvicka","Hradkanska","Malostranska"
            ,"Staromestaska","Mustek","Muzeum","Namesti Miru","Jiriho Z Podebrad"
            , "Flora","Zelivskeho", "Strasnicka","Skalka","Depo Hostivar"};
            String stationListB[] = {"Zličín","Stodůlky","Luka","Lužiny","Hůrka"
            ,"Nové Butovice","Jinonice","Radlická "
            ,"Smíchovské Nádraží","Anděl"," Karlovo náměstí "," Národní Třída "
            ," Mustek","NR","Florenc","Krizikova","Invalidovna"
            ,"CM","Vysokanska","Kolbenova","Hloubetin","Rajska Zahrada","Cerny Most"};
            String stationListC[]={"Ladvi","Kobylisy","Nadrazi Holesovice"
            ,"Vltavska","Florenc", "Hlavni Nadrazi","Muzeum","I P Pavlova"
            , "Vysehrad","Prazkeho Povstani","Pankrac","Budejovicka","Kacerov"
            ,"Roztyly","Chodov","Opatov", "Haje"};
        LinkedList         lineA = new LinkedList( );
        LinkedListIterator theItr;
        int i;
        theItr = lineA.zeroth( );
        printList( lineA );
        for( i = 0; i < stationListA.length; i++ ) {
            lineA.insert( new String ( stationListA[i] ), theItr );
            //printList( lineA );
            theItr.advance( );
        }
        LinkedList lineB=new LinkedList();
        theItr=lineB.zeroth();
        printList(lineB);
        for(i=0;i<stationListB.length;i++){
            lineB.insert(new String(stationListB[i]), theItr);
            theItr.advance();
        }
        LinkedList lineC=new LinkedList();
        theItr=lineC.zeroth();
        printList(lineC);
        for(i=0;i<stationListC.length;i++){
            lineB.insert(new String(stationListC[i]), theItr);
            theItr.advance();
        }
	}
}
public class LinkedListIterator {
  
    LinkedListIterator( ListNode theNode ) {
        current = theNode;
    }
 
    public boolean isValid( ) {
        return current != null;
    }
     public Object retrieve( ) {
        return isValid( ) ? current.element : null;
    }
     public void advance( ) {
        if( isValid( ) )
            current = current.next;
    }
    ListNode current;
}

class ListNode {
    public ListNode( Object theElement ) {
        this( theElement, null );
    }
    public ListNode( Object theElement, ListNode n ) {
        element = theElement;
        next    = n;
    }
    public Object   element;
    public ListNode next;
}

thanks

[Taywin]

Not sure. Does it mean that a node could have multiple parents with multiple children OR have one parent with multiple children? Would it possibly become a circle? You could use ArrayList to store parent/children depending on your data. However, be very careful! Circle is dangerous for a linked list!

[isamuhunter]

in a point of the structure i will have a circle between 3 stations and one that is designed (I still don't know how to) I will apply Dijkstra's algorithm to find the shortest path between 2 nodes. I was researching a lot but I couldn't find a clear example (for me) how to implement that... can you give me any link or code to help me out with that?
thanks a lot

[Taywin]

From your existing code, you could make some modification.

public class LinkedList {
  ListNode header;

  public LinkedList( ) {
    header = new ListNode(null);
  }

  public boolean isEmpty( ) {
    return header.next.isEmpty();
  }

  public void makeEmpty( ) {
    header.next = new ArrayList<ListNode>();
  }
...
}

As you see that your inner data structure is changed from only 1 pointer to multiple pointer using ArrayList instead. Because of the change, you will have to modify all other methods when you deal with a node. In addition, your insert and remove will need to be more careful not to forget anything.

Just my two cents.

PS: I don't know why you would need makeEmpty()... It is somewhat dangerous in a linkedlist because you could create problems later on (discard its children without intention).

[isamuhunter]

thx a lot. I'll try to implement that. the makeEmpty method is just routine. I will never dare to implement it.

[ztini]

Presumably distances between points are not equal. Likewise, from a design perspective, I don't think you should treat them as equal. The distance from point A to point B might be different from the distance of B to C. The distance or weight of these connections could possibly be relevant later on in development.

I suggest:

public class Connection {

	private double distance;
	private Node input, output;
	
	public Connection(Node input, Node output, double distance) {
		this.input = input;
		this.output = output;
		this.distance = distance;
	}
}

import java.util.HashMap;


public class Node {

	private HashMap<String, Connection> connections =
		new HashMap<String, Connection>();
	private String name;

	public Node(String name) {
		this.name = name;
	}
	
	public String getName() {
		return name;
	}
	
	public void addNode(Node that, int distance) {
		connections.put(that.getName(), new Connection(this, that, distance));
	}
	
	public boolean hasConnection(String name) {
		return connections.keySet().contains(name);
	}
	
}

With this framework, you can easily traverse your network of nodes. You can create a method on each node to tell you the adjacent connections. This decentralizes the organization.

[isamuhunter]

thanks a lot ztini!