Circular Linked List

Chenglei Si
Sep 8, 2018 · 2 min read

It is similar to a singly linked list, except that the tail node links to the head node. Please take note that in my implementation, the ‘head’ is actually the tail, and ‘head->next’ is actually the head. This allows us to quickly get the tail node without traversing to the end (of course you can use bidirectional links to avoid the trouble as well). You can simply replace all ‘head’ with ‘tail’ if you feel uncomfortable with it:)

//Node definition is the same as singly linked list
//use circular linked list to solve josephus problem
template <typename Type> class LinkedList {
private:
Node<Type> *head;
public:
LinkedList() {
head = NULL;
}
~LinkedList() {
if(head==NULL){
return;
}
//head is the tail node, head->next is the head node
Node<Type> *current_node = head->next;
//detach to singly linked list
head->next=NULL;
while (current_node != NULL) {
Node<Type> *delete_node = current_node;
current_node = current_node->next;
delete delete_node;
}
}
bool insert(Node<Type> *node, int index) {
if (head == NULL) {
if (index != 0) {
return false;
}
head = node;
//link to itself when only one node
head->next=head;
return true;
}
if (index == 0) {
node->next = head->next;
head->next = node;
return true;
}
Node<Type> *current_node = head->next;
int count = 0;
while (current_node != head && count < index - 1) {
current_node = current_node->next;
count++;
}
if (count == index - 1) {
node->next = current_node->next;
current_node->next = node;
//update tail
if(node==head->next){
head=node;
}
return true;
}
return false;
}
//remove and output the m-indexed numbers
void output_josephus(int m){
Node<Type> *current_node=head;
//head node may be deleted
//set it to NULL to avoid dangling pointer
head=NULL;
//loop until only one node left
while(current_node->next!=current_node){
//count m-1: node before m-node
for(int i=1;i<m;i++){
current_node=current_node->next;
}
cout<<current_node->next->data<<" ";
Node<Type> *delete_node=current_node->next;
current_node->next=current_node->next->next;
delete delete_node;
}
//output last node
cout<<current_node->data<<endl;
delete current_node;
}
};

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade