Learning Lua Step-By-Step (Part 10)

Post Stastics

• This post has 888 words.
• Estimated read time is 4.23 minute(s).

---

Advanced Data-Structures: Linked Lists

In this installment, we’ll delve into advanced data structures in Lua, including linked lists, trees, and graphs. These data structures are essential for solving complex problems and implementing efficient algorithms in various applications.

Linked Lists in Lua

Linked lists are a fundamental data structure consisting of nodes connected in a linear sequence. Each node contains data and a reference to the next node in the sequence. We’ll start by implementing a single linked list in Lua.

classDiagram
    class Node {
        +data
        +next
    }
    class LinkedList {
        +head
        +add(data)
        +search(target)
        +delete(target)
    }
    LinkedList --> Node

Single Linked List Implementation

-- Define a node structure
local Node = {}
Node.__index = Node

function Node.new(data)
    local self = setmetatable({}, Node)
    self.data = data
    self.next = nil
    return self
end

-- Define a linked list structure
local LinkedList = {}
LinkedList.__index = LinkedList

function LinkedList.new()
    local self = setmetatable({}, LinkedList)
    self.head = nil
    return self
end

function LinkedList:add(data)
    local newNode = Node.new(data)
    if not self.head then
        self.head = newNode
    else
        local current = self.head
        while current.next do
            current = current.next
        end
        current.next = newNode
    end
end

function LinkedList:search(target)
    local current = self.head
    while current do
        if current.data == target then
            return true
        end
        current = current.next
    end
    return false
end

function LinkedList:delete(target)
    if not self.head then
        return
    end
    if self.head.data == target then
        self.head = self.head.next
        return
    end
    local current = self.head
    while current.next do
        if current.next.data == target then
            current.next = current.next.next
            return
        end
        current = current.next
    end
end

-- Usage
local list = LinkedList.new()
list:add(1)
list:add(2)
list:add(3)

print(list:search(2)) -- Output: true
print(list:search(5)) -- Output: false

list:delete(2)

Double Linked List

classDiagram
    class DoubleNode {
        +data
        +prev
        +next
    }
    class DoubleLinkedList {
        +head
        +tail
        +add(data)
        +search(target)
    }
    DoubleLinkedList --> DoubleNode

Double Linked List Implementation

-- Define a double linked list node structure
local DoubleNode = {}
DoubleNode.__index = DoubleNode

function DoubleNode.new(data)
    local self = setmetatable({}, DoubleNode)
    self.data = data
    self.prev = nil
    self.next = nil
    return self
end

-- Define a double linked list structure
local DoubleLinkedList = {}
DoubleLinkedList.__index = DoubleLinkedList

function DoubleLinkedList.new()
    local self = setmetatable({}, DoubleLinkedList)
    self.head = nil
    self.tail = nil
    return self
end

function DoubleLinkedList:add(data)
    local newNode = DoubleNode.new(data)
    if not self.head then
        self.head = newNode
        self.tail = newNode
    else
        newNode.prev = self.tail
        self.tail.next = newNode
        self.tail = newNode
    end
end

-- Usage
local doubleList = DoubleLinkedList.new()
doubleList:add(1)
doubleList:add(2)
doubleList:add(3)

Searching in a Double Linked List

function DoubleLinkedList:search(target)
    local current = self.head
    while current do
        if current.data == target then
            return true
        end
        current = current.next
    end
    return false
end

-- Usage
print(doubleList:search(2)) -- Output: true
print(doubleList:search(5)) -- Output: false

ToDo List

Let’s consider a simple real-world example of using a linked list: managing a to-do list. In this scenario, each item on the to-do list can be represented as a node in the linked list, where each node contains the task description and possibly other relevant information such as the due date.

Here’s a demo code showcasing how we can implement a to-do list using a linked list in Lua:

-- Define a node structure for the to-do list
local TodoNode = {}
TodoNode.__index = TodoNode

function TodoNode.new(task, dueDate)
    local self = setmetatable({}, TodoNode)
    self.task = task
    self.dueDate = dueDate
    self.next = nil
    return self
end

-- Define a linked list structure for the to-do list
local TodoList = {}
TodoList.__index = TodoList

function TodoList.new()
    local self = setmetatable({}, TodoList)
    self.head = nil
    return self
end

function TodoList:addTask(task, dueDate)
    local newNode = TodoNode.new(task, dueDate)
    if not self.head then
        self.head = newNode
    else
        local current = self.head
        while current.next do
            current = current.next
        end
        current.next = newNode
    end
end

function TodoList:displayTasks()
    local current = self.head
    print("To-Do List:")
    while current do
        print("- Task:", current.task)
        if current.dueDate then
            print("  Due Date:", current.dueDate)
        end
        current = current.next
    end
end

-- Usage
local todoList = TodoList.new()
todoList:addTask("Finish report for meeting", "2024-05-01")
todoList:addTask("Buy groceries")
todoList:addTask("Call mom")

todoList:displayTasks()

In this example, we create a TodoNode structure to represent each task on the to-do list, containing attributes for the task description (task) and the due date (dueDate). We then define a TodoList structure to manage the linked list of tasks. The addTask function is used to add tasks to the list, and the displayTasks function is used to display all tasks in the list.

This demonstrates a practical application of linked lists in managing real-world data such as a to-do list.

Conclusion

In this part, we explored single and double-linked lists in Lua and learned how to implement basic operations such as insertion, searching, and deletion. In the next part, we’ll continue our journey through advanced data structures by covering trees and graphs.

Exercises

1. Linked List Operations:

• Implement a method to reverse a linked list in Lua.
• Write a function to find the middle element of a linked list.

1. Search in Linked Lists:

• Extend the search method to support searching in double-linked lists.

Resources

• Linked List – Wikipedia
• Depth-First Search – Wikipedia
• Breadth-First Search – Wikipedia

Stay tuned for the next part where we’ll explore trees and graphs in Lua.