Singly-linked list/Element insertion: Difference between revisions
(→{{header|Tcl}}: corrected to solve the challenge, not a misreading of it) |
m (→{{header|Tcl}}: oops!) |
||
Line 495: | Line 495: | ||
set A [List new "A" [List new "B"]] |
set A [List new "A" [List new "B"]] |
||
$A insertAfter [List new " |
$A insertAfter [List new "C"]</lang> |
Revision as of 07:54, 24 May 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Using the link element defined in Singly-Linked List (element), define a method to insert an element into a singly-linked list following a given element.
Using this method, insert an element C into a list comprised of elements A->B, following element A.
Ada
We must create a context clause making the predefined generic procedure Ada.Unchecked_Deallocation visible to this program. <lang ada>
with Ada.Unchecked_Deallocation; -- Define the link type procedure Singly_Linked is type Link; type Link_Access is access Link; type Link is record Data : Integer; Next : Link_Access := null; end record; -- Instantiate the generic deallocator for the link type procedure Free is new Ada.Unchecked_Deallocation(Link, Link_Access); -- Define the procedure procedure Insert_Append(Anchor : Link_Access; Newbie : Link_Access) is begin if Anchor /= null and Newbie /= null then Newbie.Next := Anchor.Next; Anchor.Next := Newbie; end if; end Insert_Append; -- Create the link elements A : Link_Access := new Link'(1, null); B : Link_Access := new Link'(2, null); C : Link_Access := new Link'(3, null); -- Execute the program begin Insert_Append(A, B); Insert_Append(A, C); Free(A); Free(B); Free(C); end Singly_Linked;
</lang>
ALGOL 68
Linked lists are not built into ALGOL 68 per se, nor any available standard library. However Linked lists are presented in standard text book examples. Or can be manually constructed, eg: <lang algol>MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);
STRINGLIST list := ("Big",
LOC STRINGLIST := ("fjords", LOC STRINGLIST := ("vex", LOC STRINGLIST := ("quick", LOC STRINGLIST := ("waltz", LOC STRINGLIST := ("nymph",NIL))))));
PROC insert = (REF STRINGLIST list, node)VOID: (
next OF node := next OF list; next OF list := node
);
STRINGLIST very := ("VERY", NIL);
- EXAMPLE OF INSERTION #
insert(next OF next OF list, very );
REF STRINGLIST node := list; WHILE REF STRINGLIST(node) ISNT NIL DO
print((value OF node, space)); node := next OF node
OD; print((newline)) </lang>
Output:
Big fjords vex VERY quick waltz nymph
C
Define the method:
<lang c> void insert_append (link *anchor, link *newlink) {
newbie->next = anchor->next; anchor->next = newlink; }</lang>
Note that in a production implementation, one should check anchor and newlink to ensure they're valid values. (I.e., not NULL.)
And now on to the code.
Create our links. <lang c> link *a, *b, *c;
a = malloc(sizeof(link)); b = malloc(sizeof(link)); c = malloc(sizeof(link)); a->data = 1; b->data = 2; c->data = 3;</lang>
Prepare our initial list <lang c> insert_append (a, b);</lang>
Insert element c after element a <lang c> insert_append (a, c); </lang>
Remember to free the memory once we're done. </lang c> free (a);
free (b); free (c);</lang>
C++
This uses the generic version of the link node. Of course, normally this would be just some implementation detail inside some list class, not to be used directly by client code.
<lang cpp> template<typename T> void insert_after(link<T>* list_node, link<T>* new_node)
{ new_node->next = list_node->next; list_node->next = new_node; };</lang>
Here's the example code using that method:
The following code creates the links. As numeric values I've just taken the corresponding character values. <lang cpp> link<int>* a = new link<int>('A', new link<int>('B'));
link<int>* c = new link<int>('C');</lang>
Now insert c after a: <lang cpp> insert_after(a, c);</lang>
Finally destroy the list: <lang cpp> while (a)
{ link<int>* tmp = a; a = a->next; delete tmp; }</lang>
D
This is similar to C++ example.
<lang D> Node!(T) insert_element_after(T)(Node!(T) dst, Node!(T) src) {
src.next = dst.next; dst.next = src; return dst;
} </lang>
Sample usage (tango based): <lang D> void main() {
alias Node!(char[]) NodeStr; auto a = new NodeStr("alpha", new NodeStr("bravo")); auto c = new NodeStr("charlie");
insert_element_after(a, c);
// print out while (a) { Stdout(a.data) (" -> "); a = a.next; } // gc will handle allocated memory
} </lang>
Delphi
A simple insertion into a one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever. NOTE: For original versions of Turbo Pascal, substitute the MemAvail Function for the Try Except block as this does not exist in this version of the pascal language. Also, Turbo Pascal doesn't have C++-style comments, therefore those have to be replaced with Pascal style comments, i.e. { ... } or (* ... *).
<lang delphi>
// Using the same type defs from the one way list example.
Type
// The pointer to the list structure pOneWayList = ^OneWayList;
// The list structure OneWayList = record pData : pointer ; Next : pOneWayList ; end;
// I will illustrate a simple function that will return a pointer to the // new node or it will return NIL. In this example I will always insert // right, to keep the code clear. Since I am using a function all operations // for the new node will be conducted on the functions result. This seems // somewhat counter intuitive, but it is the simplest way to accomplish this.
Function InsertNode(VAR CurrentNode:pOneWayList): pOneWayList begin
// I try not to introduce different parts of the language, and keep each // example to just the code required. in this case it is important to use // a try/except block. In any OS that is multi-threaded and has many apps // running at the same time, you cannot rely on a call to check memory available // and then attempting to allocate. In the time between the two, another // program may have grabbed the memory you were trying to get.
Try // Try to allocate enough memory for a variable the size of OneWayList GetMem(Result,SizeOf(OneWayList)); Except On EOutOfMemoryError do begin Result := NIL exit; end; end;
// Initialize the variable. Result.Next := NIL ; Reuslt.pdata := NIL ;
// Ok now we will insert to the right.
// Is the Next pointer of CurrentNode Nil? If it is we are just tacking // on to the end of the list.
if CurrentNode.Next = NIL then CurrentNode.Next := Result else // We are inserting into the middle of this list Begin Result.Next := CurrentNode.Next ; CurrentNode.Next := result ; end;
end; </lang>
E
<lang e> def insertAfter(head :LinkedList ? (!head.null()),
new :LinkedList ? (new.next().null())) { new.setNext(head.next()) head.setNext(new) }
def a := makeLink(1, empty) def b := makeLink(2, empty) def c := makeLink(3, empty) insertAfter(a, b) insertAfter(a, c)
var x := a while (!x.null()) { println(x.value()) x := x.next() }</lang>
Forth
Using the linked list concept described in the Singly-Linked_List_(element) topic: <lang forth> \ Create the list and some list elements
create A 0 , char A , create B 0 , char B , create C 0 , char C ,</lang>
Now insert b after a and c after b, giving a->b->c <lang forth> B A chain
C B chain</lang>
Here is an abbreviated version of the definition of 'chain' from the other article: <lang forth> : chain ( a b -- ) 2dup @ swap ! ! ;</lang>
Fortran
In ISO Fortran 95 or later: <lang fortran> subroutine addAfter(nodeBefore,value)
type (node), intent(inout) :: nodeBefore type (node), pointer :: newNode allocate(newNode) newNode%data = value newNode%next => nodeBefore%next nodeBefore%next => newNode end subroutine addAfter</lang>
Haskell
This kind of list manipulation is unidiomatic Haskell. But you can try the following: <lang haskell> insertAfter a b (c:cs) | a==c = a : b : cs
| otherwise = c : insertAfter a b cs insertAfter _ _ [] = error "Can't insert"</lang>
Logo
<lang logo> to insert :after :list :value
localmake "tail member :after :list if not empty? :tail [.setbf :tail fput :value bf :tail] output :list end
show insert 5 [3 5 1 8] 2</lang> [3 5 2 1 8]
OCaml
This kind of list manipulation is unidiomatic OCaml. But you can try the following: <lang ocaml>let rec insert_after a b = function
c :: cs when a = c -> a :: b :: cs | c :: cs -> c :: insert_after a b cs | [] -> raise Not_found</lang>
Pascal
Note: This code uses only Standard Pascal features. For code using features only available in modern Pascal versions, see above under "[Delphi / Object Pascal / >>Turbo Pascal<<]"
Since Standard Pascal doesn't know a generic pointer type, and also no generic types, one has to settle for a specific data type for the linked list. Since the task mentions node names "A", "B", "C", here a char is chosen. Of course any data type (including pointers to a specific data type) could have been used here.
<lang pascal> type
pCharNode = ^CharNode; CharNode = record data: char; next: pCharNode; end; (* This procedure inserts a node (newnode) directly after another node which is assumed to already be in a list. It does not allocate a new node, but takes an already allocated node, thus allowing to use it (together with a procedure to remove a node from a list) for splicing a node from one list to another. *) procedure InsertAfter(listnode, newnode: pCharNode); begin newnode^.next := listnode^.next; listnode^.next := newnode; end;</lang>
Usage example: <lang pascal> var
A, B: pCharNode; begin (* build the two-component list A->C manually *) new(A); A^.data := 'A'; new(A^.next); A^.next^.data := 'C'; A^.next^.next := nil; (* create the node to be inserted. The initialization of B^.next isn't strictly necessary (it gets overwritten anyway), but it's good style not to leave any values undefined. *) new(B); node^.data := 'B'; node^.next := nil; (* call the above procedure to insert node B after node A *) InsertAfter(A, B);
(* delete the list *) while A <> nil do begin B := A; A := A^.next; dispose(B); end end.</lang>
Perl
If you don't really need the constant-time insertion property of singly linked lists, just use an array. You can traverse and splice it any way. <lang perl> my @l = ($A, $B);
push @l, $C, splice @l, 1;</lang>
However, if you really need a linked list, or all you got is an algorithm in a foreign language, you can use references to accomplish the translation. <lang perl> sub insert_after {
# first argument: node to insert after # second argument: node to insert $_[1]{next} = $_[0]{next}; $_[0]{next} = $_[1]; } my %B = ( data => 3, next => undef, # not a circular list ); my %A = ( data => 1, next => \%B, ); my %C = ( data => 2, ); insert_after \%A, \%C;</lang>
Note that you don't have to name your new nodes. The following works just as well: <lang perl> insert_after \%A, { data => 2 };</lang> Note the curly braces instead of round parentheses.
It is straightforward to extend the function to take an arbitrary number of list nodes to insert: <lang perl> sub insert_after {
my $node = $_[0]; my $next = $node->{next}; shift; while (defined $_[0]) { $node->{next} = $_[0]; $node = $node->{next}; shift; } $node->{next} = $next; }</lang>
With this, it's rather easy to build a list: <lang perl> my %list = ( data => 'A' );
insert_after \%list, { data => 'B' }, { data => 'C' };</lang>
List handling is simplified if the variables themselves contain references. For example: <lang perl> my $list2;
# create a new list ('A'. 'B', 'C') and store it in $list2 insert_after $list2 = { data => 'A' }, { data => 'B' }, { data => 'C' }; # append two new nodes ('D', 'E') after the first element insert_after $list2, { data => 'A2' }, { data => 'A3' }; # append new nodes ('A2a', 'A2b') after the second element (which now is 'A2') insert_after $list2->{next}, { data => 'A2a' }, { data => 'A2b' };</lang>
Pop11
In Pop11 one normally uses built-in lists:
<lang pop11> define insert_into_list(anchor, x);
cons(x, back(anchor)) -> back(anchor); enddefine; ;;; Build inital list lvars l1 = cons("a", []); insert_into_list(l1, "b"); ;;; insert c insert_into_list(l1, "c");</lang>
If one wants one can use user-defined list node (for convenience we repeat definition of list node):
<lang pop11> uses objectclass;
define :class ListNode; slot value = []; slot next = []; enddefine;
define insert_into_List(anchor, x); consListNode(x, next(anchor)) -> next(anchor); enddefine; ;;; Build inital list lvars l2 = consListNode("a", []); insert_into_List(l2, "b"); ;;; insert c insert_into_List(l2, "c");</lang>
Note that user-defined case differs from built-in case only because of names.
Python
<lang python> def chain_insert(lst, at, item):
while lst is not None: if lst[0] == at: lst[1] = [item, lst[1]] return else: lst = lst[1] raise ValueError(str(at) + " not found")
chain = ['A', ['B', None]] chain_insert(chain, 'A', 'C') print chain </lang> Output: <lang python> ['A', ['C', ['B', None]]] </lang>
Ruby
<lang ruby> class ListNode
def insertAfter(a,b) if a==value self.succ = ListNode.new(b,succ) else succ.insertAfter(a,b) end end end
list = ListNode.new(:a,ListNode.new(:b)) list.insertAfter(:a,:c)</lang>
Scheme
Non-mutating: <lang scheme>(define (insert-after a b lst)
(if (null? lst) lst ; This should be an error, but we will just return the list untouched (let ((c (car lst)) (cs (cdr lst))) (if (equal? a c) (cons a (cons b cs)) (cons c (insert-after a b cs))))))</lang>
Mutating: <lang scheme>(define (insert-after! a b lst)
(let ((pos (member a lst))) (if pos (set-cdr! pos (cons b (cdr pos))))))</lang>
Tcl
<lang tcl># Assume rest of definition is already present oo::define List method insertAfter element {
$element attach $next set next $element
}
set A [List new "A" [List new "B"]] $A insertAfter [List new "C"]</lang>