Java circular linked list without a head or tail?

0
votes

My book only mentions circular linked lists on one page and says that you can create them by making the head and tail of single or double linked lists linked to each other. But then the programming exercise says:

"A circular-linked list has no need of a head or tail. Instead, you need only a reference to a current node, which is the nextNode returned by the Iterator. Implement such a class. For a nonempty list, the Iterator.hasNext method will always return true."

I'm not really sure how I should approach this.

2
javaiteratorcircular-list
Specifically, what are you stuck on? - ylun.ca
I understand how to make a single linked list, but I don't understand how I could make it a circular linked list without any reference to a head or tail node. This is the only mention of circular linked lists in the entire book. - smitty werbenjagermanjensen
Well if you think of a circle, at what point is the "start" and "end" of a circle? - MxLDevs

2 Answers

2
votes

The exercise is worded in a way not to limit you in your implementation decision: rather than prescribing a particular solution, it lets you implement the list in a way that you find most convenient.

You do need to have a pointer into the list, but since the list is circular, it does not need to point anywhere in particular. Since it does not point to a head or a tail, you can call it next, and keep it pointing to any element that you find convenient:

  • After insertion, next could point to the element that you have just inserted
  • After deletion, next could point to the element after or before the deleted one
  • After a search, next could remain unchanged
0
votes

In order to convert your single or double linked list to circular, u l link the head and tail.. now the list structure is circular.. so it is not necessary to have a head / tail. Bcoz all nodes are interlinked and so no pointer has next node as null.

And circular list is of 2 types. Single circular list - has hasNext() method nly Double circular list.- has hasNext() and hasPrev()

The above mentioned methods are the ways of traversing in the circular linked list.