Define the data structure for a complete Doubly Linked List.

 The structure should support adding elements to the head, tail and middle of the list. 
 The structure should not allow circular loops


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


 
Module Checkit {
      Form 80, 50
      Class Null {}
      Global Null->Null()
      Class Node {
            group pred, succ
            dat=0
            Remove {
                  Print "destroyed", .dat
            }
            class: 
            module Node {
                  .pred->Null
                  .succ->Null
                  if match("N") Then Read .dat
            }
      }
      Class LList {
            Group Head, Tail
            Module PushTail(k as pointer) {
                  if .Tail is Null then {
                        .Head<=k
                        .Tail<=k
                  } else {
                        n=.Tail
                        .Tail<=k
                        k=>pred=n=>pred
                        n=>pred=k
                        k=>succ=n
                  }
            }
            Function RemoveTail {
                  n=.Tail
                  if n is .Head then {
                        .Head->Null
                        .Tail->Null
                  } Else { 
                        .Tail<=n=>succ
                        .Tail=>pred=n=>pred
                        n=>pred->Null
                  }
                  for n {
                        .succ->Null
                        .pred->Null
                  }
                  =n
            }
            Module PushHead(k as pointer) {
                  if .head is Null then {
                        .Head<=k
                        .Tail<=k
                  } else {
                        n=.head
                        .head<=k
                        k=>succ=n=>succ
                        n=>succ=k
                        k=>pred=n
                  }
            }
            Function RemoveHead {
                  n=.Head
                  if n is .Tail then {
                        .Head->Null
                        .Tail->Null
                  } Else { 
                      .Head<=n=>pred
                      .Head=>succ=n=>succ
                       n=>succ->Null    
                   }
                  for n {
                        .succ->Null
                        .pred->Null
                  }
                  =n
            }
            Module RemoveNode(k as pointer) {
                  pred=k=>pred
                  succ=k=>succ
                  if pred is succ then {
                        if .head is k else Error "Can't remove this node"
                        k=.RemoveHead()
                        clear k
                  } else {
                       pred=>succ=succ
                       succ=>pred=pred 
                  }
            }
            Module InsertAfter(k as pointer, n as pointer) {
                  pred=k=>pred
                  n=>pred=pred
                  n=>succ=k
                  pred=>succ=n
                  k=>pred=n
            }
            Function IsEmpty {
                  = .Head is null or .tail is null
            }
      class:
            Module LList {
                  .Head->Null
                  .Tail->Null
            }
      }
      m->Node(100)
 
      L=LList()
      L.PushTail m
      If not L.Head is Null then Print L.Head=>dat=100
      for i=101 to 103 {
            m->Node(i)
            L.PushTail m
            Print "ok....", i
      }
      for i=104 to 106 {
            m->Node(i)
            L.PushHead m
            Print "ok....", i
      }
 
      Print "Use Head to display from last to first"
      m=L.Head
      do {
            Print m=>dat
            m=m=>pred
      } Until m is null
      Print "ok, now find 3rd and remove it"
      m1=L.Head
      i=1 
      Index=3
      While i<Index {
            if m1 is null then exit
            m1=m1=>pred
            i++
      }
      If i<>Index then {
            Print "List has less than "; Index;" Items"
      } Else {
            Print "First add one new node"
                  newNode->Node(1000)
                  L.InsertAfter m1, newNode
                  L.RemoveNode m1
                  clear m1  ' last time m1 used here
                  newNode=Null
            Print "ok.............."
      }
      Print "Use Tail to display from first to last"
      m=L.Tail
      do {
            Print m=>dat
            m=m=>succ
      } Until m is null
 
 
      useother=True
      While not L.IsEmpty(){
            For This {
                  \\ we have to use a temporary variable name, here A
                         A=If(useother->L.RemoveTail(),L.RemoveHead())
                         ? A=>dat
                        useother~
                        \\ now we can try to perform removing
                        clear A
             }
      }
      Print "list is empty:"; L.IsEmpty()    
}
Checkit
 