Doubly-linked list/Definition: Difference between revisions

The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>

{{libheader|Action! Tool Kit}}

 

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

TestAddAfter(7,listEnd)

TestClear()

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_definition.png Screenshot from Atari 8-bit computer]

{{works with|ALGOL 68|Revision 1 - one extension to language used - PRAGMA READ - a non standard feature similar to C's #include directive.}}{{works with|ALGOL 68G|Any - tested with release algol68g-2.7}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

COMMENT REQUIRES:

MODE VALUE = ~;

MODE LINK = REF LINKNEW;

 

MODE LISTNEW = LINKNEW;

MODE LIST = REF LISTNEW;

link ISNT LINK(self);

 

# -*- coding: utf-8 -*- #

MODE VALUE = STRING; # user defined data type #

OD;

print(new line)

{{out}}

<pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program defDblList.s */

bx lr @ return

 

 

=={{header|ATS}}==

 

The reason for this complication is that, in ATS, a linear object can be treated as "mutable", without resorting to embedded C code. One cost of this is that an object of a linear type has to be freed explicitly. However, if it is cast to an "ordinary" (nonlinear) type, a garbage collector to handle freeing the object. Such casting is what I have done.

 

Here is ''dllist.sats''.

(* The public interface *)

 

typedef dllist_t (t : t@ype+) = [b : bool] dllist_t (t, b)

 

(dl : list (t, n)) : dllist_t t

 

 

 

Here is ''dllist.dats''.

 

#include "share/atspre_staload.hats"

types is bypassed by these interface template functions.

 

 

The usual garbage collector to use with ATS2 (Postiats) is Boehm

end

 

 

 

And here is ''dllist-demo.dats''.

 

staload "dllist.sats"

val _ = print_forwards dl

val _ = println! ()

 

 

=={{header|C}}==

 

#include <stdio.h>

#include <stdlib.h>

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

return n;

 

Simple test:

 

 

struct IntNode {

free(lista);

}

 

=={{header|C sharp|C#}}==

Though mutating the ''structure'' of a list can only be done through the <code>LinkedList<T></code> class, mutating the values contained by the nodes of a list is done through its individual <code>LinkedListNode<T></code> instances, as the <code>LinkedListNode<T>.Next</code>.Value property is settable.

 

 

class Program

}

}

 

{{out}}

=={{header|C++}}==

{{works with|C++11}}

#include <list>

 

std::cout << i << ' ';

std::cout << '\n';

{{out}}

<pre>

 

=={{header|Clojure}}==

 

(defprotocol PDoubleList

(defmethod print-method Node [n w]

(print-method (symbol "#:double_list.Node") w)

Usage:

;=> nil

(def dl (double-list (range 10)))

;=> #:double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}

(get-prev *1)

 

=={{header|Common Lisp}}==

 

(defstruct dlink content prev next)

 

acc

(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))

 

The following produces <code>(1 2 3 4)</code>.

 

(insert-head dlist 1)

(insert-tail dlist 4)

(bad-link (insert-before dlist next-to-last 42)))

(remove-link dlist bad-link))

 

=={{header|D}}==

 

class LinkedList(T)

}

writeln;

{{out}}

<pre>

