Link list circular (loop)

Didalam kode ini berisi
 1. menambahkan node
 2. fungsi pengembalian pada list
 3. membuat list circular (loop)
 4. rekursif 

#include <iostream>
using namespace std;

struct Node
{
 int data;
 Node * next;
};

Node *root = 0;

void addNode(int n)
{
 if(root==0) {
  root = new Node;
  root->data = n;
  root->next = 0;
  return;
 }
 Node *cur = root;
 while(cur) {
  if(cur->next == 0) {
   Node *ptr = new Node;
   ptr -> data = n;
   ptr -> next = 0;
   cur -> next = ptr;
   return;
  }
  cur = cur->next;
 }
}

void makeCircular()
{
 if(!root || !root->next) return;
 Node *cur = root;
 while(cur) {
  if(cur->next == 0) {
   cur->next = root;
   return;
  }
  cur = cur->next;
 }
}

int sizeOfList()
{
 Node *cur = root;
 int size = 0;
 while(cur) {
  size++;
  if(cur->next == 0) {
   return size; 
  }
  cur = cur->next; 
 }
 return size;
}

bool detectCircular() 
{
 // Assuming the list may not be circular

 if(!root || !root->next) return false;
 Node *ptr1 = root;
 Node *ptr2 = root;

 while(ptr1 && ptr2) {
  ptr1 = ptr1->next;
  ptr2 = ptr2->next;
  if(ptr2) {
         ptr2 = ptr2->next;
         if(!ptr2) return false;
  }
  else {
   return false;
  }
  cout << ptr1->data << "," << ptr2->data << endl;
  if(ptr1==ptr2) {
   return true;
  }
 }
 return false;
}

void printRecursive(Node *ptr)
{
 if(!ptr) {
  cout << endl;
  return;
 }
 cout << ptr->data << " ";
 printRecursive(ptr->next);
}

int main(int argc, char **argv)
{
 addNode(10);addNode(20);addNode(30);addNode(40);addNode(50);
 addNode(60);addNode(70);addNode(80);addNode(90);addNode(100);
 
 printRecursive(root);

 cout << "size of list = " << sizeOfList() << endl;
  
 makeCircular();

 if(detectCircular()) cout <<"Circular\n";
 else cout << "Normal\n";
  
}

Output from the run:

10 20 30 40 50 60 70 80 90 100
size of list = 10
20,30
30,50
40,70
50,90
60,10
70,30
80,50
90,70
100,90
10,10
Circular

Example 5B - Detecting Circular (Loop) Linked List (Generic Class with Template)

#include <iostream>
#include <string>

using namespace std;

template <class T>
class LinkedList
{
private:
 struct node
 {
  T data;
  node * next;
 } *head;

public:
 LinkedList();
 ~LinkedList();
 void add(T d);
 void remove(T d);
 void clear();
 void makeCircular();
 bool isCircular();
 void display(const char* s);
};

template <class T>
LinkedList<T>::LinkedList()
{
 head = NULL;
} 

template <class T>
LinkedList<T>::~LinkedList()
{
 node *p, *q;
 p = head;
 if(p == NULL) return;
 while(p) {
  q = p->next;
  delete p;
  p = q;
 }
}

template <class T>
void LinkedList<T>::add(T d)
{ 
 node *p, *q;
 if(head == NULL) {
  head = new node;
  head->data = d;
  head->next = NULL;
  return;
 } 
 p = head;
 while(p->next != NULL) 
  p = p->next;
 q = new node;
 q->data = d;
 q->next = NULL;
 p->next = q; 
}

template <class T>
void LinkedList<T>::remove(T d)
{
 node *p, *q;
 if(head == NULL) return;
 p = head;
 while(p) {
  if(p->data == d) {
   q->next = p->next;
   delete p;
   return;
  }
  q = p;
  p = p->next;
 }
}

template <class T>
void LinkedList<T>::clear()
{
 node *p, *q;
 if(head == NULL) return;
 p = head;
 while(p) {
  q = p->next;
  delete p;
  if(q != head)  {
   head = NULL;
   return;
  }
  p = q;
 }
}

template <class T>
void LinkedList<T>::makeCircular()
{
 node *p;
 if(head == NULL || head->next == NULL) return;
 p = head;
 while(p) {
  if(p->next == NULL) {
   p->next = head;
   return;
  }
  p = p->next;
 }
}

template <class T>
bool LinkedList<T>::isCircular()
{
 node *p, *pp;
 if(head == NULL || head->next == NULL) return false;
 p = head;
 pp = head;
 while(pp) {
  p = p->next;
  if(pp->next == NULL) return false;
  pp = (pp->next)->next;
  if(p == pp) return true;
 }
 return false;
}

template <class T>
void LinkedList<T>::display(const char* s)
{
 node *p;
 if(head == NULL) return;
 p = head;
 while(p) {
  if(s == "string") 
   cout << p->data << endl;
  else
   cout << p->data << ' ';
  p = p->next;
  if(p != NULL) {
   if(p == head) return;
  }
 }
 if(s == "integer") cout << endl;
}
 
int main()
{
 LinkedList<string> sList;
 sList.add("Wolfgang Amadeus Mozart");
 sList.add("Franz Peter Schubert");
 sList.add("Pyotr Ilyich Tchaikovsky");
 sList.add("Clude-Achille Debussy");
 sList.add("Camille Saint-Saens");
 sList.display("string");
 sList.clear();

 LinkedList<int> iList;
 iList.add(40);
 iList.add(50);
 iList.add(60);
 iList.add(70);
 iList.add(80);
 iList.add(90);
 iList.add(100);
 iList.add(10);
 iList.add(20);
 iList.add(30);
 iList.display("integer");

 /* link last element to the first */
 iList.makeCircular();

 if(iList.isCircular()) cout <<"This is circular list\n";
 iList.display("integer");

 iList.clear();
 cout << "\ndisplay after clear()\n";
 iList.display("integer");

 return 0;
}

Artikel Terkait