DSA_MKU.kt

// You can run the code at - https://pl.kotl.in/_i03sJZfy

// DATA STRUCTURES - Kotlin Implementation

// 1. ARRAY

fun arrayDemo() {
    println("=== 1. ARRAY ===")

    val marks = mutableListOf(85, 90, 78, 92, 88, 76)

    println("Student marks: $marks")

    val target = 78
    val index = marks.indexOf(target)
    println("Found $target at index $index")

    marks.add(2, 95)
    println("After inserting 95 at index 2: $marks")

    val removed = marks.removeAt(3)
    println("Deleted: $removed")
    println("After deletion: $marks")
    println()
}

// 2. LINKED LIST

class Node(val data: Int, var next: Node? = null)

class LinkedList {
    var head: Node? = null
    var size = 0

    fun insertEnd(value: Int) {
        val newNode = Node(value)
        if (head == null) {
            head = newNode
        } else {
            var current = head
            while (current?.next != null) {
                current = current.next
            }
            current?.next = newNode
        }
        size++
    }

    fun insertFront(value: Int) {
        head = Node(value, next = head)
        size++
    }

    fun delete(value: Int): Boolean {
        if (head == null) {
            println("  List is empty!")
            return false
        }
        if (head?.data == value) {
            head = head?.next
            size--
            return true
        }
        var current = head
        while (current?.next != null && current.next?.data != value) {
            current = current.next
        }
        if (current?.next == null) {
            println("  $value not found")
            return false
        }
        current?.next = current?.next?.next
        size--
        return true
    }

    fun search(value: Int): Boolean {
        var current = head
        while (current != null) {
            if (current.data == value) return true
            current = current.next
        }
        return false
    }

    fun print() {
        var current = head
        val sb = StringBuilder()
        while (current != null) {
            sb.append("${current.data} -> ")
            current = current.next
        }
        sb.append("END")
        println("  $sb")
    }
}

fun linkedListDemo() {
    println("=== 2. LINKED LIST ===")

    val list = LinkedList()
    list.insertEnd(10)
    list.insertEnd(20)
    list.insertEnd(30)
    list.insertFront(5)

    print("List: ")
    list.print()

    list.delete(20)
    print("After deleting 20: ")
    list.print()

    println("  Search for 30: ${if (list.search(30)) "Found" else "Not found"}")
    println("  Search for 99: ${if (list.search(99)) "Found" else "Not found"}")
    println()
}

// 3. STACK (LIFO)

class Stack {
    private val items = mutableListOf<Int>()

    fun push(value: Int) {
        items.add(value)
    }

    fun pop(): Int {
        if (isEmpty()) {
            println("  Stack underflow!")
            return -1
        }
        return items.removeAt(items.size - 1)
    }

    fun peek(): Int {
        if (isEmpty()) {
            println("  Stack is empty!")
            return -1
        }
        return items.last()
    }

    fun isEmpty() = items.isEmpty()

    fun print() {
        println("  Stack (top to bottom): ${items.reversed()}")
    }
}

fun stackDemo() {
    println("=== 3. STACK (LIFO) ===")

    val stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    println("Pushed: 10, 20, 30")
    stack.print()

    println("  Top element: ${stack.peek()}")
    println("  Popped: ${stack.pop()}")
    stack.print()
    println()
}

// 4. QUEUE (FIFO)

class Queue {
    private val items = mutableListOf<Int>()

    fun enqueue(value: Int) {
        items.add(value)
    }

    fun dequeue(): Int {
        if (isEmpty()) {
            println("  Queue underflow!")
            return -1
        }
        return items.removeAt(0)
    }

    fun peek(): Int {
        if (isEmpty()) {
            println("  Queue is empty!")
            return -1
        }
        return items.first()
    }

    fun isEmpty() = items.isEmpty()

    fun print() {
        println("  Queue (front to rear): $items")
    }
}

fun queueDemo() {
    println("=== 4. QUEUE (FIFO) ===")

    val queue = Queue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    println("Enqueued: 10, 20, 30")
    queue.print()

    println("  Front element: ${queue.peek()}")
    println("  Dequeued: ${queue.dequeue()}")
    queue.print()
    println()
}

// 5. BINARY TREE (BST)

class TreeNode(val data: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class BinarySearchTree {
    var root: TreeNode? = null

    fun insert(value: Int) {
        root = insertNode(root, value)
    }

    private fun insertNode(node: TreeNode?, value: Int): TreeNode {
        if (node == null) return TreeNode(value)
        if (value < node.data) {
            node.left = insertNode(node.left, value)
        } else if (value > node.data) {
            node.right = insertNode(node.right, value)
        }
        return node
    }

    fun search(value: Int): Boolean {
        var current = root
        while (current != null) {
            current = when {
                value == current.data -> return true
                value < current.data -> current.left
                else -> current.right
            }
        }
        return false
    }

    fun inorder(node: TreeNode? = root) {
        if (node == null) return
        inorder(node.left)
        print("${node.data} ")
        inorder(node.right)
    }

    fun preorder(node: TreeNode? = root) {
        if (node == null) return
        print("${node.data} ")
        preorder(node.left)
        preorder(node.right)
    }

    fun postorder(node: TreeNode? = root) {
        if (node == null) return
        postorder(node.left)
        postorder(node.right)
        print("${node.data} ")
    }
}

fun treeDemo() {
    println("=== 5. BINARY TREE (BST) ===")

    val tree = BinarySearchTree()
    tree.insert(50)
    tree.insert(30)
    tree.insert(70)
    tree.insert(20)
    tree.insert(40)

    print("  Inorder (sorted):      "); tree.inorder(); println()
    print("  Preorder (root first): "); tree.preorder(); println()
    print("  Postorder (root last): "); tree.postorder(); println()

    println("  Search for 40: ${if (tree.search(40)) "Found" else "Not found"}")
    println("  Search for 99: ${if (tree.search(99)) "Found" else "Not found"}")
    println()
}


class Graph(private val vertices: Int) {
    private val matrix = Array(vertices) { IntArray(vertices) }

    fun addEdge(a: Int, b: Int) {
        matrix[a][b] = 1
        matrix[b][a] = 1
    }

    fun hasEdge(a: Int, b: Int): Boolean = matrix[a][b] == 1

    fun neighbors(vertex: Int): List<Int> {
        val result = mutableListOf<Int>()
        for (i in 0 until vertices) {
            if (matrix[vertex][i] == 1) result.add(i)
        }
        return result
    }

    fun printMatrix() {
        print("     ")
        for (i in 0 until vertices) print("$i ")
        println()
        for (i in 0 until vertices) {
            print("  $i: ")
            for (j in 0 until vertices) {
                print("${matrix[i][j]} ")
            }
            println()
        }
    }
}

fun graphDemo() {
    println("=== 6. GRAPH (Adjacency Matrix) ===")

    val graph = Graph(5)
    graph.addEdge(0, 1)
    graph.addEdge(0, 3)
    graph.addEdge(1, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 3)
    graph.addEdge(3, 4)

    println("Adjacency Matrix:")
    graph.printMatrix()

    println("  Edge between 1 and 3: ${if (graph.hasEdge(1, 3)) "YES" else "NO"}")
    println("  Edge between 0 and 4: ${if (graph.hasEdge(0, 4)) "YES" else "NO"}")
    println("  Neighbors of vertex 3: ${graph.neighbors(3)}")
    println()
}

fun main() {

    arrayDemo()
    linkedListDemo()
    stackDemo()
    queueDemo()
    treeDemo()
    graphDemo()

}