{{libheader| boost.LinkedList}}[[https://github.com/MaiconSoft/DelphiBoostLib]]

{{Trans|C#}}

program Doubly_linked;

 

List.Free;

Readln;

 

=={{header|E}}==

def firstINode

def lastINode

}

return dlList

 

# value: <>

 

? for x in 11..20 { list.push(x) }

? list

 

=={{header|Erlang}}==

As with [[Singly-linked_list/Element_insertion]] a process is used to get mutability in Erlang's single assignment world.

-module( doubly_linked_list ).

 

loop_foreach_previous( _Fun, noprevious ) -> ok;

loop_foreach_previous( Fun, Next ) -> Next ! {foreach_previous, Fun}.

 

=={{header|F Sharp|F#}}==

type DList<'T> = {mutable front: DListAux<'T> option; mutable back: DListAux<'T> option} //'

 

if link.next = dlist.back then addBack dlist elt else

let e = Some {prev=Some link; data=elt; next=link.next}

 

=={{header|Fortran}}==

Tested with g95 and gfortran v. 4.6.

module dlist

implicit none

call tidy(mydll)

end program dl

 

{{out}}

Doubly-linked list has 5 element - bwd = 7, 5, 4, 3, 1

</pre>

 

=={{header|Go}}==

Go has nothing like an enforced invariant. Responsibility for preventing circular loops must be shared by all code that modifies the list. Given that, the following declaration ''enables'' code to do that efficiently.

int

next, prev *dlNode

members map[*dlNode]int

head, tail **dlNode

Or, just use the [http://golang.org/pkg/container/list/#Element container/list] package:

 

import "fmt"

fmt.Println(e.Value)

}

 

=={{header|Haskell}}==

For an efficient implementation, see the <code>Data.FDList</code> module provided by [http://hackage.haskell.org/package/liboleg liboleg]. But before using doubly linked lists at all, see [http://stackoverflow.com/questions/1844195/doubly-linked-list-in-a-purely-functional-programming-language this discussion on Stack Overflow].

 

 

type NodeID = Maybe Rational

fromList = foldr fcons empty

 

 

An example of use:

 

where l = mcons 'M' n1 n2 x

x = rcons 'Z' $ fcons 'a' $ fcons 'q' $ singleton 'w'

n1 = firstNode x

 

==Icon and {{header|Unicon}}==

The DoubleList is made from elements of DoubleLink. [[Doubly-Linked List (element)#Icon_and_Unicon]], [[Doubly-Linked List (element insertion)#Icon_and_Unicon]] and [[Doubly-Linked List (traversal)#Icon_and_Unicon]]

 

class DoubleList (item)

 

self.item := DoubleLink (value)

end

 

An <code>insert_before</code> method was added to the DoubleLink class:

 

# insert given node before this one, losing its existing connections

method insert_before (node)

self.prev_link := node

end

 

To test the double-linked list:

 

procedure main ()

dlist := DoubleList (5)

write (node.value)

end

 

{{out}}

The <code>LinkedList<T></code> class is the Doubly-linked list implementation in Java. There are a large number of methods supporting the list. An example is shown below.

 

import java.util.LinkedList;

 

}

{{out}}

<pre>

 

=={{header|Julia}}==

value::T

pred::Union{DLNode{T}, Nothing}

delete(node4)

print("From end to beginning post deletion: "); printconnected(node1, fromtail = true)

First value is 1 and last value is 3

From beginning to end: 1 -> 4 -> 2 -> 3

=={{header|Kotlin}}==

Rather than use the java.util.LinkedList<E> class, we will write our own simple LinkedList<E> class for this task:

 

class LinkedList<E> {

ll.insert(ll.last!!.prev, 3)

println(ll)

 

{{out}}

 

=={{header|Lua}}==

-------------------

-- IMPLEMENTATION:

local n222 = list:insertAfter(n22, 222) validate(list, "-1,0,1,11,111,2,22,222,3,33,4,44,444,5,55")

local n333 = list:insertBefore(n4, 333) validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55")

{{out}}

<pre>true

 

 

Module Checkit {

Form 80, 50

}

Checkit

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

ds["Append", #] & /@ {1, 5, 7, 0, 3, 2};

ds["Prepend", 9];

(* This is adding at the end and then swap to insert in to the middle: *)

ds["Append", 14]; ds["SwapPart", Round[ds["Length"]/2], ds["Length"]];

{{out}}

<pre>{9, 1, 5, 14, 0, 3, 2, 4, 7}</pre>

=={{header|Nim}}==

Nim has a doubly linked list already in the lists module of the standard library.

List[T] = object

head, tail: Node[T]

l2.prepend newNode("hello")

l2.append newNode("world")

{{out}}

<pre>15 -> 14 -> 12

 

=={{header|Oberon-2}}==

IMPORT Basic;

TYPE

size-: INTEGER;

END;

 

=={{header|Objeck}}==

use Collection;

 

while(list->Get() <> Nil);

}

 

=={{header|Oforth}}==

 

DNode method: initialize := next := prev := value ;

dl insertBack("B")

dl head insertAfter(DNode new("C", null , null))

 

{{out}}

| | | ---+---> end

+-----+-----+

(de 2list @

(let Prev NIL

(cons L Prev) ) ) )

 

For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].

 

=={{header|PL/I}}==

define structure

1 Node,

2 back_pointer handle(Node),

2 fwd_pointer handle(Node);

 

=={{header|PowerShell}}==

Create and populate the list:

$list = New-Object -TypeName 'Collections.Generic.LinkedList[PSCustomObject]'

 

 

$list

{{Out}}

<pre>

</pre>

Insert a value at the head:

$list.AddFirst([PSCustomObject]@{ID=123; X=123;Y=123}) | Out-Null

 

$list

{{Out}}

<pre>

</pre>

Insert a value in the middle:

$current = $list.First

 

 

$list

{{Out}}

<pre>

</pre>

Insert a value at the end:

$list.AddLast([PSCustomObject]@{ID=789; X=789;Y=789}) | Out-Null

 

$list

{{Out}}

<pre>

 

=={{header|PureBasic}}==

;the list of words that will be added to the list

words:

displayList(a(),"Insertion in Middle: ")

 

{{out}}

<pre>

datatype. See [https://wiki.python.org/moin/TimeComplexity TimeComplexity].

 

from collections import deque

 

for value in reversed(some_list):

print(value)

 

{{out}}

break links between nodes in other lists.

 

"""A doubly-linked list. Requires Python >=3.7"""

from __future__ import annotations

self.size -= 1

return value

 

=={{header|Racket}}==

The following is a port of the Common Lisp solution. The ouput is '(1 2 3 4).

 

#lang racket

(define-struct dlist (head tail) #:mutable #:transparent)

(remove-link dlist bad-link))

(dlist-elements dlist))

 

=={{header|Raku}}==

(formerly Perl 6)

This shows a complete example. (Other entries in the section focus on aspects of this solution.)

has DLElem[T] $.prev is rw;

has DLElem[T] $.next is rw;

 

say $dll.list; # 0 1 2 40 41 42

{{out}}

<pre>0 1 2 40 41 42

REXX doesn't have linked lists, as there are no pointers (or handles).

<br>However, linked lists can be simulated with lists in REXX.

call sy 'initializing the list.' ; call @init

call sy 'building list: Was it a cat I saw' ; call @put "Was it a cat I saw"

/*──────────────────────────────────────────────────────────────────────────────────────*/

@show: procedure expose $.; parse arg k,m,dir; if dir==-1 & k=='' then k=$.#

'''output'''

<pre style="height:30ex;overflow:scroll">

 

=={{header|Ring}}==

# Project : Doubly-linked list/Definition

 

svect = left(svect, len(svect) - 1)

see svect

Output:

<pre>

 

 

(r7rs)

(chicken (import r7rs)))

 

(display "conversion from a list:")

 

{{out}}

=={{header|Swift}}==

 

 

class Node<T> {

list.remove(node!)

 

 

{{out}}

[0, 1, 2, 3, 4, 5, 100, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 100, 6, 7, 8, 9]</pre>

 

=={{header|Tcl}}==

See also [[Doubly-Linked List (element)]] for a TclOO-based version.

 

proc dl {_name cmd {where error} {value ""}} {

upvar 1 $_name N

}

}

set testcases [split {

dl D insert head foo

if {[lsearch $argv -p] >= 0} {parray D}

}

 

=={{header|Visual Basic .NET}}==

 

Private m_Head As Node(Of T)

Private m_Tail As Node(Of T)

End Sub

 

 

=={{header|Wren}}==

{{libheader|Wren-llist}}

The DLinkedList class in the above module is a generic doubly-linked list and is implemented in such a way that circular loops are not possible. We therefore use it here.

 

var dll = DLinkedList.new()

System.print(dll)

for (i in 1..3) dll.remove(i)

 

{{out}}

[]

</pre>

 

=={{header|zkl}}==

fcn init(_value,_prev=Void,_next=Void)

{ var value=_value, prev=_prev, next=_next; }

}.fp(Ref(self),dir))

}

a.append("c").append("d");

a.last().append("e");

a.last().first().append("b");

foreach n in (a){ print(n," ") } println();

{{out}}

<pre>