Circular linked list and access to previous/next from inside of node

Question

I need circular list of objects. And each one should know which is previous or next. I did this:

class Bus {

    private Bus previous;
    private Bus next;

    public Bus() {
      //anything
    }

    public void setPrevious(Bus bus) {
      this.previous = bus;
    }

    public void setNext(Bus bus) {
      this.next = bus;
    }

    private void someMethod() {
     // if (previous.xxx() && next.xxx()) {
     //   do something
     // } 
    }

}

And I created an array of Bus. After I add all buses into it, I set next and previous of each element. And I feel it's ugly:D. May you suggest me better way?

score 1 · Answer 1 · answered Jan 05 '12 at 22:52

1

Just a thought, but maybe have one class for the nodes and one for the list. In this way, you can have a constructor for the node class that handles setting its next and last references. This allows the list to really only need to worry about standard list functions like Add().

Take a look at the List interface.

answered Jan 05 '12 at 22:52

user489041

27,916
55
135
204

I know, but I need an access to previous and next from node, not list's controller... – ciembor Jan 05 '12 at 22:58

score 1 · Answer 2 · edited May 23 '17 at 11:55

1

A linked list don't need an array. To create the list you need to use next and previous methods to connect your objects and connect the last with the first (to do circular). And example of use (using your implementation):

Bus one = new Bus();
Bus two = new Bus();
Bus three = new Bus();

one.setPrevious(three);
one.setNext(two);

two.setPrevious(one);
two.setNext(three);

three.setPrevious(two);
three.setNext(one);

That more or less the idea of a Linked List circular. I recommend to see that another question to understand a Linked List. To do it circular is easy.

edited May 23 '17 at 11:55

Community

1
1

answered Jan 05 '12 at 22:53

jenaiz

547
2
15

But I need N nodes and I'm creating them one by one. In circular list I don't know where to put new object. It must be between last and first. – ciembor Jan 05 '12 at 23:00
Yes, a new object should be between the last and the first. You need to change the implementation of Bus to do that automatically. – jenaiz Jan 06 '12 at 14:30

score 1 · Accepted Answer · answered Jan 05 '12 at 23:24

If you adjust your setNext and setPrevious methods to not only update their instance but also the instance that is set as next and as previous you want have to depend on an external mechanism.

So let's say you have initially created Bus A and B. When you call A.setNext( B ), it should also update the previous node of B, without having to call B.setPrevious( A ). Similar as when you add something to a LinkedList in Java, you do not have to manually set the link between the last object and the object you just added. Something like

public void setPrevious(Bus bus) {
  this.previous = bus;
  if ( bus.next != this ){
    bus.next = this;
  }
}

Of course then you still have to consider the scenario where the bus is already contained in another List that you have to update that List as well.

Therefore, the suggestion to separate the nodes from the actual bus instances as suggested in one of the other responses is a better idea. This allows you to add busses to multiple lists, and makes it probably easier to write your circular list (or just use an available implementation for the list). This is also better OO design as you can reuse the list you wrote.

score 0 · Answer 4 · answered Jan 05 '12 at 22:54

0

Why do you need an array? You already have the references in each object.

answered Jan 05 '12 at 22:54

Fortunato

1,360
10
9

Circular linked list and access to previous/next from inside of node

4 Answers4