Doubly-linked list/Element 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 doubly-linked list element. The element should include a data member to hold its value and pointers to both the next element in the list and the previous element in the list. The pointers should be mutable.
Ada
<lang ada> type Link; type Link_Access is access Link; type Link is record
Next : Link_Access := null; Prev : Link_Access := null; Data : Integer;
end record; </lang> Using generics, the specification might look like this: <lang ada> generic
type Element_Type is private;
package Linked_List is
type List_Type is limited private;
... private
type List_Element;
type List_Element_Ptr is access list_element;
type List_Element is
record
Prev : List_Element_Ptr; Data : Element_Type; Next : List_Element_Ptr;
end record;
type List_Type is
record
Head : List_Element_Ptr; -- Pointer to first element. Tail : List_Element_Ptr; -- Pointer to last element. Cursor : List_Element_Ptr; -- Pointer to cursor element. Count : Natural := 0; -- Number of items in list. Traversing : Boolean := False; -- True when in a traversal.
end record;
end Linked_List; </lang> In Ada 2005 this example can be written without declaration of an access type: <lang ada> type Link is limited record
Next : not null access Link := Link'Unchecked_Access; Prev : not null access Link := Link'Unchecked_Access; Data : Integer;
end record; </lang> Here the list element is created already pointing to itself, so that no further initialization is required. The type of the element is marked as limited indicating that such elements have referential semantics and cannot be copied.
Ada's standard container library includes a generic doubly linked list. The structure of the link element is private.
ALGOL 68
MODE LINK = STRUCT ( REF LINK prev, REF LINK next, DATA value ); MODE DATA = STRUCT(INT year elected, STRING name); LINK previous, incumbent, elect; previous := (NIL, incumbent, DATA(1993, "Clinton")); incumbent:= (previous, elect,DATA(2001, "Bush" )); elect := (incumbent, NIL, DATA(2008, "Obama" )); REF LINK node := previous; WHILE REF LINK(node) ISNT NIL DO printf(($dddd": "g"; "$,value OF node)); node := next OF node OD; print((newline)); node := elect; WHILE REF LINK(node) ISNT NIL DO printf(($dddd": "g"; "$,value OF node)); node := prev OF node OD; print((newline))
Output:
1993: Clinton; 2001: Bush; 2008: Obama; 2008: Obama; 2001: Bush; 1993: Clinton;
AutoHotkey
<lang AutoHotkey>a_prev = 0 a = 1 a_next = b b_prev = a b = 2 b_next = 0</lang>
C
struct link {
struct link *next;
struct link *prev;
int data;
};
C#
<lang csharp>class Link {
public int item; public Link next; public Link prev;
}</lang>
Common Lisp
<lang lisp>(defstruct dlist head tail) (defstruct dlink content prev next)</lang>
See the functions on the Doubly-Linked List page for the usage of these structures.
D
struct Node(T) {
Node* next, prev;
T data;
}
E
This does no type-checking, under the assumption that it is being used by a containing doubly-linked list object which enforces that invariant along with others such as that element.getNext().getPrev() == element. See Doubly-Linked List#E for an actual implementation (which uses slightly more elaborate nodes than this).
<lang e> def makeElement(var value, var next, var prev) {
def element {
to setValue(v) { value := v }
to getValue() { return value }
to setNext(n) { next := n }
to getNext() { return next }
to setPrev(p) { prev := p }
to getPrev() { return prev }
}
return element
}</lang>
Fortran
In ISO Fortran 95 or later:
type node
real :: data
type(node), pointer :: next => null(), previous => null()
end type node
!
! . . . .
!
type( node ), target :: head
Java
public class Node<T> {
private T element;
private Node<T> next, prev;
public Node<T>(){
next = prev = element = null;
}
public Node<T>(Node<T> n, Node<T> p, T elem){
next = n;
prev = p;
element = elem;
}
public void setNext(Node<T> n){
next = n;
}
public Node<T> getNext(){
return next;
}
public void setElem(T elem){
element = elem;
}
public T getElem(){
return element;
}
public void setNext(Node<T> n){
next = n;
}
public Node<T> setPrev(Node<T> p){
prev = p;
}
public getPrev(){
return prev;
}
}
For use with Java 1.4 and below, delete all "<T>"s and replace T's with "Object".
OCaml
Imperative
<lang ocaml>type 'a dlink = {
mutable data: 'a; mutable next: 'a dlink option; mutable prev: 'a dlink option;
}
let dlink_of_list li =
let rec aux prev_dlink = function
| [] -> prev_dlink
| hd::tl ->
let dlink = {
data = hd;
prev = None;
next = prev_dlink }
in
begin match prev_dlink with
| None -> ()
| Some prev_dlink ->
prev_dlink.prev <- Some dlink
end;
aux (Some dlink) tl
in
aux None (List.rev li)
let list_of_dlink =
let rec aux acc = function
| None -> List.rev acc
| Some{ data = d;
prev = _;
next = next } -> aux (d::acc) next
in
aux []
let iter_forward_dlink f =
let rec aux = function
| None -> ()
| Some{ data = d;
prev = _;
next = next } -> f d; aux next
in
aux
- </lang>
<lang ocaml># let dl = dlink_of_list [1;2;3;4;5] in
iter_forward_dlink (Printf.printf "%d\n") dl ;;
1 2 3 4 5 - : unit = ()</lang>
Functional
The previous implementation is the strict equivalent of the other examples of this page and its task, but in regular OCaml these kind of imperative structures can be advantageously replaced by a functional equivalent, that can be use in the same area, which is to have a list of elements and be able to point to one of these. We can use this type:
<lang ocaml>type 'a nav_list = 'a list * 'a * 'a list</lang>
The middle element is the pointed item, and the two lists are the previous and the following items. Here are the associated functions: <lang ocaml> let nav_list_of_list = function
| hd::tl -> [], hd, tl | [] -> invalid_arg "empty list"
let current = function
| _, item, _ -> item
let next = function
| prev, item, next::next_tl ->
item::prev, next, next_tl
| _ ->
failwith "end of nav_list reached"
let prev = function
| prev::prev_tl, item, next ->
prev_tl, prev, item::next
| _ ->
failwith "begin of nav_list reached"
</lang> <lang ocaml>
- let nl = nav_list_of_list [1;2;3;4;5] ;;
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])
- let nl = next nl ;;
val nl : int list * int * int list = ([1], 2, [3; 4; 5])
- let nl = next nl ;;
val nl : int list * int * int list = ([2; 1], 3, [4; 5])
- current nl ;;
- : int = 3 </lang>
Pascal
type link_ptr = ^link;
data_ptr = ^data; (* presumes that type 'data' is defined above *)
link = record
prev: link_ptr;
next: link_ptr;
data: data_ptr;
end;
Perl
<lang perl>my %node = (
data => 'say what',
next => \%foo_node,
prev => \%bar_node,
); $node{next} = \%quux_node; # mutable</lang>
Pop11
uses objectclass;
define :class Link;
slot next = [];
slot prev = [];
slot data = [];
enddefine;
Python
<lang python>class Node(object):
def __init__(self, data = None, prev = None, next = None):
self.prev = prev
self.next = next
self.data = data
def __str__(self):
return str(self.data)
def __repr__(self):
return repr(self.data)
def iter_forward(self):
c = self
while c != None:
yield c
c = c.next
def iter_backward(self):
c = self
while c != None:
yield c
c = c.prev</lang>
Ruby
<lang ruby>class ListNode
attr_accessor :val, :nxt, :prv
def initialize(mval,mprv=nil,mnxt=nil)
self.val=mval
self.prv=mprv
prv.nxt=self if prv
self.nxt=mnxt
nxt.prv=self if nxt
end
def each(&b)
yield val
nxt.each(&b) if nxt
self
end
include Enumerable
end</lang>
Tcl
While it is highly unusual to implement linked lists in Tcl, since the language has a built-in list type (that internally uses arrays of references), it is possible to simulate it with objects.
<lang tcl>oo::class create List {
variable content next prev
constructor {value {list ""}} {
set content $value
set next $list
set prev ""
if {$next ne ""} {
$next previous [self]
}
}
method value args {
set content {*}$args
}
method next args {
set next {*}$args
}
method previous args {
set prev {*}$args
}
}</lang>
Visual Basic .NET
Public Class Node(Of T) Public Value As T Public [Next] As Node(Of T) Public Previous As Node(Of T) End Class