Doubly-linked list/Definition
From Rosetta Code
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
See also Linked List
Contents |
[edit] 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
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
)
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
[edit] AutoHotkey
see Doubly-linked list/AutoHotkey
[edit] 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;
}
Simple test:
/* 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);
}
}
[edit] Common Lisp
(defstruct dlist head tail)
(defstruct dlink content prev next)
(defun insert-between (dlist before after data)
"Insert a fresh link containing DATA after existing link BEFORE if not nil and before existing link AFTER if not nil"
(let ((new-link (make-dlink :content data :prev before :next after)))
(if (null before)
(setf (dlist-head dlist) new-link)
(setf (dlink-next before) new-link))
(if (null after)
(setf (dlist-tail dlist) new-link)
(setf (dlink-prev after) new-link))
new-link))
(defun insert-before (dlist dlink data)
"Insert a fresh link containing DATA before existing link DLINK"
(insert-between dlist (dlink-prev dlink) dlink data))
(defun insert-after (dlist dlink data)
"Insert a fresh link containing DATA after existing link DLINK"
(insert-between dlist dlink (dlink-next dlink) data))
(defun insert-head (dlist data)
"Insert a fresh link containing DATA at the head of DLIST"
(insert-between dlist nil (dlist-head dlist) data))
(defun insert-tail (dlist data)
"Insert a fresh link containing DATA at the tail of DLIST"
(insert-between dlist (dlist-tail dlist) nil data))
(defun remove-link (dlist dlink)
"Remove link DLINK from DLIST and return its content"
(let ((before (dlink-prev dlink))
(after (dlink-next dlink)))
(if (null before)
(setf (dlist-head dlist) after)
(setf (dlink-next before) after))
(if (null after)
(setf (dlist-tail dlist) before)
(setf (dlink-prev after) before))))
(defun dlist-elements (dlist)
"Returns the elements of DLIST as a list"
(labels ((extract-values (dlink acc)
(if (null dlink)
acc
(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
(reverse (extract-values (dlist-head dlist) nil))))
The following produces (1 2 3 4).
(let ((dlist (make-dlist)))
(insert-head dlist 1)
(insert-tail dlist 4)
(insert-after dlist (dlist-head dlist) 2)
(let* ((next-to-last (insert-before dlist (dlist-tail dlist) 3))
(bad-link (insert-before dlist next-to-last 42)))
(remove-link dlist bad-link))
(print (dlist-elements dlist)))
[edit] D
class LinkedList(T)
{
Node!(T) head, tail;
/** Iterate in the forward direction. */
int opApply (int delegate(uint, Node!(T)) dg)
{
uint i = 0;
auto link = head;
int result = 0;
while (link)
{
result = dg (i, link);
if (result) return result;
i++;
link = link.next;
}
return result;
}
static LinkedList!(T) fromArray (T[] array)
{
Node!(T) link = null;
auto head = link;
auto self = new LinkedList!(T);
foreach (elem; array)
{
link = new Node!(T)(null, link, elem, self);
if (!head)
head = link;
}
return self;
}
}
class Node(T)
{
Node!(T) next;
Node!(T) previous;
LinkedList!(T) parent;
T value;
this (Node!(T) next, Node!(T) previous, T value, LinkedList!(T) parent)
in
{
assert (parent !is null);
}
body
{
this.next = next;
if (next)
next.previous = this;
if (previous)
previous.next = this;
this.previous = previous;
this.value = value;
this.parent = parent;
if (parent.head == next)
parent.head = this;
if (parent.tail == previous)
parent.tail = this;
}
/** Insert an element after this one. */
void insertAfter (T value)
{
new Node!(T)(this, next, value, parent);
}
/** Insert an element before this one. */
void insertBefore (T value)
{
new Node!(T)(previous, this, value, parent);
}
/** Remove the current node from the list. */
void remove ()
{
if (next)
next.previous = previous;
if (previous)
previous.next = next;
if (parent.tail == this)
parent.tail = previous;
if (parent.head == this)
parent.head = next;
}
}
void main ()
{
char[][] sample = ["was", "it", "a", "cat", "I", "saw"];
auto list = LinkedList!(char[]).fromArray (sample);
for (auto elem = list.head; elem; elem = elem.next)
{
writef ("%s ", elem.value);
if (elem.value == "it") elem.insertAfter("really");
}
writeln;
for (auto elem = list.tail; elem; elem = elem.previous)
{
writef ("%s ", elem.value);
}
writeln;
}
Output:
Iterate forward: Was it really a cat I saw Iterate backward: saw I cat a really it Was Empty from tail: saw I cat a really it Was
[edit] E
def makeDLList() {
def firstINode
def lastINode
def makeNode(var value, var prevI, var nextI) {
# To meet the requirement that the client cannot create a loop, the
# inter-node refs are protected: clients only get the external facet
# with invariant-preserving operations.
def iNode
def node { # external facet
to get() { return value }
to put(new) { value := new }
/** Return the value of the element of the list at the specified offset
from this element. */
to get(index :int) {
if (index > 0 && node.hasNext()) {
return nextI.node().get(index - 1)
} else if (index < 0 && node.hasPrev()) {
return prevI.node().get(index + 1)
} else if (index <=> 0) {
return value
} else {
throw("index out of range in dlList")
}
}
to hasPrev() {
return nextI != firstINode && nextI != null
}
to prev() {
if (!node.hasPrev()) {
throw("there is no previous node")
}
return prevI.node()
}
to hasNext() {
return nextI != lastINode && nextI != null
}
to next() {
if (!node.hasNext()) {
throw("there is no previous node")
}
return nextI.node()
}
to remove() {
if (prevI == null || nextI == null) { return }
prevI.setNextI(nextI)
nextI.setPrevI(prevI)
prevI := null
nextI := null
}
to insertAfter(newValue) {
def newI := makeNode(newValue, iNode, nextI)
nextI.setPrevI(newI)
nextI := newI
}
to insertBefore(newValue) {
prevI.node().insertAfter(newValue)
}
}
bind iNode { # internal facet
to node() { return node }
to nextI() { return nextI }
to prevI() { return prevI }
to setNextI(new) { nextI := new }
to setPrevI(new) { prevI := new }
}
return iNode
} # end makeNode
bind firstINode := makeNode(null, Ref.broken("no first prev"), lastINode)
bind lastINode := makeNode(null, firstINode, Ref.broken("no last next"))
def dlList {
to __printOn(out) {
out.print("<")
var sep := ""
for x in dlList {
out.print(sep)
out.quote(x)
sep := ", "
}
out.print(">")
}
to iterate(f) {
var n := firstINode
while (n.node().hasNext()) {
n := n.nextI()
f(n.node(), n.node()[])
}
}
to atFirst() { return firstINode.nextI().node() }
to atLast() { return lastINode.prevI().node() }
to insertFirst(new) { return firstINode.node().insertAfter(new) }
to push(new) { return lastINode.node().insertBefore(new) }
/** Return the node which has the specified value */
to nodeOf(value) {
for node => v ? (v == value) in dlList { return node }
}
}
return dlList
}
? def list := makeDLList()
# value: <>
? list.push(1)
? list
# value: <1>
? list.push(10)
? list.push(100)
? list
# value: <1, 10, 100>
? list.atFirst().insertAfter(5)
? list
# value: <1, 5, 10, 100>
? list.insertFirst(0)
? list
# value: <0, 1, 5, 10, 100>
? list.atLast().prev().remove()
? list
# value: <0, 1, 5, 100>
? list.atLast()[] := 10
? list
# value: <0, 1, 5, 10>
? for x in 11..20 { list.push(x) }
? list
# value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20>
[edit] Fortran
Tested with g95.
module dlist
implicit none
type node
type(node), pointer :: next => null()
type(node), pointer :: prev => null()
integer :: data
end type node
type dll
type(node), pointer :: head => null()
type(node), pointer :: tail => null()
integer :: num_nodes = 0
end type dll
public :: node, dll, append, prepend, insert, dump, reverse_dump, tidy
private :: init
contains
! Create a new doubly-linked list
type(dll) function new_dll()
new_dll = dll()
return
end function new_dll
! Append an element to the end of the list
subroutine append(dl2, value)
type(dll), intent(inout) :: dl2
integer, intent(in) :: value
type(node) :: element
type(node), pointer :: np
! If the list is empty
if (dl2%num_nodes == 0) then
call init(dl2, value)
return
end if
! Add new element to the end
dl2%num_nodes = dl2%num_nodes + 1
np => dl2%tail
allocate(dl2%tail)
dl2%tail%data = value
dl2%tail%prev => np
dl2%tail%prev%next => dl2%tail
end subroutine append
! Prepend an element to the beginning of the list
subroutine prepend(dl2, value)
type(dll), intent(inout) :: dl2
integer, intent(in) :: value
type(node) :: element
type(node), pointer :: np
if (dl2%num_nodes == 0) then
call init(dl2, value)
return
end if
dl2%num_nodes = dl2%num_nodes + 1
np => dl2%head
allocate(dl2%head)
dl2%head%data = value
dl2%head%next => np
dl2%head%next%prev => dl2%head
end subroutine prepend
! Insert immediately before the given index
subroutine insert(dl2, index, value)
type(dll), intent(inout) :: dl2
integer, intent(in) :: index
integer, intent(in) :: value
type(node), pointer :: element
type(node), pointer :: np1, np2
integer :: i
if (dl2%num_nodes == 0) then
call init(dl2, value)
return
end if
! If index is beyond the end then append
if (index > dl2%num_nodes) then
call append(dl2, value)
return
end if
! If index is less than 1 then prepend
if (index <= 1) then
call prepend(dl2, value)
return
end if
! Find the node at position 'index' counting from 1
np1 => dl2%head
do i=1, index-2
np1 => np1%next
end do
np2 => np1%next
! Create the new node
allocate(element)
element%data = value
! Connect it up
element%prev => np1
element%next => np2
np1%next => element
np2%prev => element
dl2%num_nodes = dl2%num_nodes + 1
end subroutine insert
subroutine dump(dl2)
type(dll), intent(in) :: dl2
type(node), pointer :: current
integer :: i
write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - fwd = '
current => dl2%head
i = 1
write(*,fmt='(i0,a)',advance='no') current%data,', '
do
current => current%next
if (.not. associated(current)) then
exit
end if
i = i + 1
if (i == dl2%num_nodes) then
write(*,'(i0)') current%data
else
write(*,fmt='(i0,a)',advance='no') current%data,', '
end if
end do
end subroutine dump
subroutine reverse_dump(dl2)
type(dll), intent(in) :: dl2
type(node), pointer :: current
integer :: i
write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - bwd = '
current => dl2%tail
write(*,fmt='(i0,a)',advance='no') current%data,', '
i = 1
do
current => current%prev
if (.not. associated(current)) then
exit
end if
i = i + 1
if (i == dl2%num_nodes) then
write(*,'(i0)') current%data
else
write(*,fmt='(i0,a)',advance='no') current%data,', '
end if
end do
end subroutine reverse_dump
! Deallocate all allocated memory
subroutine tidy(dl2)
type(dll), intent(in) :: dl2
type(node), pointer :: current, last
current => dl2%head
do
last => current
current => current%next
if (associated(last)) then
deallocate(last)
end if
if (associated(current, dl2%tail)) then
deallocate(current)
exit
end if
end do
end subroutine tidy
subroutine init(dl2, value)
type(dll), intent(inout) :: dl2
integer, intent(in) :: value
allocate(dl2%head)
dl2%tail => dl2%head
dl2%tail%data = value
dl2%num_nodes = 1
return
end subroutine init
end module dlist
program dl
use dlist
implicit none
type(dll) :: mydll
mydll = new_dll()
call append(mydll, 5)
call append(mydll, 7)
call prepend(mydll, 3)
call prepend(mydll, 1)
call insert(mydll, 3, 4)
call dump(mydll)
call reverse_dump(mydll)
call tidy(mydll)
end program dl
Output:
Doubly-linked list has 5 element - fwd = 1, 3, 4, 5, 7 Doubly-linked list has 5 element - bwd = 7, 5, 4, 3, 1
[edit] F#
type DListAux<'T> = {mutable prev: DListAux<'T> option; data: 'T; mutable next: DListAux<'T> option}
type DList<'T> = {mutable front: DListAux<'T> option; mutable back: DListAux<'T> option}
let empty() = {front=None; back=None}
let addFront dlist elt =
match dlist.front with
| None ->
let e = Some {prev=None; data=elt; next=None}
dlist.front <- e
dlist.back <- e
| Some e2 ->
let e1 = Some {prev=None; data=elt; next=Some e2}
e2.prev <- e1
dlist.front <- e1
let addBack dlist elt =
match dlist.back with
| None -> addFront dlist elt
| Some e2 ->
let e1 = Some {prev=Some e2; data=elt; next=None}
e2.next <- e1
dlist.back <- e1
let addAfter dlist link elt =
if link.next = dlist.back then addBack dlist elt else
let e = Some {prev=Some link; data=elt; next=link.next}
link.next <- e
[edit] Haskell
For an efficient implementation, see the Data.FDList module provided by liboleg. But before using doubly linked lists at all, see this discussion on Stack Overflow.
import qualified Data.Map as M
type NodeID = Maybe Rational
data Node a = Node
{vNode :: a,
pNode, nNode :: NodeID}
type DLList a = M.Map Rational (Node a)
empty = M.empty
singleton a = M.singleton 0 $ Node a Nothing Nothing
fcons :: a -> DLList a -> DLList a
fcons a list | M.null list = singleton a
| otherwise = M.insert newid new $
M.insert firstid changed list
where (firstid, Node firstval _ secondid) = M.findMin list
newid = firstid - 1
new = Node a Nothing (Just firstid)
changed = Node firstval (Just newid) secondid
rcons :: a -> DLList a -> DLList a
rcons a list | M.null list = singleton a
| otherwise = M.insert lastid changed $
M.insert newid new list
where (lastid, Node lastval penultimateid _) = M.findMax list
newid = lastid + 1
changed = Node lastval penultimateid (Just newid)
new = Node a (Just lastid) Nothing
mcons :: a -> Node a -> Node a -> DLList a -> DLList a
mcons a n1 n2 = M.insert n1id left .
M.insert midid mid . M.insert n2id right
where Node n1val farleftid (Just n2id) = n1
Node n2val (Just n1id) farrightid = n2
midid = (n1id + n2id) / 2 -- Hence the use of Rationals.
mid = Node a (Just n1id) (Just n2id)
left = Node n1val farleftid (Just midid)
right = Node n2val (Just midid) farrightid
firstNode :: DLList a -> Node a
firstNode = snd . M.findMin
lastNode :: DLList a -> Node a
lastNode = snd . M.findMax
nextNode :: DLList a -> Node a -> Maybe (Node a)
nextNode l n = nNode n >>= flip M.lookup l
prevNode :: DLList a -> Node a -> Maybe (Node a)
prevNode l n = pNode n >>= flip M.lookup l
fromList = foldr fcons empty
toList = map vNode . M.elems
An example of use:
main = putStrLn $ toList l
where l = mcons 'M' n1 n2 x
x = rcons 'Z' $ fcons 'a' $ fcons 'q' $ singleton 'w'
n1 = firstNode x
Just n2 = nextNode x n1
[edit] J
Doubly linked lists are antithetical to J.
First, J already has a built in list data type which is heavily optimized, and micromanaging issues like list traversal bypasses all of that design and architecture.
Second, an implementation of "doubly linked" conflicts with the "once and only once" character of many good implementations. In a doubly linked list order must be specified redundantly and that redundancy creates maintenance costs which are justified only in rare cases.
So, first, here is a native J list:
list=: 2 3 4 5 11
To implement a doubly linked list, one could create a list of successor indices and another list of predecessor indices.
First, let us define a different order for our list element, so we can easily show that our doubly linked list is logically distinct from the built in list. If we use "alphabeted order by names of numbers" we would have the list 11 5 7 3 2
3 is followed by 2 5 is followed by 7 7 is followed by 3 11 is followed by 5
and
2 is preceded by 3 3 is preceded by 7 5 is preceded by 11 7 is preceded by 5
To represent this in J, we can define additional lists with the successor index and predecessor index for each node:
successors=: _ 0 3 1 2 predecessors=: 1 3 4 2 __
Note that the successor for the end of the list is _ and the successor for the beginning of the list is __
To check for loops, look for repeated indices in either of these ordering lists. To add an element to the doubly linked list, you would add an element to the data list, and then update the successor and predecessor list by appending to the end the index of the item designated as the successor/predecessor of the new item and replacing the previous holder of that value with the newly valid index.
Finally, note that we can remove elements from the doubly linked list without removing them from the data list. We might wish to chain removed elements together to facilitate re-use of their positions. If we want to do this, we will need a place to start:
garbage=: __
When we delete an item we place the old garbage value as its successor index and we define the garbage variable to be the index we just deleted. And when adding to the list we first check if garbage has a valid index and if so we take over that position in the structure and update garbage with the previous value of the successor.
Needless to say, this approach is expensive and inefficient.
[edit] JavaScript
See Doubly-Linked List (element)#JavaScript, Doubly-Linked List (element insertion)#JavaScript and Doubly-Linked List (traversal)#JavaScript
[edit] PL/I
define structure
1 Node,
2 value fixed decimal,
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
[edit] PicoLisp
For the list of double-cell structures described in Doubly-linked list/Element definition#PicoLisp, we define a header structure, containing one pointer to the start and one to the end of the list.
+------------> start
|
+--+--+-----+
| | | ---+---> end
+-----+-----+
# Build a doubly-linked list
(de 2list @
(let Prev NIL
(let L
(make
(while (args)
(setq Prev (chain (list (next) Prev))) ) )
(cons L Prev) ) ) )
(setq *DLst (2list 'was 'it 'a 'cat 'I 'saw))
For output of the example data, see Doubly-linked list/Traversal#PicoLisp.
[edit] PureBasic
DataSection
;the list of words that will be added to the list
words:
Data.s "One", "Two", "Three", "Four", "Five", "Six", "EndOfData"
EndDataSection
Procedure displayList(List x.s(), title$)
;display all elements from list of strings
Print(title$)
ForEach x()
Print(x() + " ")
Next
PrintN("")
EndProcedure
OpenConsole()
NewList a.s() ;create a new list of strings
;add words to the head of list
Restore words
Repeat
Read.s a$
If a$ <> "EndOfData"
ResetList(a()) ;Move to head of list
AddElement(a())
a() = a$
EndIf
Until a$ = "EndOfData"
displayList(a(),"Insertion at Head: ")
ClearList(a())
;add words to the tail of list
Restore words
LastElement(a()) ;Move to the tail of the list
Repeat
Read.s a$
If a$ <> "EndOfData"
AddElement(a()) ;after insertion the new position is still at the tail
a() = a$
EndIf
Until a$ = "EndOfData"
displayList(a(),"Insertion at Tail: ")
ClearList(a())
;add words to the middle of list
Restore words
ResetList(a()) ;Move to the tail of the list
Repeat
Read.s a$
If a$ <> "EndOfData"
c = CountList(a())
If c > 1
SelectElement(a(),Random(c - 2)) ;insert after a random element but before tail
Else
FirstElement(a())
EndIf
AddElement(a())
a() = a$
EndIf
Until a$ = "EndOfData"
displayList(a(),"Insertion in Middle: ")
Repeat: Until Inkey() <> ""
Example output:
Insertion at Head: Six Five Four Three Two One Insertion at Tail: One Two Three Four Five Six Insertion at Middle: One Five Six Three Four Two
[edit] Python
In the high level language Python, its list native datatype should be used. It automatically preserves the integrity of the list w.r.t. loops and allows insertion at any point using list.insert() via an integer index into the list rather than a machine-code level pointer to a list element.
[edit] Ruby
See Doubly-Linked List (element)#Ruby, Doubly-Linked List (element insertion)#Ruby and Doubly-Linked List (traversal)#Ruby
[edit] Tcl
This task was earlier marked as unfeasible for Tcl. Tcl lists are compact arrays of pointers to values. However, on very long lists, insertions and deletions (if not at end) may require copying a large amount of data. In such cases, the implementation below may be helpful. It provides a single dl command, which is called with the name of a DList, a method name, and possibly more arguments as required. The testcases below should give a good idea. The asList and asList2 methods demonstrate forward and backward traversal.
See also Doubly-Linked List (element) for a TclOO-based version.
package require Tcl 8.4
proc dl {_name cmd {where error} {value ""}} {
upvar 1 $_name N
switch -- $cmd {
insert {
if ![info exists N()] {set N() {"" "" 0}}
set id [lindex $N() 2]
lset N() 2 [incr id]
switch -- $where {
head {
set prev {}
set next [lindex $N() 0]
lset N() 0 $id
}
end {
set prev [lindex $N() 1]
set next {}
lset N() 1 $id
}
default {
set prev $where
set next [lindex $N($where) 1]
lset N($where) 1 $id
}
}
if {$prev ne ""} {lset N($prev) 1 $id}
if {$next ne ""} {lset N($next) 0 $id}
if {[lindex $N() 1] eq ""} {lset N() 1 $id}
set N($id) [list $prev $next $value]
return $id
}
delete {
set i $where
if {$where eq "head"} {set i [dl N head]}
if {$where eq "end"} {set i [dl N end]}
foreach {prev next} $N($i) break
if {$prev ne ""} {lset N($prev) 1 $next}
if {$next ne ""} {lset N($next) 0 $prev}
if {[dl N head] == $i} {lset N() 0 $next}
if {[dl N end] == $i} {lset N() 1 $prev}
unset N($i)
}
findfrom {
if {$where eq "head"} {set where [dl N head]}
for {set i $where} {$i ne ""} {set i [dl N next $i]} {
if {[dl N get $i] eq $value} {return $i}
}
}
get {lindex $N($where) 2}
set {lset N($where) 2 $value; set value}
head {lindex $N() 0}
end {lindex $N() 1}
next {lindex $N($where) 1}
prev {lindex $N($where) 0}
length {expr {[array size N]-1}}
asList {
set res {}
for {set i [dl N head]} {$i ne ""} {set i [dl N next $i]} {
lappend res [dl N get $i]
}
return $res
}
asList2 {
set res {}
for {set i [dl N end]} {$i ne ""} {set i [dl N prev $i]} {
lappend res [dl N get $i]
}
return $res
}
}
}
# Testing code
set testcases [split {
dl D insert head foo
dl D insert end bar
dl D insert head hello
dl D set [dl D head] hi
dl D insert end grill
set i [dl D findfrom head bar]
dl D set $i BAR
dl D insert $i and
dl D length
dl D asList2
dl D delete $i
dl D findfrom head nix
dl D delete head
dl D delete end
dl D delete end
dl D delete head
dl D length
} \n]
foreach case $testcases {
if {[string trim $case] ne ""} {
puts " $case -> [eval $case] : [dl D asList]"
if {[lsearch $argv -p] >= 0} {parray D}
}
}
[edit] 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
Categories: Programming Tasks | Data Structures | ALGOL 68 | AutoHotkey | C | Common Lisp | D | E | Fortran | F Sharp | Haskell | J | JavaScript | PL/I | PicoLisp | PureBasic | Python | Ruby | Tcl | Visual Basic .NET | TI-83 BASIC/Omit | TI-89 BASIC/Omit
