Created
August 18, 2022 07:21
-
-
Save hackwaly/78a8d9a82b7aa3abb860d5753acc4173 to your computer and use it in GitHub Desktop.
Doubly linked list in OCaml
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (* Doubly linked list *) | |
| type 'a node = { mutable prev : 'a node; mutable next : 'a node; data : 'a } | |
| type 'a list = List of 'a node [@@unboxed] | |
| let create () = | |
| let rec root = { prev = root; next = root; data = Obj.magic `Dummy } in | |
| List root | |
| let iter (List root) f = | |
| let node = ref root.next in | |
| while !node != root do | |
| f !node; | |
| node := !node.next | |
| done | |
| let rev_iter (List root) f = | |
| let node = ref root.prev in | |
| while !node != root do | |
| f !node; | |
| node := !node.prev | |
| done | |
| let first (List root) = | |
| let node = root.next in | |
| if node == root then None else Some node | |
| let last (List root) = | |
| let node = root.prev in | |
| if node == root then None else Some node | |
| let is_first (List root) node = node == root.next | |
| let is_last (List root) node = node == root.prev | |
| let _insert prev next data = | |
| let node = { prev; next; data } in | |
| prev.next <- node; | |
| next.prev <- node; | |
| node | |
| let append (List root) data = | |
| let prev = root.prev in | |
| let next = root in | |
| _insert prev next data | |
| let prepend (List root) data = | |
| let prev = root in | |
| let next = root.next in | |
| _insert prev next data | |
| let is_empty (List root) = root.prev == root && root.next == root | |
| let insert_before next data = | |
| let prev = next.prev in | |
| _insert prev next data | |
| let insert_after prev data = | |
| let next = prev.next in | |
| _insert prev next data | |
| let remove node = | |
| let prev = node.prev in | |
| let next = node.next in | |
| prev.next <- next; | |
| next.prev <- prev; | |
| node.data | |
| let clear (List root) = | |
| root.prev <- root; | |
| root.next <- root |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment