Doubly-linked list/Element insertion: Difference between revisions
Doubly-linked list/Element insertion (view source)
Revision as of 12:02, 28 November 2023
, 6 months ago→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (97 intermediate revisions by 61 users not shown) | |||
Line 1:
This is much like inserting into a [[Singly-Linked List (element insertion)|Singly-Linked List]], but with added assignments so that the backwards-pointing links remain correct.
{{Template:See also lists}}
=={{header|Action!}}==
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}}
<syntaxhighlight lang="action!">CARD EndProg ;required for ALLOCATE.ACT
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
DEFINE PTR="CARD"
DEFINE NODE_SIZE="5"
TYPE ListNode=[CHAR data PTR prv,nxt]
ListNode POINTER listBegin,listEnd
PROC AddBegin(CHAR v)
ListNode POINTER n
n=Alloc(NODE_SIZE)
n.data=v
n.prv=0
n.nxt=listBegin
IF listBegin THEN
listBegin.prv=n
ELSE
listEnd=n
FI
listBegin=n
RETURN
PROC AddEnd(CHAR v)
ListNode POINTER n
n=Alloc(NODE_SIZE)
n.data=v
n.prv=listEnd
n.nxt=0
IF listEnd THEN
listEnd.nxt=n
ELSE
listBegin=n
FI
listEnd=n
RETURN
PROC AddAfter(CHAR v ListNode POINTER node)
ListNode POINTER n,tmp
IF node=0 THEN
PrintE("The node is null!") Break()
ELSEIF node=listEnd THEN
AddEnd(v)
ELSE
n=Alloc(NODE_SIZE)
n.data=v
n.nxt=node.nxt
n.prv=node
tmp=node.nxt
tmp.prv=n
node.nxt=n
FI
RETURN
PROC Clear()
ListNode POINTER n,next
n=listBegin
WHILE n
DO
next=n.nxt
Free(n,NODE_SIZE)
n=next
OD
listBegin=0
listEnd=0
RETURN
PROC PrintList()
ListNode POINTER n
n=listBegin
Print("(")
WHILE n
DO
Put(n.data)
IF n.nxt THEN
Print(", ")
FI
n=n.nxt
OD
PrintE(")")
RETURN
PROC TestAddBegin(CHAR v)
AddBegin(v)
PrintF("Add '%C' at the begin:%E",v)
PrintList()
RETURN
PROC TestAddAfter(CHAR v ListNode POINTER node)
AddAfter(v,node)
PrintF("Add '%C' after '%C':%E",v,node.data)
PrintList()
RETURN
PROC TestClear()
Clear()
PrintE("Clear the list:")
PrintList()
RETURN
PROC Main()
Put(125) PutE() ;clear screen
AllocInit(0)
listBegin=0
listEnd=0
PrintList()
TestAddBegin('A)
TestAddAfter('B,listBegin)
TestAddAfter('C,listBegin)
TestClear()
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_insertion.png Screenshot from Atari 8-bit computer]
<pre>
()
Add 'A' at the begin:
(A)
Add 'B' after 'A':
(A, B)
Add 'C' after 'A':
(A, C, B)
Clear the list:
()
</pre>
=={{header|Ada}}==
Define the procedure:
Create links and form the list.
Element insertion using the generic doubly linked list defined in the standard Ada containers library.
begin
Put_Line(To_String(Element(Position)));
end Print;
The_List : List;
begin
The_List.Append(To_Unbounded_String("A"));
The_List.Append(To_Unbounded_String("B"));
The_List.Insert(Before => The_List.Find(To_Unbounded_String("B")),
New_Item => To_Unbounded_String("C"));
The_List.Iterate(Print'access);
end List_Insertion;</syntaxhighlight>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1 - no extensions to language used.}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
<syntaxhighlight lang="algol68">#!/usr/local/bin/a68g --script #
# SEMA do link OF splice = LEVEL 1 #
MODE LINK = STRUCT (
REF LINK prev,
REF LINK next,
DATA value
);
# BEGIN rosettacode task specimen code:
can handle insert both before the first, and after the last link #
PROC insert after = (REF LINK #self,# prev, DATA new data)LINK: (
# DOWN do link OF splice OF self; to make thread safe #
REF LINK next = next OF prev;
HEAP LINK new link := LINK(prev, next, new data);
next OF prev := prev OF next := new link;
# UP do link OF splice OF self; #
new link
);
PROC insert before = (REF LINK #self,# next, DATA new data)LINK:
insert after(#self,# prev OF next, new data);
# END rosettacode task specimen code #
# Test case: #
MODE DATA = STRUCT(INT year elected, STRING name);
FORMAT data fmt = $dddd": "g"; "$;
test:(
# manually initialise the back splices #
LINK presidential splice;
presidential splice := (presidential splice, presidential splice, SKIP);
# manually build the chain #
LINK previous, incumbent, elect;
previous := (presidential splice, incumbent, DATA(1993, "Clinton"));
incumbent:= (previous, elect, DATA(2001, "Bush" ));
elect := (incumbent, presidential splice, DATA(2008, "Obama" ));
insert after(incumbent, LOC DATA := DATA(2004, "Cheney"));
REF LINK node := previous;
WHILE REF LINK(node) ISNT presidential splice DO
printf((data fmt, value OF node));
node := next OF node
OD;
print(new line)
)</syntaxhighlight>
Output:
<pre>
1993: Clinton; 2001: Bush; 2004: Cheney; 2008: Obama;
</pre>
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw"> % record type to hold an element of a doubly linked list of integers %
record DListIElement ( reference(DListIElement) prev
; integer iValue
; reference(DListIElement) next
);
% additional record types would be required for other element types %
% inserts a new element into the list, before e %
reference(DListIElement) procedure insertIntoDListIBefore( reference(DListIElement) value e
; integer value v
);
begin
reference(DListIElement) newElement;
newElement := DListIElement( null, v, e );
if e not = null then begin
% the element we are inserting before is not null %
reference(DListIElement) ePrev;
ePrev := prev(e);
prev(newElement) := ePrev;
prev(e) := newElement;
if ePrev not = null then next(ePrev) := newElement
end if_e_ne_null ;
newElement
end insertIntoDListiAfter ;</syntaxhighlight>
=={{header|AutoHotkey}}==
see [[Doubly-linked list/AutoHotkey]]
=={{header|Axe}}==
<syntaxhighlight lang="axe">Lbl INSERT
{r₁+2}ʳ→{r₂+2}ʳ
r₁→{r₂+4}ʳ
r₂→{{r₂+2}ʳ+4}ʳ
r₂→{r₁+2}ʳ
r₁
Return</syntaxhighlight>
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> DIM node{pPrev%, pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
a.pNext% = b{}
a.iData% = 123
b.pPrev% = a{}
b.iData% = 456
c.iData% = 789
PROCinsert(a{}, c{})
END
DEF PROCinsert(here{}, new{})
LOCAL temp{} : DIM temp{} = node{}
new.pNext% = here.pNext%
new.pPrev% = here{}
!(^temp{}+4) = new.pNext%
temp.pPrev% = new{}
here.pNext% = new{}
ENDPROC
</syntaxhighlight>
=={{header|C}}==
Define the function:
}</syntaxhighlight>
Production code should also include checks that the passed links are valid (e.g. not null pointers). There should also be code to handle special cases, such as when *anchor is the end of the existing list (i.e. anchor->next is a null pointer).
Line 69 ⟶ 328:
Create links, and form the list:
This list is now {a,b}, and c is separate.
Now call the function:
This function call changes the list from {a,b} to {a,b,c}.
=={{header|C sharp|C#}}==
The function handles creation of nodes in addition to inserting them.
<syntaxhighlight lang="csharp">static void InsertAfter(Link prev, int i)
{
if (prev.next != null)
{
prev.next.prev = new Link() { item = i, prev = prev, next = prev.next };
prev.next = prev.next.prev;
}
else
prev.next = new Link() { item = i, prev = prev };
}</syntaxhighlight>
Example use:
<syntaxhighlight lang="csharp">static void Main()
{
//Create A(5)->B(7)
var A = new Link() { item = 5 };
InsertAfter(A, 7);
//Insert C(15) between A and B
InsertAfter(A, 15);
}</syntaxhighlight>
=={{header|C++}}==
C++ already has own linked list structure. If we were to roll our own linked list, we could implement function inserting new value after specific node like that:
<syntaxhighlight lang="cpp">template <typename T>
void insert_after(Node<T>* N, T&& data)
{
auto node = new Node<T>{N, N->next, std::forward(data)};
if(N->next != nullptr)
N->next->prev = node;
N->next = node;
}</syntaxhighlight>
=={{header|Clojure}}==
This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better.
<syntaxhighlight lang="clojure">(defrecord Node [prev next data])
(defn new-node [prev next data]
(Node. (ref prev) (ref next) data))
(defn new-list [head tail]
(List. (ref head) (ref tail)))
(defn insert-between [node1 node2 new-node]
(dosync
(ref-set (:next node1) new-node)
(ref-set (:prev new-node) node1)
(ref-set (:next new-node) node2)
(ref-set (:prev node2) new-node)))
(set! *print-level* 1)
;; warning: depending on the value of *print-level*
;; this could cause a stack overflow when printing
(let [h (new-node nil nil :A)
t (new-node nil nil :B)]
(insert-between h t (new-node nil nil :C))
(new-list h t))</syntaxhighlight>
=={{header|Common Lisp}}==
Code is on the [[Doubly-Linked List]] page, in function <code>insert-between</code>.
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio;
struct Node(T) {
T data;
typeof(this)* prev, next;
}
/// If prev is null, prev gets to point to a new node.
void insertAfter(T)(ref Node!T* prev, T item) pure nothrow {
if (prev) {
auto newNode = new Node!T(item, prev, prev.next);
prev.next = newNode;
if (newNode.next)
newNode.next.prev = newNode;
} else
prev = new Node!T(item);
}
void show(T)(Node!T* list) {
while (list) {
write(list.data, " ");
list = list.next;
}
writeln;
}
void main() {
Node!(string)* list;
insertAfter(list, "A");
list.show;
insertAfter(list, "B");
list.show;
insertAfter(list, "C");
list.show;
}</syntaxhighlight>
{{out}}
<pre>A
A B
A C B </pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader|Boost.LinkedList}}[https://github.com/MaiconSoft/DelphiBoostLib]
<syntaxhighlight lang="delphi">
program Element_insertion;
{$APPTYPE CONSOLE}
uses
System.SysUtils,Boost.LinkedList;
var
List:TLinkedList<Integer>;
Node:TLinkedListNode<Integer>;
begin
List := TLinkedList<Integer>.Create;
Node:= List.Add(5);
List.AddAfter(Node,7);
List.AddAfter(Node,15);
Writeln(List.ToString);
List.Free;
Readln;
end.</syntaxhighlight>
{{out}}
<pre>[ 5, 15, 7]</pre>
See [[#Pascal]] for vanilla version.
=={{header|E}}==
<syntaxhighlight lang="e">def insert(after, value) {
def newNode := makeElement(value, after, after.getNext())
after.getNext().setPrev(newNode)
after.setNext(newNode)
}</syntaxhighlight>
<syntaxhighlight lang="e">insert(A_node, C)</syntaxhighlight>
=={{header|Erlang}}==
Using the code in [[Doubly-linked_list/Definition]].
{{out}}
<pre>
2> doubly_linked_list:task().
foreach_next a
foreach_next c
foreach_next b
foreach_previous b
foreach_previous c
foreach_previous a
</pre>
=={{header|Fortran}}==
In ISO Fortran 95 or later:
<syntaxhighlight lang="fortran">module dlList
public :: node, insertAfter, getNext
type node
real :: data
type( node ), pointer :: next => null()
type( node ), pointer :: previous => null()
end type node
contains
subroutine insertAfter(nodeBefore, value)
type( node ), intent(inout), target :: nodeBefore
type( node ), pointer :: newNode
real, intent(in) :: value
allocate( newNode )
newNode%data = value
newNode%next => nodeBefore%next
newNode%previous => nodeBefore
if (associated( newNode%next )) then
newNode%next%previous => newNode
end if
newNode%previous%next => newNode
end subroutine insertAfter
subroutine delete(current)
type( node ), intent(inout), pointer :: current
if (associated( current%next )) current%next%previous => current%previous
if (associated( current%previous )) current%previous%next => current%next
deallocate(current)
end subroutine delete
end module dlList
program dlListTest
use dlList
type( node
head%data = 1.0
do
call insertAfter(current, 2.0**i)
current => current%next
end do
current => head
do while (associated(current))
print *, current%data
next => current%next
if (.not. associated(current, head)) call delete(current)
current => next
end do
end program dlListTest</syntaxhighlight>
Output:
<syntaxhighlight lang="fortran">1.
2.
4.
8.
16.
32.
64.
128.
256.
512.
1024.
2048.
4096.
8192.
16384.
32768.
65536.
131072.
262144.
524288.
1048576.</syntaxhighlight>
=={{header|FreeBASIC}}==
{{trans|Yabasic}}
<syntaxhighlight lang="freebasic">#define FIL 1
#define DATO
#define LPREV 3
#define LNEXT 4
Dim Shared As Integer countNodes, Nodes
countNodes = 0
Nodes = 10
Dim Shared As Integer list(Nodes, 4)
list(0, LNEXT) = 1
Function searchNode(node As Integer) As Integer
Dim As Integer Node11
For i As Integer = 0 To node-1
Node11 = list(Node11, LNEXT)
Next i
Return Node11
End Function
Sub insertNode(node As Integer, newNode As Integer)
Dim As Integer Node11, i
If countNodes = 0 Then node = 2
For i = 1 To Nodes
If Not list(i, FIL) Then Exit For
Next
list(i, FIL) = True
list(i, DATO) = newNode
Node11 = searchNode(node)
list(i, LPREV) = list(Node11, LPREV)
list(list(i, LPREV), LNEXT) = i
If i <> Node11 Then list(i, LNEXT) = Node11 : list(Node11, LPREV) = i
countNodes += 1
If countNodes = Nodes Then Nodes += 10 : Redim list(Nodes, 4)
End Sub
Sub removeNode(n As Integer)
Dim As Integer Node11 = searchNode(n)
list(list(Node11, LPREV), LNEXT) = list(Node11, LNEXT)
list(list(Node11, LNEXT), LPREV) = list(Node11, LPREV)
list(Node11, LNEXT) = 0
list(Node11, LPREV) = 0
list(Node11, FIL) = False
countNodes -= 1
End Sub
Sub printNode(node As Integer)
Dim As Integer Node11 = searchNode(node)
Print list(Node11, DATO);
Print
End Sub
Sub traverseList()
For i As Integer = 1 To countNodes
printNode(i)
Next i
End Sub
insertNode(1, 1000)
insertNode(2, 2000)
insertNode(2, 3000)
traverseList()
removeNode(2)
Print
traverseList()
Sleep</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de Yabasic.
</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
import "fmt"
type dlNode struct {
string
next, prev *dlNode
}
type dlList struct {
head, tail *dlNode
}
func (list *dlList) String() string {
if list.head == nil {
return fmt.Sprint(list.head)
}
r := "[" + list.head.string
for p := list.head.next; p != nil; p = p.next {
r += " " + p.string
}
return r + "]"
}
func (list *dlList) insertTail(node *dlNode) {
if list.tail == nil {
list.head = node
} else {
list.tail.next = node
}
node.next = nil
node.prev = list.tail
list.tail = node
}
func (list *dlList) insertAfter(existing, insert *dlNode) {
insert.prev = existing
insert.next = existing.next
existing.next.prev = insert
existing.next = insert
if existing == list.tail {
list.tail = insert
}
}
func main() {
dll := &dlList{}
fmt.Println(dll)
a := &dlNode{string: "A"}
dll.insertTail(a)
dll.insertTail(&dlNode{string: "B"})
fmt.Println(dll)
dll.insertAfter(a, &dlNode{string: "C"})
fmt.Println(dll)
}</syntaxhighlight>
Output:
<pre>
<nil>
[A B]
[A C B]
</pre>
=={{header|Haskell}}==
Using the algebraic data type and update functions from [[Doubly-Linked_List_(element)#Haskell]].
<syntaxhighlight lang="haskell">
insert _ Leaf = Leaf
insert nv l@(Node pl v r) = (\(Node c _ _) -> c) new
where new = updateLeft left . updateRight right $ Node l nv r
left = Node pl v new
right = case r of
Leaf -> Leaf
Node _ v r -> Node new v r
</syntaxhighlight>
==Icon and {{header|Unicon}}==
Uses Unicon classes.
<syntaxhighlight lang="unicon">
class DoubleLink (value, prev_link, next_link)
# insert given node after this one, losing its existing connections
method insert_after (node)
node.prev_link := self
if (\next_link) then next_link.prev_link := node
node.next_link := next_link
self.next_link := node
end
initially (value, prev_link, next_link)
self.value := value
self.prev_link := prev_link # links are 'null' if not given
self.next_link := next_link
end
</syntaxhighlight>
=={{header|J}}==
Using the list element definition at [[Doubly-linked_list/Element_definition#J]]
(pred;succ;<data) conew 'DoublyLinkedListElement'
This creates a new node containing the specified data between the nodes pred and succ.
=={{header|Java}}==
The <code>LinkedList<T></code> class is the Doubly-linked list implementation in Java. There are a large number of methods supporting the list.
The Java implementation does not a method to add an element based on another element. However, we can use methods from the base class to create a <code>AddAfter</code> method. A class with this method inherting all methods from the <code>LinkedList<T></code> class is shown below.
<syntaxhighlight lang="java">
import java.util.LinkedList;
@SuppressWarnings("serial")
public class DoublyLinkedListInsertion<T> extends LinkedList<T> {
public static void main(String[] args) {
DoublyLinkedListInsertion<String> list = new DoublyLinkedListInsertion<String>();
list.addFirst("Add First 1");
list.addFirst("Add First 2");
list.addFirst("Add First 3");
list.addFirst("Add First 4");
list.addFirst("Add First 5");
traverseList(list);
list.addAfter("Add First 3", "Add New");
traverseList(list);
}
/*
* Add after indicated node. If not in the list, added as the last node.
*/
public void addAfter(T after, T element) {
int index = indexOf(after);
if ( index >= 0 ) {
add(index + 1, element);
}
else {
addLast(element);
}
}
private static void traverseList(LinkedList<String> list) {
System.out.println("Traverse List:");
for ( int i = 0 ; i < list.size() ; i++ ) {
System.out.printf("Element number %d - Element value = '%s'%n", i, list.get(i));
}
System.out.println();
}
}
</syntaxhighlight>
{{out}}
<pre>
Traverse List:
Element number 0 - Element value = 'Add First 5'
Element number 1 - Element value = 'Add First 4'
Element number 2 - Element value = 'Add First 3'
Element number 3 - Element value = 'Add First 2'
Element number 4 - Element value = 'Add First 1'
Traverse List:
Element number 0 - Element value = 'Add First 5'
Element number 1 - Element value = 'Add First 4'
Element number 2 - Element value = 'Add First 3'
Element number 3 - Element value = 'Add New'
Element number 4 - Element value = 'Add First 2'
Element number 5 - Element value = 'Add First 1'
</pre>
=={{header|JavaScript}}==
See [[Doubly-Linked_List_(element)#JavaScript]]
<syntaxhighlight lang="javascript">DoublyLinkedList.prototype.insertAfter = function(searchValue, nodeToInsert) {
if (this._value == searchValue) {
var after = this.next();
this.next(nodeToInsert);
nodeToInsert.prev(this);
nodeToInsert.next(after);
after.prev(nodeToInsert);
}
else if (this.next() == null)
throw new Error(0, "value '" + searchValue + "' not found in linked list.")
else
this.next().insertAfter(searchValue, nodeToInsert);
}
var list = createDoublyLinkedListFromArray(['A','B']);
list.insertAfter('A', new DoublyLinkedList('C', null, null));</syntaxhighlight>
=={{header|Julia}}==
<syntaxhighlight lang="julia">mutable struct DLNode{T}
value::T
pred::Union{DLNode{T}, Nothing}
succ::Union{DLNode{T}, Nothing}
DLNode(v) = new{typeof(v)}(v, nothing, nothing)
end
function insertpost(prevnode, node)
succ = prevnode.succ
prevnode.succ = node
node.pred = prevnode
node.succ = succ
if succ != nothing
succ.pred = node
end
node
end
function printfromroot(root)
print(root.value)
while root.succ != nothing
root = root.succ
print(" -> $(root.value)")
end
println()
end
node1 = DLNode(1)
printfromroot(node1)
node2 = DLNode(2)
node3 = DLNode(3)
insertpost(node1, node2)
printfromroot(node1)
insertpost(node1, node3)
printfromroot(node1)
</syntaxhighlight> {{output}} <pre>
1
1 -> 2
1 -> 3 -> 2
</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.2
class Node<T: Number>(var data: T, var prev: Node<T>? = null, var next: Node<T>? = null) {
override fun toString(): String {
val sb = StringBuilder(this.data.toString())
var node = this.next
while (node != null) {
sb.append(" -> ", node.data.toString())
node = node.next
}
return sb.toString()
}
}
fun <T: Number> insert(after: Node<T>, new: Node<T>) {
new.next = after.next
if (after.next != null) after.next!!.prev = new
new.prev = after
after.next = new
}
fun main(args: Array<String>) {
val a = Node(1)
val b = Node(3, a)
a.next = b
println("Before insertion : $a")
val c = Node(2)
insert(after = a, new = c)
println("After insertion : $a")
}</syntaxhighlight>
{{out}}
<pre>
Before insertion : 1 -> 3
After insertion : 1 -> 2 -> 3
</pre>
=={{header|Lua}}==
see [[Doubly-linked_list/Definition#Lua]]
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ds = CreateDataStructure["DoublyLinkedList"];
ds["Append", "A"];
ds["Append", "B"];
ds["Append", "C"];
ds["SwapPart", 2, 3];
ds["Elements"]</syntaxhighlight>
{{out}}
<pre>{"A", "C", "B"}</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">proc insertAfter[T](l: var List[T], r, n: Node[T]) =
n.prev = r
n.next = r.next
n.next.prev = n
r.next = n
if r == l.tail: l.tail = n</syntaxhighlight>
=={{header|Oberon-2}}==
<syntaxhighlight lang="oberon2">
PROCEDURE (dll: DLList) InsertAfter*(p: Node; o: Box.Object);
VAR
n: Node;
BEGIN
n := NewNode(o);
n.prev := p;
n.next := p.next;
IF p.next # NIL THEN p.next.prev := n END;
p.next := n;
IF p = dll.last THEN dll.last := n END;
INC(dll.size)
END InsertAfter;
</syntaxhighlight>
=={{header|Objeck}}==
<syntaxhighlight lang="objeck">method : public : native : AddBack(value : Base) ~ Nil {
node := ListNode->New(value);
if(@head = Nil) {
@head := node;
@tail := @head;
}
else {
@tail->SetNext(node);
node->SetPrevious(@tail);
@tail := node;
};
}</syntaxhighlight>
=={{header|OCaml}}==
===with dlink===
<syntaxhighlight lang="ocaml">(* val _insert : 'a dlink -> 'a dlink -> unit *)
let _insert anchor newlink =
newlink.next <- anchor.next;
newlink.prev <- Some anchor;
begin match newlink.next with
| None -> ()
| Some next ->
next.prev <-Some newlink;
end;
anchor.next <- Some newlink;;
(* val insert : 'a dlink option -> 'a -> unit *)
let insert dl v =
match dl with
| (Some anchor) -> _insert anchor {data=v; prev=None; next=None}
| None -> invalid_arg "dlink empty";;</syntaxhighlight>
testing in the top level:
<syntaxhighlight lang="ocaml"># type t = A | B | C ;;
type t = A | B | C
# let dl = dlink_of_list [A; B] in
insert dl C;
list_of_dlink dl ;;
- : t list = [A; C; B]</syntaxhighlight>
===with nav_list===
<syntaxhighlight lang="ocaml">(* val insert : 'a nav_list -> 'a -> 'a nav_list *)
let insert (prev, cur, next) v = (prev, cur, v::next)</syntaxhighlight>
testing in the top level:
<syntaxhighlight lang="ocaml"># type t = A | B | C ;;
type t = A | B | C
# let nl = nav_list_of_list [A; B] ;;
val nl : 'a list * t * t list = ([], A, [B])
# insert nl C ;;
- : 'a list * t * t list = ([], A, [C; B])</syntaxhighlight>
=={{header|Oforth}}==
Complete definition is here : [[../Definition#Oforth]]
<syntaxhighlight lang="oforth">: test // ( -- aDList )
| dl |
DList new ->dl
dl insertFront("A")
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
dl ;</syntaxhighlight>
{{out}}
<pre>
>test .s
[1] (DList) [A, C, B]
</pre>
=={{header|Oz}}==
Warning: Do not use in real programs.
<syntaxhighlight lang="oz">declare
fun {CreateNewNode Value}
node(prev:{NewCell nil}
next:{NewCell nil}
value:Value)
end
proc {InsertAfter Node NewNode}
Next = Node.next
in
(NewNode.next) := @Next
(NewNode.prev) := Node
case @Next of nil then skip
[] node(prev:NextPrev ...) then
NextPrev := NewNode
end
Next := NewNode
end
A = {CreateNewNode a}
B = {CreateNewNode b}
C = {CreateNewNode c}
in
{InsertAfter A B}
{InsertAfter A C}</syntaxhighlight>
=={{header|Pascal}}==
end;</syntaxhighlight>
Actually, a more likely real world scenario is 'insert after A'. So...
end;</syntaxhighlight>
=={{header|
<syntaxhighlight lang="perl">my %node_model = (
data => 'something',
prev => undef,
next => undef,
);
sub insert
{
my ($anchor, $newlink) = @_;
$newlink->{next} = $anchor->{next};
$newlink->{prev} = $anchor;
$newlink->{next}->{prev} = $newlink;
$anchor->{next} = $newlink;
}
# create the list {A,B}
my $node_a = { %node_model };
my $node_b = { %node_model };
$node_a->{next} = $node_b;
$node_b->{prev} = $node_a;
# insert element C into a list {A,B}, between elements A and B.
my $node_c = { %node_model };
insert($node_a, $node_c);</syntaxhighlight>
=={{header|Phix}}==
See also [[Doubly-linked_list/Traversal#Phix|Doubly-linked_list/Traversal]].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_dll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">prv</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}}
</pre>
=={{header|PicoLisp}}==
This works with the structures described in
[[Doubly-linked list/Definition#PicoLisp]] and
[[Doubly-linked list/Element definition#PicoLisp]].
<syntaxhighlight lang="picolisp"># Insert an element X at position Pos
(de 2insert (X Pos DLst)
(let (Lst (nth (car DLst) (dec (* 2 Pos))) New (cons X (cadr Lst) Lst))
(if (cadr Lst)
(con (cdr @) New)
(set DLst New) )
(if (cdr Lst)
(set @ New)
(con DLst New) ) ) )
(setq *DL (2list 'A 'B)) # Build a two-element doubly-linked list
(2insert 'C 2 *DL) # Insert C at position 2</syntaxhighlight>
For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
define structure
1 Node,
2 value fixed decimal,
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
/* Given that 'Current" points at some node in the linked list : */
P = NEW (: Node :); /* Create a node. */
get (P => value);
P => fwd_pointer = Current => fwd_pointer;
/* Points the new node at the next one. */
Current => fwd_pinter = P;
/* Points the current node at the new one. */
P => back_pointer = Current;
/* Points the new node back at the current one. */
Q = P => fwd_pointer;
Q => back_pointer = P;
/* Points the next node to the new one. */
</syntaxhighlight>
=={{header|Pop11}}==
<syntaxhighlight lang="pop11">define insert_double(list, element);
lvars tmp;
if list == [] then
Line 154 ⟶ 1,214:
insert_double(A, B) -> _;
;;; insert C between A and b
insert_double(A, C) -> _;</syntaxhighlight>
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">Structure node
*prev.node
*next.node
value.c ;use character type for elements in this example
EndStructure
Procedure insertAfter(element.c, *c.node)
;insert new node *n after node *c and set it's value to element
Protected *n.node = AllocateMemory(SizeOf(node))
If *n
*n\value = element
*n\prev = *c
If *c
*n\next = *c\next
*c\next = *n
EndIf
EndIf
ProcedureReturn *n
EndProcedure
Procedure displayList(*dl.node)
Protected *n.node = *dl
Repeat
Print(Chr(*n\Value) + " ")
*n = *n\next
Until *n = #Null
EndProcedure
If OpenConsole()
Define dl.node, *n.node
*n = insertAfter('A',dl)
insertAfter('B',*n)
insertAfter('C',*n)
displayList(dl)
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf</syntaxhighlight>
Sample output:
<pre>A C B</pre>
=={{header|Python}}==
=={{header|
Code is on the [[Doubly-Linked List]] page, in function <code>insert-between</code>.
=={{header|Raku}}==
(formerly Perl 6)
Using the generic definitions from [[Doubly-linked_list/Definition#Raku]]:
<syntaxhighlight lang="raku" line>role DLElem[::T] {
has DLElem[T] $.prev is rw;
has DLElem[T] $.next is rw;
has T $.payload = T;
method pre-insert(T $payload) {
die "Can't insert before beginning" unless $!prev;
my $elem = ::?CLASS.new(:$payload);
$!prev.next = $elem;
$elem.prev = $!prev;
$elem.next = self;
$!prev = $elem;
$elem;
}
method post-insert(T $payload) {
die "Can't insert after end" unless $!next;
my $elem = ::?CLASS.new(:$payload);
$!next.prev = $elem;
$elem.next = $!next;
$elem.prev = self;
$!next = $elem;
$elem;
}
method delete {
die "Can't delete a sentinel" unless $!prev and $!next;
$!next.prev = $!prev;
$!prev.next = $!next; # conveniently returns next element
}
}
role DLList[::DLE] {
has DLE $.first;
has DLE $.last;
submethod BUILD {
$!first = DLE.new;
$!last = DLE.new;
$!first.next = $!last;
$!last.prev = $!first;
}
method list { ($!first.next, *.next ...^ !*.next).map: *.payload }
method reverse { ($!last.prev, *.prev ...^ !*.prev).map: *.payload }
}
class DLElem_Str does DLElem[Str] {}
class DLList_Str does DLList[DLElem_Str] {}
my $sdll = DLList_Str.new;
my $b = $sdll.first.post-insert('A').post-insert('B');
$b.pre-insert('C');
say $sdll.list; # A C B</syntaxhighlight>
{{out}}
<pre>A C B</pre>
=={{header|REXX}}==
REXX doesn't have linked lists, as there are no pointers (or handles).
<br>However, linked lists can be simulated with lists in REXX.
<syntaxhighlight lang="rexx">/*REXX program that implements various List Manager functions. */
/*┌────────────────────────────────────────────────────────────────────┐
┌─┘ Functions of the List Manager └─┐
│ │
│ @init ─── initializes the List. │
│ │
│ @size ─── returns the size of the List [could be 0 (zero)]. │
│ │
│ @show ─── shows (displays) the complete List. │
│ @show k,1 ─── shows (displays) the Kth item. │
│ @show k,m ─── shows (displays) M items, starting with Kth item. │
│ @show ,,─1 ─── shows (displays) the complete List backwards. │
│ │
│ @get k ─── returns the Kth item. │
│ @get k,m ─── returns the M items starting with the Kth item. │
│ │
│ @put x ─── adds the X items to the end (tail) of the List. │
│ @put x,0 ─── adds the X items to the start (head) of the List. │
│ @put x,k ─── adds the X items to before of the Kth item. │
│ │
│ @del k ─── deletes the item K. │
│ @del k,m ─── deletes the M items starting with item K. │
└─┐ ┌─┘
└────────────────────────────────────────────────────────────────────┘*/
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'
call sy 'displaying list size.' ; say 'list size='@size()
call sy 'forward list' ; call @show
call sy 'backward list' ; call @show ,,-1
call sy 'showing 4th item' ; call @show 4,1
call sy 'showing 6th & 6th items' ; call @show 5,2
call sy 'adding item before item 4: black' ; call @put 'black',4
call sy 'showing list' ; call @show
call sy 'adding to tail: there, in the ...'; call @put 'there, in the shadows, stalking its prey (and next meal).'
call sy 'showing list' ; call @show
call sy 'adding to head: Oy!' ; call @put 'Oy!',0
call sy 'showing list' ; call @show
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────subroutines─────────────────────────*/
p: return word(arg(1),1)
sy: say; say left('',30) "───" arg(1) '───'; return
@hasopt: arg o; return pos(o,opt)\==0
@size: return $.#
@init: $.@=''; $.#=0; return 0
@adjust: $.@=space($.@); $.#=words($.@); return 0
@parms: arg opt
if @hasopt('k') then k=min($.#+1,max(1,p(k 1)))
if @hasopt('m') then m=p(m 1)
if @hasopt('d') then dir=p(dir 1)
return
@show: procedure expose $.; parse arg k,m,dir
if dir==-1 & k=='' then k=$.#
m=p(m $.#);
call @parms 'kmd'
say @get(k,m,dir);
return 0
@get: procedure expose $.; arg k,m,dir,_
call @parms 'kmd'
do j=k for m by dir while j>0 & j<=$.#
_=_ subword($.@,j,1)
end /*j*/
return strip(_)
@put: procedure expose $.; parse arg x,k
k=p(k $.#+1)
call @parms 'k'
$.@=subword($.@,1,max(0,k-1)) x subword($.@,k)
call @adjust
return 0
@del: procedure expose $.; arg k,m
call @parms 'km'
_=subword($.@,k,k-1) subword($.@,k+m)
$.@=_
call @adjust
return</syntaxhighlight>
'''output'''
<pre style="height:50ex;overflow:scroll">
─── initializing the list. ───
─── building list: Was it a cat I saw ───
─── displaying list size. ───
list size=6
─── forward list ───
Was it a cat I saw
─── backward list ───
saw I cat a it Was
─── showing 4th item ───
cat
─── showing 6th & 6th items ───
I saw
─── adding item before item 4: black ───
─── showing list ───
Was it a black cat I saw
─── adding to tail: there, in the ... ───
─── showing list ───
Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).
─── adding to head: Oy! ───
─── showing list ───
Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">class DListNode
def insert_after(search_value, new_value)
if search_value == value
new_node = self.class.new(new_value, nil, nil)
next_node = self.succ
self.succ = new_node
new_node.prev = self
new_node.succ = next_node
next_node.prev = new_node
elsif self.succ.nil?
raise StandardError, "value #{search_value} not found in list"
else
self.succ.insert_after(search_value, new_value)
end
end
end
head = DListNode.from_array([:a, :b])
head.insert_after(:a, :c)</syntaxhighlight>
=={{header|Rust}}==
=== Simply using the standard library ===
<syntaxhighlight lang="rust">use std::collections::LinkedList;
fn main() {
let mut list = LinkedList::new();
list.push_front(8);
}</syntaxhighlight>
=== The behind-the-scenes implementation ===
This expands upon the implementation defined in [[Doubly-linked list/Element definition#The_behind-the-scenes_implementation]] and consists of the relevant lines from the LinkedList implementation in the Rust standard library.
<syntaxhighlight lang="rust">impl<T> Node<T> {
fn new(v: T) -> Node<T> {
Node {value: v, next: None, prev: Rawlink::none()}
}
}
impl<T> Rawlink<T> {
fn none() -> Self {
Rawlink {p: ptr::null_mut()}
}
fn some(n: &mut T) -> Rawlink<T> {
Rawlink{p: n}
}
}
impl<'a, T> From<&'a mut Link<T>> for Rawlink<Node<T>> {
fn from(node: &'a mut Link<T>) -> Self {
match node.as_mut() {
None => Rawlink::none(),
Some(ptr) => Rawlink::some(ptr)
}
}
}
fn link_no_prev<T>(mut next: Box<Node<T>>) -> Link<T> {
next.prev = Rawlink::none();
Some(next)
}
impl<T> LinkedList<T> {
#[inline]
fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
match self.list_head {
None => {
self.list_head = link_no_prev(new_head);
self.list_tail = Rawlink::from(&mut self.list_head);
}
Some(ref mut head) => {
new_head.prev = Rawlink::none();
head.prev = Rawlink::some(&mut *new_head);
mem::swap(head, &mut new_head);
head.next = Some(new_head);
}
}
self.length += 1;
}
pub fn push_front(&mut self, elt: T) {
self.push_front_node(Box::new(Node::new(elt)));
}
}</syntaxhighlight>
=={{header|Swift}}==
<syntaxhighlight lang="swift">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
class Node<T> {
var value: T
fileprivate var prev: NodePtr<T>?
fileprivate var next: NodePtr<T>?
init(value: T, prev: NodePtr<T>? = nil, next: NodePtr<T>? = nil) {
self.value = value
self.prev = prev
self.next = next
}
}
@discardableResult
func insert<T>(_ val: T, after: Node<T>? = nil, list: NodePtr<T>? = nil) -> NodePtr<T> {
let node = NodePtr<T>.allocate(capacity: 1)
node.initialize(to: Node(value: val))
var n = list
while n != nil {
if n?.pointee !== after {
n = n?.pointee.next
continue
}
node.pointee.prev = n
node.pointee.next = n?.pointee.next
n?.pointee.next?.pointee.prev = node
n?.pointee.next = node
break
}
return node
}
// [1]
let list = insert(1)
// [1, 2]
insert(2, after: list.pointee, list: list)
// [1, 3, 2]
insert(3, after: list.pointee, list: list)</syntaxhighlight>
=={{header|Tcl}}==
See [[Doubly-Linked List (element)#Tcl|Doubly-Linked List (element)]] for caveats about linked lists in Tcl.
<br>
{{works with|Tcl|8.6}}
<syntaxhighlight lang="tcl">oo::define List {
method insertBefore {elem} {
$elem next [self]
$elem previous $prev
if {$prev ne ""} {
$prev next $elem
}
set prev $elem
}
method insertAfter {elem} {
$elem previous [self]
$elem next $next
if {$next ne ""} {
$next previous $elem
}
set next $elem
}
}</syntaxhighlight>
Demonstration:
<syntaxhighlight lang="tcl">set B [List new 3]
set A [List new 1 $B]
set C [List new 2]
$A insertAfter $C
puts [format "{%d,%d,%d}" [$A value] [[$A next] value] [[[$A next] next] value]]</syntaxhighlight>
=={{header|Visual Basic .NET}}==
<syntaxhighlight lang="vbnet">Public Sub Insert(ByVal a As Node(Of T), ByVal b As Node(Of T), ByVal c As T)
Dim node As New Node(Of T)(value)
a.Next = node
node.Previous = a
b.Previous = node
node.Next = b
End Sub</syntaxhighlight>
=={{header|Wren}}==
{{libheader|Wren-llist}}
<syntaxhighlight lang="wren">import "./llist" for DLinkedList
var dll = DLinkedList.new(["A", "B"])
dll.insertAfter("A", "C")
System.print(dll)</syntaxhighlight>
{{out}}
<pre>
[A <-> C <-> B]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">def \Node\ Prev, Data, Next; \Element (Node) definition
proc Insert(NewNode, Node); \Insert NewNode after Node
int NewNode, Node, NextNode;
[NextNode:= Node(Next);
NextNode(Prev):= NewNode;
NewNode(Next):= NextNode;
NewNode(Prev):= Node;
Node(Next):= NewNode;
];
int Node, A(3), B(3), C(3);
[A(Next):= B;
A(Data):= ^a;
B(Prev):= A;
B(Data):= ^b;
B(Next):= 0;
C(Data):= ^c;
Insert(C, A);
Node:= A;
while Node # 0 do
[ChOut(0, Node(Data));
Node:= Node(Next);
];
]</syntaxhighlight>
{{out}}
<pre>
acb
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Doubly-linked_list/Element_insertion & removal & traverse
// by Galileo, 02/2022
FIL = 1 : DATO = 2 : LPREV = 3 : LNEXT = 4
countNodes = 0 : Nodes = 10
dim list(Nodes, 4)
list(0, LNEXT) = 1
sub searchNode(node)
local i, Node
for i = 0 to node-1
Node = list(Node, LNEXT)
next
return Node
end sub
sub insertNode(node, newNode)
local Node, i
if not countNodes node = 2
for i = 1 to Nodes
if not list(i, FIL) break
next
list(i, FIL) = true
list(i, DATO) = newNode
Node = searchNode(node)
list(i, LPREV) = list(Node, LPREV) : list(list(i, LPREV), LNEXT) = i
if i <> Node list(i, LNEXT) = Node : list(Node, LPREV) = i
countNodes = countNodes + 1
if countNodes = Nodes then Nodes = Nodes + 10 : redim list(Nodes, 4) : end if
end sub
sub removeNode(n)
local Node
Node = searchNode(n)
list(list(Node, LPREV), LNEXT) = list(Node, LNEXT)
list(list(Node, LNEXT), LPREV) = list(Node, LPREV)
list(Node, LNEXT) = 0 : list(Node, LPREV) = 0
list(Node, FIL) = false
countNodes = countNodes - 1
end sub
sub printNode(node)
local Node
Node = searchNode(node)
print list(Node, DATO);
print
end sub
sub traverseList()
local i
for i = 1 to countNodes
printNode(i)
next
end sub
insertNode(1, 1000)
insertNode(2, 2000)
insertNode(2, 3000)
traverseList()
removeNode(2)
print
traverseList()</syntaxhighlight>
{{out}}
<pre>1000
3000
2000
1000
2000
---Program done, press RETURN---</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class Node{
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
fcn toString{ value.toString() }
fcn append(value){
b,c := Node(value,self,next),next;
next=b;
if(c) c.prev=b;
b
}
}</syntaxhighlight>
<syntaxhighlight lang="zkl">a:=Node("a");
a.append("b").append("c");
println(a," ",a.next," ",a.next.next);</syntaxhighlight>
{{out}}
<pre>
a b c
</pre>
{{omit from|ACL2}}
{{omit from|TI-83 BASIC}} {{omit from|TI-89 BASIC}} <!-- Does not have user-defined data structures or objects. -->
| |||