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
<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 #
- 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;
- 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);
- 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);
- 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 */
- include <stdio.h>
- 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>