Doubly-Linked List (element)

From Rosetta Code

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.

Contents 1 Ada 2 ALGOL 68 3 C 4 Fortran 5 Java 6 OCaml 7 Pascal 8 Perl 9 Pop11 10 Python 11 Ruby

[edit] 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;
 

In Ada 2005 this example can be written without declaration of an access type:

 
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;
 

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.

[edit] ALGOL 68

MODE LINK = STRUCT (
  REF LINK next,
  REF LINK prev,
  INT data
);
LINK example;
~

[edit] C

struct link (
  struct link *next;
  struct link *prev;
  int data;
);

[edit] 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

[edit] Java

Works with: Java version 1.5+

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".

[edit] 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 iter_forward_dlink f =
  let rec aux = function
  | None -> ()
  | Some{ data = d;
          prev = _;
          next = next } -> f d; aux next
  in
  aux
;;

# 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 = ()

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:

type 'a nav_list = 'a list * 'a * 'a list

The middle element is the pointed item, and the two lists are the previous and the following items. Here are the associated functions:

 
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"
 

 
# 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
 

[edit] 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;

[edit] Perl

Just use an array. You can traverse and splice it any way. Linked lists are way too low level.

However, if all you have is an algorithm in another language, you can use references to accomplish the translation.

my %node = (
    data => 'say what',
    next => \%foo_node,
    prev => \%bar_node,
);
$node{next} = \%quux_node;  # mutable

[edit] Pop11

uses objectclass;
define :class Link;
    slot next = [];
    slot prev = [];
    slot data = [];
enddefine;

[edit] 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

[edit] 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