# Learning Lua Step-By-Step (Part 10)

This entry is part 11 of 24 in the series Learning Lua Step-By-Step

Table of Contents

#### 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

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

Series Navigation<< Learning Lua Step-By-Step (Part 9): Exploring Metatables and Operator OverloadingLearning Lua Step-By-Step: Part 12 >>