Doubly-linked list/Definition

Doubly-linked list/Definition
You are encouraged to solve this task according to the task description, using any language you may know.

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

ALGOL 68

Translation of: C

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang ada> MODE DATA = STRING; # user defined data type #

MODE MNODE = STRUCT (

 NODE pred,
      succ,
 DATA value

);

MODE LIST = REF MNODE; MODE NODE = REF MNODE;

STRUCT (

 PROC LIST new list,
 PROC (LIST)BOOL is empty,
 PROC (LIST)NODE get head,
                 get tail,
 PROC (LIST, NODE)NODE add tail,
                           add head,
 PROC (LIST)NODE remove head,
                 remove tail,
 PROC (LIST, NODE, NODE)NODE insert after,
 PROC (LIST, NODE)NODE remove node

) class list;

new list OF class list := LIST: (

 HEAP MNODE master link; 
 master link := (master link, master link, ~);
 master link

);

is empty OF class list := (LIST self)BOOL:

 (LIST(pred OF self) :=: LIST(self)) AND (LIST(self) :=: LIST(succ OF self));

get head OF class list := (LIST self)NODE:

 succ OF self;

get tail OF class list := (LIST self)NODE:

 pred OF self;

add tail OF class list := (LIST self, NODE node)NODE:

 (insert after OF class list)(self, pred OF self, node);
 

add head OF class list := (LIST self, NODE node)NODE:

 (insert after OF class list)(self, succ OF self, node);

remove head OF class list := (LIST self)NODE:

 (remove node OF class list)(self, succ OF self);

remove tail OF class list := (LIST self)NODE:

 (remove node OF class list)(self, pred OF self);

insert after OF class list := (LIST self, NODE cursor, NODE node)NODE: (

 succ OF node := succ OF cursor;
 pred OF node := cursor;
 succ OF cursor := node;
 pred OF succ OF node := node;
 node

);

remove node OF class list := (LIST self, NODE node)NODE: (

 succ OF pred OF node := succ OF node;
 pred OF succ OF node := pred OF node;
 succ OF node := pred OF node := NIL; # garbage collection hint #
 node

);

main: (

   []DATA sample = ("Was", "it", "a", "cat", "I", "saw");

   LIST list a := new list OF class list;

   NODE tmp;

   IF list a :/=: REF LIST(NIL) THEN # technically "list a" is never NIL #

1. Add some data to a list #

       FOR i TO UPB sample DO
           tmp := HEAP MNODE;
           IF tmp :/=: NODE(NIL) THEN # technically "tmp" is never NIL #
              value OF tmp := sample[i];
              (add tail OF class list)(list a, tmp)
           FI
       OD;

1. Iterate throught the list forward #

       NODE node := (get head OF class list)(list a);
       print("Iterate orward: ");
       WHILE  node :/=: NODE(list a) DO
           print((value OF node, " "));
           node := succ OF node
       OD;
       print(new line);
 

1. Iterate throught the list backward #

       node := (get tail OF class list)(list a);
       print("Iterate backward: ");
       WHILE  node :/=: NODE(list a) DO
           print((value OF node, " "));
           node := pred OF node
       OD;
       print(new line);

1. Finally empty the list #

       print("Empty from tail: ");
       WHILE NOT (is empty OF class list)(list a) DO
             tmp := (remove tail OF class list)(list a);
             print((value OF tmp, " "))
             # sweep heap #
       OD;
       print(new line)
       # sweep heap #
   FI

) </lang> Output:

Iterate forward: Was it a cat I saw 
Iterate backward: saw I cat a it Was 
Empty from tail: saw I cat a it Was 

C

<lang c>/* double linked list */

1. include <stdio.h>
2. include <stdlib.h>

struct List {

  struct MNode *head;
  struct MNode *tail;
  struct MNode *tail_pred;

};

struct MNode {

  struct MNode *succ;
  struct MNode *pred;

};

typedef struct MNode *NODE; typedef struct List *LIST;

