Doubly Linked List
A doubly linked list contains nodes that are linked together in both directions, allowing for more efficient operations in some scenarios. Each node in a doubly linked list contains:
data
, the value stored in the node.next
, a pointer to the next node in the list.prev
, a pointer to the previous node in the list.
The list itself maintains:
head
, the head of the list, used for traversal from the start.tail
, the tail of the list, used for traversal from the end and fast additions.len
, the length of the list, tracking the number of nodes.
Operations that can be performed on doubly linked lists include:
- Insertion at the end O(1), based on the
tail
pointer. - Insertion at arbitrary positions O(n), due to traversal requirements.
- Deletion O(n), with improved efficiency compared to singly linked lists it could easily find and remove nodes in this list without a full traversal.
const std = @import("std");
const Allocator = std.mem.Allocator;
fn DoublyLinkedList(comptime T: type) type {
return struct {
const Node = struct {
data: T,
next: ?*Node = null,
prev: ?*Node = null,
};
const Self = @This();
head: ?*Node = null,
tail: ?*Node = null,
len: usize = 0,
allocator: Allocator,
fn init(allocator: Allocator) Self {
return .{ .allocator = allocator };
}
// This function is equals to self.insertAt(self.len, value)
// But this cost O(1), while insertAt cost O(n) .
fn insertLast(self: *Self, value: T) !void {
const node = try self.allocator.create(Node);
node.* = Node{ .data = value, .prev = self.tail };
if (self.tail) |tail| {
tail.*.next = node;
} else {
self.head = node;
}
self.tail = node;
self.len += 1;
}
fn insertAt(self: *Self, position: usize, value: T) !void {
if (position > self.len) {
return error.OutOfRange;
}
defer self.len += 1;
const node = try self.allocator.create(Node);
node.* = Node{ .data = value };
var current = self.head;
// Find the node which is specified by the position
for (0..position) |_| {
if (current) |cur| {
current = cur.next;
}
}
// Put node in front of current
node.next = current;
if (current) |cur| {
node.*.prev = cur.prev;
if (cur.prev) |*prev| {
prev.*.next = node;
} else {
// When current has no prev, we are insert at head.
self.head = node;
}
cur.*.prev = node;
} else { // We are insert at tail, update node to new tail.
if (self.tail) |tail| {
node.*.prev = tail;
tail.*.next = node;
}
self.tail = node;
// Head may also be null for an empty list
if (null == self.head) {
self.head = node;
}
}
}
fn remove(self: *Self, value: T) bool {
var current = self.head;
while (current) |cur| : (current = cur.next) {
if (cur.data == value) {
// if the current node has a previous node
// then set the previous node's next to the current node's next
if (cur.prev) |prev| {
prev.next = cur.next;
} else {
// if the current node has no previous node
self.head = cur.next;
}
// if the current node has a next node
// then set the next node's previous to the current node's previous
if (cur.next) |next| {
next.prev = cur.prev;
} else {
// if the current node has no next node
// then set the tail to the current node's previous
self.tail = cur.prev;
}
self.allocator.destroy(cur);
self.len -= 1;
return true;
}
}
return false;
}
fn search(self: *Self, value: T) bool {
var current: ?*Node = self.head;
while (current) |cur| : (current = cur.next) {
if (cur.data == value) {
return true;
}
}
return false;
}
fn visit(self: Self, visitor: *const fn (i: usize, v: T) anyerror!void) !usize {
var current: ?*Node = self.head;
var i: usize = 0;
while (current) |cur| : (i += 1) {
try visitor(i, cur.data);
current = cur.next;
}
return i;
}
fn visitBackwards(self: Self, visitor: *const fn (i: usize, v: T) anyerror!void) !usize {
var current = self.tail;
var i: usize = 0;
while (current) |cur| : (i += 1) {
try visitor(i, cur.data);
current = cur.prev;
}
return i;
}
fn deinit(self: *Self) void {
var current = self.head;
while (current) |cur| {
const next = cur.next;
self.allocator.destroy(cur);
current = next;
}
self.head = null;
self.tail = null;
self.len = 0;
}
};
}
fn ensureList(lst: DoublyLinkedList(u32), comptime expected: []const u32) !void {
const visited_times = try lst.visit(struct {
fn visitor(i: usize, v: u32) !void {
if (expected.len == 0) {
unreachable;
} else {
try std.testing.expectEqual(v, expected[i]);
}
}
}.visitor);
try std.testing.expectEqual(visited_times, expected.len);
const visited_times2 = try lst.visitBackwards(struct {
fn visitor(i: usize, v: u32) !void {
if (expected.len == 0) {
unreachable;
} else {
try std.testing.expectEqual(v, expected[expected.len - i - 1]);
}
}
}.visitor);
try std.testing.expectEqual(visited_times2, expected.len);
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var list = DoublyLinkedList(u32).init(allocator);
defer list.deinit();
const values = [_]u32{ 1, 2, 3, 4, 5 };
for (values) |value| {
try list.insertLast(value);
}
try ensureList(list, &values);
try list.insertAt(1, 100);
try ensureList(list, &[_]u32{ 1, 100, 2, 3, 4, 5 });
try list.insertAt(0, 200);
try ensureList(list, &[_]u32{ 200, 1, 100, 2, 3, 4, 5 });
try std.testing.expect(list.remove(100));
try ensureList(list, &[_]u32{ 200, 1, 2, 3, 4, 5 });
// delete all
for (values) |value| {
try std.testing.expect(list.remove(value));
}
try std.testing.expect(list.remove(200));
try ensureList(list, &[_]u32{});
}