Doubly-linked list/Element insertion: Difference between revisions
(Added Oz.) |
(→{{header|Oz}}: Correction) |
||
| Line 313: | Line 313: | ||
case @Next of nil then skip |
case @Next of nil then skip |
||
[] node(prev:NextPrev ...) then |
[] node(prev:NextPrev ...) then |
||
NextPrev := NewNode |
|||
end |
end |
||
Next := NewNode |
Next := NewNode |
||
Revision as of 21:59, 12 January 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Use the link structure defined in Doubly-Linked List (element) to define a procedure for inserting a link into a doubly-linked list. Call this procedure to insert element C into a list {A,B}, between elements A and B.
This is much like inserting into a Singly-Linked List, but with added assignments so that the backwards-pointing links remain correct.
Ada
Define the procedure: <lang ada>procedure Insert (Anchor : Link_Access; New_Link : Link_Access) is begin
if Anchor /= Null and New_Link /= Null then
New_Link.Next := Anchor.Next;
New_Link.Prev := Anchor;
if New_Link.Next /= Null then
New_Link.Next.Prev := New_Link;
end if;
Anchor.Next := New_Link;
end if;
end Insert;</lang> Create links and form the list.
<lang ada>procedure Make_List is
Link_Access : A, B, C;
begin
A := new Link; B := new Link; C := new Link; A.Data := 1; B.Data := 2; C.Data := 2; Insert(Anchor => A, New_Link => B); -- The list is (A, B) Insert(Anchor => A, New_Link => C); -- The list is (A, C, B)
end Make_List;</lang>
Element insertion using the generic doubly linked list defined in the standard Ada containers library.
<lang ada>with Ada.Containers.Doubly_Linked_Lists; with Ada.Text_Io; use Ada.Text_Io; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
procedure List_Insertion is
package String_List is new Ada.Containers.Doubly_Linked_Lists(Unbounded_String);
use String_List;
procedure Print(Position : Cursor) is
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;</lang>
AutoHotkey
<lang AutoHotkey>a_prev = 0 a = 1 a_next = b b_prev = a b = 2 b_next = 0 c = 4
insert_between("c", "a", "b") ListVars return
insert_between(new, prev, next) {
local temp %prev%_next := new %new%_prev := prev %new%_next := next %next%_prev := new
}</lang>
C
Define the function: <lang c>void insert(link* anchor, link* newlink) {
newlink->next = anchor->next; newlink->prev = anchor; (newlink->next)->prev = newlink; anchor->next = newlink;
}</lang>
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).
To call the function:
Create links, and form the list: <lang c>link a, b, c; a.next = &b; a.prev = null; a.data = 1; b.next = null; b.prev = &a; b.data = 3; c.data = 2;</lang>
This list is now {a,b}, and c is separate.
Now call the function: <lang c>insert(&a, &c);</lang>
This function call changes the list from {a,b} to {a,b,c}.
C#
The function handles creation of nodes in addition to inserting them. <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 };
}</lang> Example use: <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);
}</lang>
Common Lisp
Code is on the Doubly-Linked List page, in function insert-between.
E
<lang e>def insert(after, value) {
def newNode := makeElement(value, after, after.getNext()) after.getNext().setPrev(newNode) after.setNext(newNode)
}</lang>
<lang e>insert(A_node, C)</lang>
Fortran
In ISO Fortran 95 or later: <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 ), target :: head
type( node ), pointer :: current, next
head%data = 1.0
current => head
do i = 1, 20
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</lang> Output: <lang fortran>1. 2. 4. 8. 16. 32. 64. 128. 256. 512. 1024. 2048. 4096. 8192. 16384. 32768. 65536. 131072. 262144. 524288. 1048576.</lang>
Haskell
Using the algebraic data type and update functions from Doubly-Linked_List_(element)#Haskell.
<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
</lang>
JavaScript
See Doubly-Linked_List_(element)#JavaScript <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));</lang>
OCaml
with dlink
<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";;</lang>
testing in the top level:
<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]</lang>
<lang ocaml>(* val insert : 'a nav_list -> 'a -> 'a nav_list *) let insert (prev, cur, next) v = (prev, cur, v::next)</lang>
testing in the top level: <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])</lang>
Oz
Warning: Do not use in real programs. <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}</lang>
Pascal
<lang pascal>procedure insert_link( a, b, c: link_ptr ); begin
a^.next := c; if b <> nil then b^.prev := c; c^.next := b; c^.prev := a;
end;</lang>
Actually, a more likely real world scenario is 'insert after A'. So...
<lang pascal>procedure realistic_insert_link( a, c: link_ptr ); begin
if a^.next <> nil then a^.next^.prev := c; (* 'a^.next^' is another way of saying 'b', if b exists *) c^.next := a^.next; a^.next := c; c^.prev := a;
end;</lang>
Pop11
<lang pop11>define insert_double(list, element);
lvars tmp;
if list == [] then
;;; Insertion into empty list, return element
element
else
next(list) -> tmp;
list -> prev(element);
tmp -> next(element);
element -> next(list);
if tmp /= [] then
element -> prev(tmp)
endif;
;;; return original list
list
endif;
enddefine;
lvars A = newLink(), B = newLink(), C = newLink();
- Build the list of A and B
insert_double(A, B) -> _;
- insert C between A and b
insert_double(A, C) -> _;</lang>
Python
<lang python>def insert(anchor, new):
new.next = anchor.next new.prev = anchor anchor.next.prev = new anchor.next = new</lang>
Ruby
<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)</lang>
Tcl
See Doubly-Linked List (element) for caveats about linked lists in Tcl.
<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
}
}</lang> Demonstration: <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]]</lang>
Visual Basic .NET
<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</lang>