Acyclic List

An acyclic list is a list data structure in which nodes are connected linearly without any cycles. This means it is not possible to start at a node and follow a sequence of references to come back to the same node.

Acyclic lists only allow traversal in one direction from head to tail. This also implies that no node in the list can reference a node that came before it.

Common examples of acyclic lists include linked lists and trees. Graphs that are directed and without cycles are also acyclic.

Acyclic structures allow simpler algorithms and modeling of hierarchies because cycles do not need to be handled.

Solution

Here is an implementation of an acyclic singly linked list:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Node {
  int data;
  Node next;
}

class AcyclicList {
  Node head;
  
  // inserts node at head
  public void insert(int data) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = head;
    head = newNode;
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
struct Node {
  int data;
  Node* next;
};

class AcyclicList {
public:
  Node* head;

  // insert node at head
  void insert(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    head = newNode;
  }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Node:
  def __init__(self, data): 
    self.data = data
    self.next = None
    
class AcyclicList:
  def __init__(self):
    self.head = None
  
  # insert node at head  
  def insert(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

The next pointers always move forward, preventing cycles. This gives an acyclic list.

Acyclic structures simplify algorithms by avoiding cycle handling.

Description: Acyclic List

An Acyclic List is a data structure similar to a linked list but without any cycles, meaning it doesn’t contain any node that is revisited. Acyclic lists always have a starting node (head) and end at a null or a terminal node. They are simpler to handle compared to cyclic or doubly-linked lists, and they offer advantages in scenarios where you don’t need to revisit nodes.

Solution

We’ll demonstrate how to implement an acyclic list and also how to check for cycles in a given list. We’ll do this using Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class AcyclicList {
    public static boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        System.out.println("Has cycle: " + hasCycle(head));
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while(fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            return true;
        }
    }
    return false;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    cout << "Has cycle: " << (hasCycle(head) ? "Yes" : "No");
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def hasCycle(head):
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

print("Has cycle:", hasCycle(head))

Key Takeaways

Acyclic lists are lists without cycles; they have a clear start and end point.
Checking for cycles involves using two pointers moving at different speeds through the list. If a cycle exists, they will eventually meet.
The core logic for checking cycles is consistent across Java, C++, and Python. The syntax varies according to the language.