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

C

<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;

}</c>

Simple test:

<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);
   }

}</c>

Visual Basic .NET

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