/* An implementation of doubly linked lists */

class ListItem <: Object {
  Object? obj;
  ListItem? prev;
  ListItem? next;

  new (Object? o)() (
    this.obj = o;
    this.prev = null;
    this.next = null
  )
}

class List <: Object {
  ListItem? head;

  new ()() (
    this.head = null
  )

  int is_empty() (
    this.head == null
  )

  /* insert an item at the head of the list */
  unit insert(Object o) (
    ListItem new_item = new ListItem(o);
    new_item.next = this.head;
    if? (ListItem old_head = this.head)
      old_head.prev = new_item;
    this.head = new_item
  )

  /* remove an element from the list */
  unit delete(ListItem item) ( 
    if (this.head == item) (
      /* item is the first element of the list */
      this.head = item.next;
      if? (ListItem next = item.next) 
        next.prev = null
    ) else (
      /* item is in the middle or end of the list */
      if? (ListItem prev = item.prev) (
        prev.next = item.next;
        if? (ListItem next = item.next)
           next.prev = prev
      ) else fail string ( "invalid list" )
    )
    
 )
}

0