#lang racket

;; Defining a new structure, ilist, as a datatype to
;; store linked-list data.
(define-struct ilist (head tail) #:mutable #:transparent)

;; Defines an end-of-ilist condition
;; Runs in constant time O(1)
(define iempty null)

;; Predicate to test for the end-of-ilist condition
;; Runs in constant time O(1)
(define iempty? (lambda (x) (if (equal? x iempty) #t #f)))

;; Creates an ilist with first element(head) is ANY and
;; second element(tail) is another ilist.
;; Runs in constant time O(1)
(define icons (lambda (x y) (make-ilist x y)))

;; Returns the head of a consumed ilist.
;; Runs in constant time O(1)
(define ifirst (lambda (x) (ilist-head x)))

;; Returns the tail of the consumed ilist.
;; Runs in constant time O(1)
(define irest (lambda (x) (ilist-tail x)))

;; Returns the length of a given ilist, ie how many
;; "nested" ilist structures exist before the
;; end-of-list condition is met.
;; Runs in log(n) time O(log(n)) where n = number of
;; elements (heads before end) in ilist.
(define (ilength ilist)
  (if (iempty? ilist) 0
      (+ 1 (ilength (irest ilist)))))

;; Consumes to ilists and concatenates the first onto
;; the second. iappend is recursive and runs in log(n).
(define iappend (lambda (x y) (if (iempty? x) y
                                  (icons (ifirst x) (iappend (irest x) y)))))

(define tester (icons 1 (icons 2 (icons 3 iempty))))

(define tester2 (icons 4 (icons 5 (icons 6 iempty))))