/*

• • LIST l = newList()
  • create (alloc space for) and initialize a list
• /

LIST newList(void);

/*

• • int isEmpty(LIST l)
  • test if a list is empty
• /

int isEmpty(LIST);

/*

• • NODE n = getTail(LIST l)
  • get the tail node of the list, without removing it
• /

NODE getTail(LIST);

/*

• • NODE n = getHead(LIST l)
  • get the head node of the list, without removing it
• /

NODE getHead(LIST);

/*

• • NODE rn = addTail(LIST l, NODE n)
  • add the node n to the tail of the list l, and return it (rn==n)
• /

NODE addTail(LIST, NODE);

/*

• • NODE rn = addHead(LIST l, NODE n)
  • add the node n to the head of the list l, and return it (rn==n)
• /

NODE addHead(LIST, NODE);

/*

• • NODE n = remHead(LIST l)
  • remove the head node of the list and return it
• /

NODE remHead(LIST);

/*

• • NODE n = remTail(LIST l)
  • remove the tail node of the list and return it
• /

NODE remTail(LIST);

/*

• • NODE rn = insertAfter(LIST l, NODE r, NODE n)
  • insert the node n after the node r, in the list l; return n (rn==n)
• /

NODE insertAfter(LIST, NODE, NODE);

/*

• • NODE rn = removeNode(LIST l, NODE n)
  • remove the node n (that must be in the list l) from the list and return it (rn==n)
• /

NODE removeNode(LIST, NODE);

LIST newList(void) {

   LIST tl = malloc(sizeof(struct List));
   if ( tl != NULL )
   {
      tl->tail_pred = (NODE)&tl->head;
      tl->tail = NULL;
      tl->head = (NODE)&tl->tail;
      return tl;
   }
   return NULL;

}

int isEmpty(LIST l) {

  return (l->head->succ == 0);

}

NODE getHead(LIST l) {

 return l->head;

}

NODE getTail(LIST l) {

 return l->tail_pred;

}

NODE addTail(LIST l, NODE n) {

   n->succ = (NODE)&l->tail;
   n->pred = l->tail_pred;
   l->tail_pred->succ = n;
   l->tail_pred = n;
   return n;

}

NODE addHead(LIST l, NODE n) {

   n->succ = l->head;
   n->pred = (NODE)&l->head;
   l->head->pred = n;
   l->head = n;
   return n;

}

NODE remHead(LIST l) {

  NODE h;
  h = l->head;
  l->head = l->head->succ;
  l->head->pred = (NODE)&l->head;
  return h;

}

NODE remTail(LIST l) {

  NODE t;
  t = l->tail_pred;
  l->tail_pred = l->tail_pred->pred;
  l->tail_pred->succ = (NODE)&l->tail;
  return t;

}

NODE insertAfter(LIST l, NODE r, NODE n) {

  n->pred = r; n->succ = r->succ;
  n->succ->pred = n; r->succ = n;
  return n;

}

NODE removeNode(LIST l, NODE n) {

  n->pred->succ = n->succ;
  n->succ->pred = n->pred;
  return n;

}</lang>

Simple test:

<lang c>/* basic test */

struct IntNode {

 struct MNode node;
 int data;

};

int main() {

   int i;
   LIST lista;
   struct IntNode *m;
   NODE n;
   
   lista = newList();
   if ( lista != NULL )
   {
     for(i=0; i < 5; i++)
     {
         m = malloc(sizeof(struct IntNode));
         if ( m != NULL )
         {
            m->data = rand()%64;
            addTail(lista, (NODE)m);
         }
     }
     while( !isEmpty(lista) )
     {
           m = (struct IntNode *)remTail(lista);
           printf("%d\n", m->data);
           free(m);
     }
     free(lista);
   }

}</lang>

Visual Basic .NET

<lang vbnet>Public Class DoubleLinkList(Of T)

  Private m_Head As Node(Of T)
  Private m_Tail As Node(Of T)

  Public Sub AddHead(ByVal value As T)
      Dim node As New Node(Of T)(Me, value)

      If m_Head Is Nothing Then
          m_Head = Node
          m_Tail = m_Head
      Else
          node.Next = m_Head
          m_Head = node
      End If

  End Sub

  Public Sub AddTail(ByVal value As T)
      Dim node As New Node(Of T)(Me, value)

      If m_Tail Is Nothing Then
          m_Head = node
          m_Tail = m_Head
      Else
          node.Previous = m_Tail
          m_Tail = node
      End If
  End Sub

  Public ReadOnly Property Head() As Node(Of T)
      Get
          Return m_Head
      End Get
  End Property

  Public ReadOnly Property Tail() As Node(Of T)
      Get
          Return m_Tail
      End Get
  End Property

  Public Sub RemoveTail()
      If m_Tail Is Nothing Then Return

      If m_Tail.Previous Is Nothing Then 'empty
          m_Head = Nothing
          m_Tail = Nothing
      Else
          m_Tail = m_Tail.Previous
          m_Tail.Next = Nothing
      End If
  End Sub

  Public Sub RemoveHead()
      If m_Head Is Nothing Then Return

      If m_Head.Next Is Nothing Then 'empty
          m_Head = Nothing
          m_Tail = Nothing
      Else
          m_Head = m_Head.Next
          m_Head.Previous = Nothing
      End If
  End Sub

End Class

Public Class Node(Of T)

  Private ReadOnly m_Value As T
  Private m_Next As Node(Of T)
  Private m_Previous As Node(Of T)
  Private ReadOnly m_Parent As DoubleLinkList(Of T)

  Public Sub New(ByVal parent As DoubleLinkList(Of T), ByVal value As T)
      m_Parent = parent
      m_Value = value
  End Sub

  Public Property [Next]() As Node(Of T)
      Get
          Return m_Next
      End Get
      Friend Set(ByVal value As Node(Of T))
          m_Next = value
      End Set
  End Property

  Public Property Previous() As Node(Of T)
      Get
          Return m_Previous
      End Get
      Friend Set(ByVal value As Node(Of T))
          m_Previous = value
      End Set
  End Property

  Public ReadOnly Property Value() As T
      Get
          Return m_Value
      End Get
  End Property

  Public Sub InsertAfter(ByVal value As T)
      If m_Next Is Nothing Then
          m_Parent.AddTail(value)
      ElseIf m_Previous Is Nothing Then
          m_Parent.AddHead(value)
      Else
          Dim node As New Node(Of T)(m_Parent, value)
          node.Previous = Me
          node.Next = Me.Next
          Me.Next.Previous = node
          Me.Next = node
      End If
  End Sub

  Public Sub Remove()
      If m_Next Is Nothing Then
          m_Parent.RemoveTail()
      ElseIf m_Previous Is Nothing Then
          m_Parent.RemoveHead()
      Else
          m_Previous.Next = Me.Next
          m_Next.Previous = Me.Previous
      End If
  End Sub

End Class</lang>