mirror of
https://github.com/ziglang/zig.git
synced 2024-11-14 16:13:24 +00:00
e834e95d71
This reverts commit 8b10970836.
This implementation has the following problems:
* It does not provide context to the less than function. This will be an
API break in order to fix.
* It uses recursion, causing unbounded stack memory usage - likely
depending on user input, which is extra problematic.
* Sorting linked lists is generally an inefficient operation;
encouraging it by having a standard library function for it may
lead to suboptimal software being written in Zig.
Furthermore, there is almost no benefit to providing a sort function as
a method, when a third party implementation can easily be passed a
linked list to then be sorted.
456 lines
14 KiB
Zig
456 lines
14 KiB
Zig
const std = @import("std.zig");
|
|
const debug = std.debug;
|
|
const assert = debug.assert;
|
|
const testing = std.testing;
|
|
|
|
/// A singly-linked list is headed by a single forward pointer. The elements
|
|
/// are singly-linked for minimum space and pointer manipulation overhead at
|
|
/// the expense of O(n) removal for arbitrary elements. New elements can be
|
|
/// added to the list after an existing element or at the head of the list.
|
|
/// A singly-linked list may only be traversed in the forward direction.
|
|
/// Singly-linked lists are ideal for applications with large datasets and
|
|
/// few or no removals or for implementing a LIFO queue.
|
|
pub fn SinglyLinkedList(comptime T: type) type {
|
|
return struct {
|
|
const Self = @This();
|
|
|
|
/// Node inside the linked list wrapping the actual data.
|
|
pub const Node = struct {
|
|
next: ?*Node = null,
|
|
data: T,
|
|
|
|
pub const Data = T;
|
|
|
|
/// Insert a new node after the current one.
|
|
///
|
|
/// Arguments:
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn insertAfter(node: *Node, new_node: *Node) void {
|
|
new_node.next = node.next;
|
|
node.next = new_node;
|
|
}
|
|
|
|
/// Remove a node from the list.
|
|
///
|
|
/// Arguments:
|
|
/// node: Pointer to the node to be removed.
|
|
/// Returns:
|
|
/// node removed
|
|
pub fn removeNext(node: *Node) ?*Node {
|
|
const next_node = node.next orelse return null;
|
|
node.next = next_node.next;
|
|
return next_node;
|
|
}
|
|
|
|
/// Iterate over the singly-linked list from this node, until the final node is found.
|
|
/// This operation is O(N).
|
|
pub fn findLast(node: *Node) *Node {
|
|
var it = node;
|
|
while (true) {
|
|
it = it.next orelse return it;
|
|
}
|
|
}
|
|
|
|
/// Iterate over each next node, returning the count of all nodes except the starting one.
|
|
/// This operation is O(N).
|
|
pub fn countChildren(node: *const Node) usize {
|
|
var count: usize = 0;
|
|
var it: ?*const Node = node.next;
|
|
while (it) |n| : (it = n.next) {
|
|
count += 1;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
/// Reverse the list starting from this node in-place.
|
|
/// This operation is O(N).
|
|
pub fn reverse(indirect: *?*Node) void {
|
|
if (indirect.* == null) {
|
|
return;
|
|
}
|
|
var current: *Node = indirect.*.?;
|
|
while (current.next) |next| {
|
|
current.next = next.next;
|
|
next.next = indirect.*;
|
|
indirect.* = next;
|
|
}
|
|
}
|
|
};
|
|
|
|
first: ?*Node = null,
|
|
|
|
/// Insert a new node at the head.
|
|
///
|
|
/// Arguments:
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn prepend(list: *Self, new_node: *Node) void {
|
|
new_node.next = list.first;
|
|
list.first = new_node;
|
|
}
|
|
|
|
/// Remove a node from the list.
|
|
///
|
|
/// Arguments:
|
|
/// node: Pointer to the node to be removed.
|
|
pub fn remove(list: *Self, node: *Node) void {
|
|
if (list.first == node) {
|
|
list.first = node.next;
|
|
} else {
|
|
var current_elm = list.first.?;
|
|
while (current_elm.next != node) {
|
|
current_elm = current_elm.next.?;
|
|
}
|
|
current_elm.next = node.next;
|
|
}
|
|
}
|
|
|
|
/// Remove and return the first node in the list.
|
|
///
|
|
/// Returns:
|
|
/// A pointer to the first node in the list.
|
|
pub fn popFirst(list: *Self) ?*Node {
|
|
const first = list.first orelse return null;
|
|
list.first = first.next;
|
|
return first;
|
|
}
|
|
|
|
/// Iterate over all nodes, returning the count.
|
|
/// This operation is O(N).
|
|
pub fn len(list: Self) usize {
|
|
if (list.first) |n| {
|
|
return 1 + n.countChildren();
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
};
|
|
}
|
|
|
|
test "basic SinglyLinkedList test" {
|
|
const L = SinglyLinkedList(u32);
|
|
var list = L{};
|
|
|
|
try testing.expect(list.len() == 0);
|
|
|
|
var one = L.Node{ .data = 1 };
|
|
var two = L.Node{ .data = 2 };
|
|
var three = L.Node{ .data = 3 };
|
|
var four = L.Node{ .data = 4 };
|
|
var five = L.Node{ .data = 5 };
|
|
|
|
list.prepend(&two); // {2}
|
|
two.insertAfter(&five); // {2, 5}
|
|
list.prepend(&one); // {1, 2, 5}
|
|
two.insertAfter(&three); // {1, 2, 3, 5}
|
|
three.insertAfter(&four); // {1, 2, 3, 4, 5}
|
|
|
|
try testing.expect(list.len() == 5);
|
|
|
|
// Traverse forwards.
|
|
{
|
|
var it = list.first;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.next) {
|
|
try testing.expect(node.data == index);
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
_ = list.popFirst(); // {2, 3, 4, 5}
|
|
_ = list.remove(&five); // {2, 3, 4}
|
|
_ = two.removeNext(); // {2, 4}
|
|
|
|
try testing.expect(list.first.?.data == 2);
|
|
try testing.expect(list.first.?.next.?.data == 4);
|
|
try testing.expect(list.first.?.next.?.next == null);
|
|
|
|
L.Node.reverse(&list.first);
|
|
|
|
try testing.expect(list.first.?.data == 4);
|
|
try testing.expect(list.first.?.next.?.data == 2);
|
|
try testing.expect(list.first.?.next.?.next == null);
|
|
}
|
|
|
|
/// A doubly-linked list has a pair of pointers to both the head and
|
|
/// tail of the list. List elements have pointers to both the previous
|
|
/// and next elements in the sequence. The list can be traversed both
|
|
/// forward and backward. Some operations that take linear O(n) time
|
|
/// with a singly-linked list can be done without traversal in constant
|
|
/// O(1) time with a doubly-linked list:
|
|
///
|
|
/// - Removing an element.
|
|
/// - Inserting a new element before an existing element.
|
|
/// - Pushing or popping an element from the end of the list.
|
|
pub fn DoublyLinkedList(comptime T: type) type {
|
|
return struct {
|
|
const Self = @This();
|
|
|
|
/// Node inside the linked list wrapping the actual data.
|
|
pub const Node = struct {
|
|
prev: ?*Node = null,
|
|
next: ?*Node = null,
|
|
data: T,
|
|
};
|
|
|
|
first: ?*Node = null,
|
|
last: ?*Node = null,
|
|
len: usize = 0,
|
|
|
|
/// Insert a new node after an existing one.
|
|
///
|
|
/// Arguments:
|
|
/// node: Pointer to a node in the list.
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn insertAfter(list: *Self, node: *Node, new_node: *Node) void {
|
|
new_node.prev = node;
|
|
if (node.next) |next_node| {
|
|
// Intermediate node.
|
|
new_node.next = next_node;
|
|
next_node.prev = new_node;
|
|
} else {
|
|
// Last element of the list.
|
|
new_node.next = null;
|
|
list.last = new_node;
|
|
}
|
|
node.next = new_node;
|
|
|
|
list.len += 1;
|
|
}
|
|
|
|
/// Insert a new node before an existing one.
|
|
///
|
|
/// Arguments:
|
|
/// node: Pointer to a node in the list.
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn insertBefore(list: *Self, node: *Node, new_node: *Node) void {
|
|
new_node.next = node;
|
|
if (node.prev) |prev_node| {
|
|
// Intermediate node.
|
|
new_node.prev = prev_node;
|
|
prev_node.next = new_node;
|
|
} else {
|
|
// First element of the list.
|
|
new_node.prev = null;
|
|
list.first = new_node;
|
|
}
|
|
node.prev = new_node;
|
|
|
|
list.len += 1;
|
|
}
|
|
|
|
/// Concatenate list2 onto the end of list1, removing all entries from the former.
|
|
///
|
|
/// Arguments:
|
|
/// list1: the list to concatenate onto
|
|
/// list2: the list to be concatenated
|
|
pub fn concatByMoving(list1: *Self, list2: *Self) void {
|
|
const l2_first = list2.first orelse return;
|
|
if (list1.last) |l1_last| {
|
|
l1_last.next = list2.first;
|
|
l2_first.prev = list1.last;
|
|
list1.len += list2.len;
|
|
} else {
|
|
// list1 was empty
|
|
list1.first = list2.first;
|
|
list1.len = list2.len;
|
|
}
|
|
list1.last = list2.last;
|
|
list2.first = null;
|
|
list2.last = null;
|
|
list2.len = 0;
|
|
}
|
|
|
|
/// Insert a new node at the end of the list.
|
|
///
|
|
/// Arguments:
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn append(list: *Self, new_node: *Node) void {
|
|
if (list.last) |last| {
|
|
// Insert after last.
|
|
list.insertAfter(last, new_node);
|
|
} else {
|
|
// Empty list.
|
|
list.prepend(new_node);
|
|
}
|
|
}
|
|
|
|
/// Insert a new node at the beginning of the list.
|
|
///
|
|
/// Arguments:
|
|
/// new_node: Pointer to the new node to insert.
|
|
pub fn prepend(list: *Self, new_node: *Node) void {
|
|
if (list.first) |first| {
|
|
// Insert before first.
|
|
list.insertBefore(first, new_node);
|
|
} else {
|
|
// Empty list.
|
|
list.first = new_node;
|
|
list.last = new_node;
|
|
new_node.prev = null;
|
|
new_node.next = null;
|
|
|
|
list.len = 1;
|
|
}
|
|
}
|
|
|
|
/// Remove a node from the list.
|
|
///
|
|
/// Arguments:
|
|
/// node: Pointer to the node to be removed.
|
|
pub fn remove(list: *Self, node: *Node) void {
|
|
if (node.prev) |prev_node| {
|
|
// Intermediate node.
|
|
prev_node.next = node.next;
|
|
} else {
|
|
// First element of the list.
|
|
list.first = node.next;
|
|
}
|
|
|
|
if (node.next) |next_node| {
|
|
// Intermediate node.
|
|
next_node.prev = node.prev;
|
|
} else {
|
|
// Last element of the list.
|
|
list.last = node.prev;
|
|
}
|
|
|
|
list.len -= 1;
|
|
assert(list.len == 0 or (list.first != null and list.last != null));
|
|
}
|
|
|
|
/// Remove and return the last node in the list.
|
|
///
|
|
/// Returns:
|
|
/// A pointer to the last node in the list.
|
|
pub fn pop(list: *Self) ?*Node {
|
|
const last = list.last orelse return null;
|
|
list.remove(last);
|
|
return last;
|
|
}
|
|
|
|
/// Remove and return the first node in the list.
|
|
///
|
|
/// Returns:
|
|
/// A pointer to the first node in the list.
|
|
pub fn popFirst(list: *Self) ?*Node {
|
|
const first = list.first orelse return null;
|
|
list.remove(first);
|
|
return first;
|
|
}
|
|
};
|
|
}
|
|
|
|
test "basic DoublyLinkedList test" {
|
|
const L = DoublyLinkedList(u32);
|
|
var list = L{};
|
|
|
|
var one = L.Node{ .data = 1 };
|
|
var two = L.Node{ .data = 2 };
|
|
var three = L.Node{ .data = 3 };
|
|
var four = L.Node{ .data = 4 };
|
|
var five = L.Node{ .data = 5 };
|
|
|
|
list.append(&two); // {2}
|
|
list.append(&five); // {2, 5}
|
|
list.prepend(&one); // {1, 2, 5}
|
|
list.insertBefore(&five, &four); // {1, 2, 4, 5}
|
|
list.insertAfter(&two, &three); // {1, 2, 3, 4, 5}
|
|
|
|
// Traverse forwards.
|
|
{
|
|
var it = list.first;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.next) {
|
|
try testing.expect(node.data == index);
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
// Traverse backwards.
|
|
{
|
|
var it = list.last;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.prev) {
|
|
try testing.expect(node.data == (6 - index));
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
_ = list.popFirst(); // {2, 3, 4, 5}
|
|
_ = list.pop(); // {2, 3, 4}
|
|
list.remove(&three); // {2, 4}
|
|
|
|
try testing.expect(list.first.?.data == 2);
|
|
try testing.expect(list.last.?.data == 4);
|
|
try testing.expect(list.len == 2);
|
|
}
|
|
|
|
test "DoublyLinkedList concatenation" {
|
|
const L = DoublyLinkedList(u32);
|
|
var list1 = L{};
|
|
var list2 = L{};
|
|
|
|
var one = L.Node{ .data = 1 };
|
|
var two = L.Node{ .data = 2 };
|
|
var three = L.Node{ .data = 3 };
|
|
var four = L.Node{ .data = 4 };
|
|
var five = L.Node{ .data = 5 };
|
|
|
|
list1.append(&one);
|
|
list1.append(&two);
|
|
list2.append(&three);
|
|
list2.append(&four);
|
|
list2.append(&five);
|
|
|
|
list1.concatByMoving(&list2);
|
|
|
|
try testing.expect(list1.last == &five);
|
|
try testing.expect(list1.len == 5);
|
|
try testing.expect(list2.first == null);
|
|
try testing.expect(list2.last == null);
|
|
try testing.expect(list2.len == 0);
|
|
|
|
// Traverse forwards.
|
|
{
|
|
var it = list1.first;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.next) {
|
|
try testing.expect(node.data == index);
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
// Traverse backwards.
|
|
{
|
|
var it = list1.last;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.prev) {
|
|
try testing.expect(node.data == (6 - index));
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
// Swap them back, this verifies that concatenating to an empty list works.
|
|
list2.concatByMoving(&list1);
|
|
|
|
// Traverse forwards.
|
|
{
|
|
var it = list2.first;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.next) {
|
|
try testing.expect(node.data == index);
|
|
index += 1;
|
|
}
|
|
}
|
|
|
|
// Traverse backwards.
|
|
{
|
|
var it = list2.last;
|
|
var index: u32 = 1;
|
|
while (it) |node| : (it = node.prev) {
|
|
try testing.expect(node.data == (6 - index));
|
|
index += 1;
|
|
}
|
|
}
|
|
}
|