const std = @import("std");
fn LinkedList(comptime T: type) type {
return struct {
const Self = @This();
const Node = struct {
value: T,
next: ?*Node,
};
allocator: std.mem.Allocator,
head: ?*Node,
len: usize,
fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.head = null,
.len = 0,
};
}
fn deinit(self: *Self) void {
var current = self.head;
while (current) |node| {
current = node.next;
self.allocator.destroy(node);
}
}
fn append(self: *Self, value: T) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{ .value = value, .next = null };
if (self.head == null) {
self.head = new_node;
} else {
var current = self.head;
while (current.?.next) |next| {
current = next;
}
current.?.next = new_node;
}
self.len += 1;
}
fn prepend(self: *Self, value: T) !void {
const new_node = try self.allocator.create(Node);
new_node.* = .{ .value = value, .next = self.head };
self.head = new_node;
self.len += 1;
}
fn find(self: *Self, value: T) ?*Node {
var current = self.head;
while (current) |node| : (current = node.next) {
if (node.value == value) return node;
}
return null;
}
fn print(self: *Self) void {
var current = self.head;
std.debug.print("List: ", .{});
while (current) |node| : (current = node.next) {
std.debug.print("{} -> ", .{node.value});
}
std.debug.print("null\n", .{});
}
};
}
test "linked list" {
const allocator = std.testing.allocator;
var list = LinkedList(i32).init(allocator);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.prepend(0);
list.print();
}
fn Stack(comptime T: type) type {
return struct {
const Self = @This();
items: std.ArrayList(T),
fn init(allocator: std.mem.Allocator) Self {
return .{ .items = std.ArrayList(T).init(allocator) };
}
fn deinit(self: *Self) void {
self.items.deinit();
}
fn push(self: *Self, item: T) !void {
try self.items.append(item);
}
fn pop(self: *Self) ?T {
if (self.items.items.len == 0) return null;
return self.items.pop();
}
fn peek(self: *Self) ?T {
if (self.items.items.len == 0) return null;
return self.items.items[self.items.items.len - 1];
}
fn isEmpty(self: *Self) bool {
return self.items.items.len == 0;
}
fn size(self: *Self) usize {
return self.items.items.len;
}
};
}
test "stack" {
const allocator = std.testing.allocator;
var stack = Stack(i32).init(allocator);
defer stack.deinit();
try stack.push(10);
try stack.push(20);
try stack.push(30);
std.debug.print("Stack peek: {}\n", .{stack.peek().?});
std.debug.print("Stack pop: {}\n", .{stack.pop().?});
std.debug.print("Stack size: {}\n", .{stack.size()});
}
fn Queue(comptime T: type) type {
return struct {
const Self = @This();
items: std.ArrayList(T),
head: usize,
fn init(allocator: std.mem.Allocator) Self {
return .{
.items = std.ArrayList(T).init(allocator),
.head = 0,
};
}
fn deinit(self: *Self) void {
self.items.deinit();
}
fn enqueue(self: *Self, item: T) !void {
try self.items.append(item);
}
fn dequeue(self: *Self) ?T {
if (self.head >= self.items.items.len) return null;
const item = self.items.items[self.head];
self.head += 1;
return item;
}
fn peek(self: *Self) ?T {
if (self.head >= self.items.items.len) return null;
return self.items.items[self.head];
}
fn isEmpty(self: *Self) bool {
return self.head >= self.items.items.len;
}
fn size(self: *Self) usize {
return self.items.items.len - self.head;
}
};
}
test "queue" {
const allocator = std.testing.allocator;
var queue = Queue(i32).init(allocator);
defer queue.deinit();
try queue.enqueue(1);
try queue.enqueue(2);
try queue.enqueue(3);
std.debug.print("Queue dequeue: {}\n", .{queue.dequeue().?});
std.debug.print("Queue size: {}\n", .{queue.size()});
}
const BinaryTree = struct {
const Self = @This();
allocator: std.mem.Allocator,
root: ?*Node,
const Node = struct {
value: i32,
left: ?*Node,
right: ?*Node,
};
fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.root = null,
};
}
fn deinit(self: *Self) void {
self.destroyNode(self.root);
}
fn destroyNode(self: *Self, maybe_node: ?*Node) void {
const node = maybe_node orelse return;
self.destroyNode(node.left);
self.destroyNode(node.right);
self.allocator.destroy(node);
}
fn insert(self: *Self, value: i32) !void {
self.root = try self.insertNode(self.root, value);
}
fn insertNode(self: *Self, maybe_node: ?*Node, value: i32) !?*Node {
if (maybe_node == null) {
const node = try self.allocator.create(Node);
node.* = .{ .value = value, .left = null, .right = null };
return node;
}
const node = maybe_node.?;
if (value < node.value) {
node.left = try self.insertNode(node.left, value);
} else {
node.right = try self.insertNode(node.right, value);
}
return node;
}
fn inorder(self: *Self) void {
self.inorderNode(self.root);
std.debug.print("\n", .{});
}
fn inorderNode(self: *Self, maybe_node: ?*Node) void {
const node = maybe_node orelse return;
self.inorderNode(node.left);
std.debug.print("{} ", .{node.value});
self.inorderNode(node.right);
}
fn search(self: *Self, value: i32) bool {
return self.searchNode(self.root, value);
}
fn searchNode(self: *Self, maybe_node: ?*Node, value: i32) bool {
const node = maybe_node orelse return false;
if (value == node.value) return true;
if (value < node.value) return self.searchNode(node.left, value);
return self.searchNode(node.right, value);
}
};
test "binary tree" {
const allocator = std.testing.allocator;
var tree = BinaryTree.init(allocator);
defer tree.deinit();
try tree.insert(50);
try tree.insert(30);
try tree.insert(70);
try tree.insert(20);
try tree.insert(40);
std.debug.print("Inorder traversal: ", .{});
tree.inorder();
std.debug.print("Search 40: {}\n", .{tree.search(40)});
std.debug.print("Search 100: {}\n", .{tree.search(100)});
}
fn DynamicArray(comptime T: type) type {
return struct {
const Self = @This();
allocator: std.mem.Allocator,
items: []T,
capacity: usize,
len: usize,
fn init(allocator: std.mem.Allocator) Self {
return .{
.allocator = allocator,
.items = &[_]T{},
.capacity = 0,
.len = 0,
};
}
fn deinit(self: *Self) void {
self.allocator.free(self.items);
}
fn append(self: *Self, item: T) !void {
if (self.len >= self.capacity) {
const new_capacity = if (self.capacity == 0) 8 else self.capacity * 2;
const new_items = try self.allocator.realloc(self.items, new_capacity);
self.items = new_items;
self.capacity = new_capacity;
}
self.items[self.len] = item;
self.len += 1;
}
fn get(self: *Self, index: usize) ?T {
if (index >= self.len) return null;
return self.items[index];
}
fn size(self: *Self) usize {
return self.len;
}
};
}
test "dynamic array" {
const allocator = std.testing.allocator;
var arr = DynamicArray(i32).init(allocator);
defer arr.deinit();
for (0..10) |i| {
try arr.append(@intCast(i));
}
std.debug.print("Array size: {}\n", .{arr.size()});
std.debug.print("Array[5]: {}\n", .{arr.get(5).?});
}
pub fn main() !void {
std.debug.print("Data structures examples\n", .{});
}